On two proofs of $d^2$ mixing of weighted Dikin walks

On two proofs of d2 mixing of weighted Dikin walks

arXiv:2608.28566v1 [cs.DS] 28 Aug 2026

Yuansi Chen ETH Zürich yuansi.chen@stat.math.ethz.ch

Yunbum Kook University of Michigan ybkook@umich.edu

Abstract We study the mixing time of weighted Dikin walks for sampling from exponential distributions on polytopes and truncated positive-semidefinite (PSD) cones. Our first result gives a general total-variation mixing bound under strong self-concordance, ν̄-symmetry, and mixed-trace regularity on the local metric. The key idea is to control the Metropolis–Hastings acceptance probability on a high-probability region rather than at every point. Applying this framework e 2 ) mixing bound for sampling to the Lee–Sidford, Lewis-weight, and John metrics yields an O(d e 4 ) mixing bound for sampling from polytopes, while applying it to a hybrid barrier yields an O(d from truncated PSD cones. Our second result establishes stronger χ2 -divergence guarantees and pointwise acceptance control using a new fourth-order bootstrap condition. For a suitably e 2 ) mixing bound in χ2 -divergence, improving on scaled Lee–Sidford metric, this yields an O(d 9/4 e the previous O(d ) bound.

1

Introduction

Sampling uniformly from a high-dimensional convex body is a fundamental primitive in polynomialtime randomized algorithms for computing the volume of the body [DFK91, LS93, KLS97, LV06b, CV18, JLLV26]. A long line of work has studied the complexity of this algorithmic task assuming access to a membership oracle for the convex body K, which answers whether a queried point lies in K. This abstract computational model has provided a common setting for designing algorithms and analyzing their complexity. For instance, general-purpose samplers such as the Ball walk [Lov90, LS93, KLS97], Hit-and-Run [Lov99, LV06a, KV26a], and In-and-Out [KVZ26, KV25a, KV25b, KV26b] have been developed and analyzed. In practice, we often know an explicit description of a convex body. For instance, a polytope— finitely many linear inequalities—is a canonical convex body, and uniform sampling from a polytope has found applications in Bayesian statistics, machine learning, and systems biology. It is natural to ask whether one can leverage this additional information to design more efficient sampling algorithms. Kannan and Narayanan [KN12] proposed the Dikin walk, which exploits the inequality description to construct position-dependent Gaussian proposals. Inspired by interior-point methods (IPMs) for structured convex optimization [Dik67, Kar84, NN94], the walk uses the Hessian of a barrier function as its local metric. For a bounded, full-dimensional polytope K := P {x ∈ Rd : Ax ≥ b} T with A ∈ Rm×d and b ∈ Rm , the Hessian of the logarithmic barrier ϕlog (x) := − m i=1 log(ai x − bi ) encodes the local geometry of the polytope, and Kannan and Narayanan showed that the Dikin e walk with this local geometry mixes in O(md) iterations from an O(1)-warm start [KN12, SV16]. This m-dependence is representation-dependent, since redundant constraints can increase m without changing K. The optimization literature has addressed this issue through Vaidya’s volumetriclogarithmic barrier and the Lewis-weight-based Lee–Sidford barrier [Vai96, CP15, LS19], which 1

Table 1: Comparison of the two generic mixing frameworks. Framework Acceptance control

Metric assumptions

Conductance

Theorem 1 High-prob. region Theorem 2 Pointwise

SSC, ν̄-symmetry, mixed 23-trace Above conditions, LTSC, fourth-order bootstrap

s-conductance TV Conductance

Guarantee Applications

χ2

LS, Lewis-weight, John, hybrid PSD Scaled LS

improve the dependence of IPM iteration complexity on m. This suggests an analogous route to reduce the dependence on m in sampling with the Dikin walk. Implementing these ideas, Chen, Dwivedi, Wainwright, and Yu introduced the Vaidya and John walks [CDWY18]. The Vaidya walk, based on the volumetric-logarithmic barrier, has an e 1/2 d3/2 ) warm-start mixing bound. The John walk, based on approximate John ellipsoids, O(m e 5/2 ) warm-start mixing bound. They further conjectured that a refined analysis would has an O(d e 2 ). improve the John-walk bound to O(d 2 e An O(d ) mixing bound is consistent with progress in both optimization and general-purpose sampling. For linear programming, the Lee–Sidford√barrier improves the interior-point iteration e √m) for the logarithmic barrier to O( e d), leaving only polylogarithmic dependence bound from O( on the number of constraints [LS19]. For uniform sampling, general-purpose samplers achieve e 2 ) mixing from an O(1)-warm start when the body is isotropic (i.e., the covariance is close to O(d the identity) [KLS97, Kla23, KVZ26, KV26a]. Since the Dikin walk is affine-invariant, one may e 2 ) a natural goal for a weighted Dikin walk. think of it as enforcing ‘local’ isotropy, making O(d Laddha, Lee, and Vempala proposed a route to this goal based on strong self-concordance and ν̄-symmetry [LLV20]. Strong self-concordance is a stronger version of usual self-concordance required for an improved analysis, while ν̄-symmetry measures how well the local Dikin ellipsoid approximates the largest centrally symmetric subset of the body centered at the current point. Their e conductance argument would give an O(dν̄) warm-start mixing bound if transition overlap held for e nearby points. Such transition overlap, together with their estimate ν̄ = O(d) for the Lee–Sidford 2 e metric, would imply O(d ) mixing. Their Metropolis–Hastings analysis, however, does not establish this transition overlap, leaving the implication incomplete1 . Later works [KV24, JC25] analyzed e 2.5 ). Recently, the Dikin walk with the Lewis-weight metric, but their mixing bounds remain at O(d e 9/4 ) warmusing the Lee–Sidford metric, [Koo26] showed that a higher-order analysis yields an O(d start mixing bound for exponential sampling, making progress toward the conjectured d2 bound. e We resolve this conjecture with two main results. First, Theorem 1 proves an O(dν̄) totalvariation mixing bound for exponential sampling under fewer assumptions than prior work [KV24, JC25]. Unlike prior work, we show that the Dikin proposal has high acceptance probability for most points rather than at every point; this allows us to prove the mixing bound under weaker assumptions. This framework allows us to easily verify the conditions for the Lee–Sidford, Lewis-weight, e 2 ) mixing bound. Moreover, it gives an O(n e 2 ) mixing bound for a and John metrics, yielding an O(d hybrid metric on truncated positive-semidefinite cones of ambient dimension n = Θ(d2 ), improving on previous mixing bounds [Nar16, KV24]. Second, Theorem 2 imposes additional assumptions to obtain high acceptance probability at every point, resulting in a stronger χ2 -divergence guarantee. e 2 ) mixing bound for the Lee–Sidford Dikin walk from total variation to This strengthens the O(d 2 χ -divergence. Table 1 summarizes the two frameworks and their applications. 1

Detailed expositions can be found in [Koo26]

2

2

Preliminaries

This section introduces the basic setup, the Dikin walk, regularity conditions, and the weighted metrics used in our applications.

2.1

Basic setup and notation

a ≲ b means a ≤ Cb for a universal constant C > 0, and similarly for ≳. We use a ≍ b if a ≲ b e to suppress factors polylogarithmic in m, d, ν̄, the inverse accuracy, and and b ≲ a. We use O(·) the warm-start parameter. Here ν̄ is the symmetry parameter introduced in Definition 2. Other standard notation is clarified in §A. Convex bodies and polytopes. A convex body is a compact convex set with nonempty interior. Unless stated otherwise, K ⊂ Rd is a full-dimensional convex body, and int K and B(K) denote its interior and Borel σ-algebra, respectively. We denote a polytope by K = {x ∈ Rd : Ax ≥ b}, where A has full column rank and no zero rows, and b ∈ Rm . Probability. We use the same symbol for a probability measure and its Lebesgue density when clear from context. For probability measures µ and ν, their total-variation (TV) distance is R 2 dTV (µ, ν) := supE |µ(E) − ν(E)|. Their chi-square divergence is χ2 (µ ∥ ν) := ( dµ dν − 1) dν if 2 2 2 µ ≪ ν; otherwise χ (µ ∥ ν) = ∞. Note that 4dTV ≤ χ . Throughout the paper, we aim to sample from an exponential distribution on K: for θ ∈ Rd , Z 1 T exp(−θT x) dx , πθ (dx) := exp(−θ x) IK (x) dx for Zθ := Zθ K where IK is the indicator function of K. Basic facts about Markov chains and mixing are deferred to §A.

2.2

Local metrics and the Dikin walk

Local metric. Let g : int K → Sd++ be a local metric. We identify symmetric matrices with their bilinear forms and write g(x)[u, v] := uT g(x)v. For h ∈ Rd , its local norm at x is ∥h∥2g(x) := hT g(x)h. The corresponding Dikin ellipsoid of radius ρ > 0 is Dg (x, ρ) := {y ∈ Rd : ∥y − x∥g(x) ≤ ρ} . For the Hessian metric of a self-concordant barrier, the unit Dikin ellipsoid is contained in K [NN94, Theorem 2.1.1]. √ Dikin walk. Given a local metric g and a proposal radius r > 0, set η := r/ d. From a current state x ∈ int K, one step of the Dikin walk proceeds as follows. 1. Sample a proposal Y ∼ Px := N(x, η 2 g(x)−1 ), whose density is p
det g(x) 1 2 px (y) = exp − ∥y − x∥ . g(x) 2η 2 (2πη 2 )d/2

(1)

2. If Y ∈ int K, move to Y with the Metropolis–Hastings acceptance probability αg (x, Y ) defined below; otherwise remain at x.

3

Equivalently, the proposal can be written as Y = x + ηH for H | X = x ∼ N(0, g(x)−1 ). For x, y ∈ int K, we call py (x)/px (y) the proposal-density ratio and its logarithm the log proposal-density ratio. For the target πθ , the acceptance probability can be written as  min1, exp(−⟨θ, y − x⟩) py (x) , y ∈ int K , px (y) αg (x, y) =  0, y∈ / int K , (2)
 1 py (x) det g(y)
1/2 = exp − 2 (y − x)T g(y) − g(x) (y − x) . px (y) det g(x) 2η Let T be the resulting transition kernel, and set Tx := T (x, ·). The Metropolis correction makes T reversible with respect to πθ , so πθ is stationary. We use Te for its lazy version. Dikin metrics on polytopes.

For a polytope K = {Ax ≥ b} and x ∈ int K, define

sx := Ax − b ∈ Rm >0 ,

Sx := Diag sx ,

Ax := Sx−1 A .

Writing ai and ax,i for the i-th rows of A and Ax , respectively, we have ax,i = ai /sx,i . The weighted Dikin metrics considered in this paper have the form g(x) := AT x W x Ax ,

Wx := Diag wx ,

wx ∈ Rm >0 .

The Dikin walk with this metric is called a weighted Dikin walk.

2.3

Regularity conditions for mixing

We first state the regularity conditions used in the high-probability conductance framework and then recall two additional conditions used in the pointwise acceptance analysis. Self-concordance and symmetry. Self-concordance is standard in interior-point theory [NN94] and Dikin-walk analysis [KN12]. Strong self-concordance and ν̄-symmetry were introduced for Dikin-walk sampling by Laddha, Lee, and Vempala [LLV20]. Below, for a differentiable map F , DF (x)[h] denotes the first directional derivative of F at x in the direction h ∈ Rd . Definition 1 (Self-concordance and strong self-concordance). Let g : int K → Sd++ be continuously differentiable (C 1 ). The metric g is self-concordant if, for every x ∈ int K and h ∈ Rd , ∥g(x)−1/2 Dg(x)[h] g(x)−1/2 ∥op ≤ 2 ∥h∥g(x) . Equivalently, −2g(x)∥h∥g(x) ⪯ Dg(x)[h] ⪯ 2g(x)∥h∥g(x) . It is called strongly self-concordant (SSC) if the stronger Frobenius-norm bound holds: ∥g(x)−1/2 Dg(x)[h] g(x)−1/2 ∥F ≤ 2 ∥h∥g(x)

for any x ∈ int K and h ∈ Rd .

Definition 2 (ν̄-symmetry). For ν̄ ≥ 1, a local metric g on a convex body K is ν̄-symmetric if √ Dg (x, 1) ⊆ K ∩ (2x − K) ⊆ Dg (x, ν̄) for any x ∈ int K , where 2x − K is the reflection of K about x.

4

Mixed-trace regularity. tensor Jxg : (Rd )3 → R by

For a C 1 local metric g and x ∈ int K, define the normalized derivative

Jxg [u, v, w] := (g(x)−1/2 u)T Dg(x)[g(x)−1/2 w] g(x)−1/2 v . This tensor is symmetric in its first two arguments. For an orthonormal basis {ei }di=1 , define ∥Jxg ∥{12}{3} :=

d X

sup

∥w∥=1 i,j=1

(Tr12 Jxg )k :=

Jxg [ei , ej , w]2

d X

1/2

= sup ∥g(x)−1/2 Dg(x)[g(x)−1/2 w] g(x)−1/2 ∥F , ∥w∥=1

Jxg [ei , ei , ek ] ,

(Tr23 Jxg )i :=

i=1

d X

Jxg [ei , ej , ej ] .

j=1

The norm and the resulting contraction vectors are independent of the orthonormal basis. When g is clear from context, we write Jx := Jxg . Note that SSC is equivalent to ∥Jxg ∥{12}{3} ≤ 2. Definition 3 (Mixed-23-trace). For γ ≥ 0, a C 1 local metric g has γ-bounded mixed 23-trace if √ for every x ∈ int K . ∥Tr23 Jxg ∥ ≤ γ d When γ is a universal constant, we simply say that g has bounded mixed 23-trace. This term naturally arises when we analyze the first-order derivative of some quantity in (22). Remark 1 (Mixed trace for Hessian metrics). SSC gives √ √ ∥Tr12 Jxg ∥ ≤ d ∥Jxg ∥{12}{3} ≤ 2 d . If g = ∇2 f for a C 3 function f , then Jxg is fully symmetric. Consequently, Tr23 Jxg = Tr12 Jxg , so an SSC Hessian metric has 2-bounded mixed 23-trace. Second-order derivative. For a twice-differentiable map F , we use D2 F (x)[h1 , h2 ] to denote its second directional derivative in the directions h1 and h2 . For a C 2 local metric g and x ∈ int K, define the normalized second-derivative tensor Qgx [u, v, w, z] := D2 g(x)[g(x)−1/2 w, g(x)−1/2 z][g(x)−1/2 u, g(x)−1/2 v] .

(3)

It is symmetric in (u, v) and in (w, z). If g = ∇2 f for a C 4 function f , then Qgx is fully symmetric. For an orthonormal basis {ei }di=1 , define (Tr12 Qgx )[w, z] :=

d X

Qgx [ei , ei , w, z] .

i=1

For h = g(x)−1/2 w,

2

D

(Tr12 Qgx )[w, w] = Tr g(x)−1 D2 g(x)[h, h] ,

(4)

log det g(x)[h, h] = (Tr12 Qgx )[w, w] − ∥Jxg [ ·, ·, w]∥2F .

(5)

Kook and Vempala [KV24] introduced lower-trace self-concordance and the original one-sided form of average self-concordance. We use the two-sided form stated by Jiang and Chen [JC25]. 5

Definition 4 (Lower-trace self-concordance). Let g : int K → Sd++ be C 2 . It is lower-trace selfconcordant (LTSC) if for every x ∈ int K, Tr12 Qgx ⪰ −Id . Equivalently, Tr(g(x)−1 D2 g(x)[h, h]) ≥ −∥h∥2g(x) for every x ∈ int K and h ∈ Rd . Definition 5 (Average self-concordance). A local metric g is average self-concordant (ASC) if, for every ε ∈ (0, 1/2), there is a radius rε > 0, depending only on ε and not on d, such that for every x ∈ int K and 0 < r ≤ rε , PY ∼N(x, r2 g(x)−1 ) Y ∈ int K and |∥Y − x∥2g(Y ) − ∥Y − x∥2g(x) | ≤ d

2.4

2εr2
≥ 1 − ε. d

Weighted Dikin metrics

We now define the special metrics used in the polytope applications. Leverage scores. For a full-column-rank matrix B ∈ Rm×d , let σ(B) := diag(B(B T B)−1 B T ) ∈ 1/2 [0, 1]m denote its leverage-score vector. For the weighted Dikin metric, set Bx := Wx Ax . All leverage scores of Bx are positive since A has no zero rows. The identity −1 σi (Bx ) = wx,i aT x,i g(x) ax,i

for each i ∈ [m]

(6)

shows that Dg (x, 1) ⊆ K Lewis weights.

⇐⇒

−1 aT x,i g(x) ax,i ≤ 1 for every i

⇐⇒

σ(Bx ) ≤ wx

entrywise .

(p)

For p ≥ 2, the ℓp -Lewis weights of Ax are the unique vector wx ∈ Rm >0 satisfying wx(p) = σ([Wx(p) ]1/2−1/p Ax )

for Wx(p) := Diag wx(p) .

P (p) (p) The fixed-point identity gives m i=1 wx,i = d and Wx ⪯ Im , and the weights vary smoothly with x ∈ int K [LS19, Lemmas 22, 24, and 47]. (1) Lee–Sidford metric. For pLS = 2 (1 + log m) and ΛLS = pLS 2 , the normalized Lee–Sidford (LS) metric [LS19, LLV20] is (pLS ) 1−2/pLS gLS (x) := Λ2LS AT ] Ax . x [Wx

(7)

√ 1/(pLW +2) , the (2) Lewis-weight metric. For pLW = 4 ∨ log m and ΛLW = (1 + pLW 2 ) 2m normalized Lewis-weight metric [KV24] is defined as (pLW ) gLW (x) := Λ2LW AT Ax . x Wx

(3) John metric.

(8)

1 d Following Chen et al. [CDWY18], set κ = log2 2m d , αJ = 1 − κ , and βJ = 2m . α /2

J The John-weight vector ζx ∈ Rm Ax ) + βJ 1 for >0 is the unique positive solution of ζx = σ(Zx Zx := Diag ζx , as follows from the strictly convex formulation of Chen et al. [LS19, CDWY18, Eq. (12) and Lemma 3(a)]. With λJ = 4 (1 + κ)2 , the normalized John metric is

gJ (x) := λJ AT x Z x Ax .

6

(9)

3

Main results

We now present two complementary mixing frameworks. The first establishes acceptance control only on a high-probability region and uses s-conductance to obtain total-variation mixing without assumptions on second derivatives of the metric. The second adds LTSC and fourth-order bootstrap control to obtain pointwise acceptance, a spectral gap, and χ2 -contraction.

3.1

Mixing with acceptance control on a high-probability region

Our first framework uses s-conductance once acceptance is controlled on a high-probability region. Consequently, TV-mixing requires only the three conditions below, which involve at most first derivatives of the metric: SSC, ν̄-symmetry, and bounded mixed 23-trace. Theorem 1 (TV-mixing of the Dikin walk on a convex body). Let K ⊂ Rd be a full-dimensional convex body, let θ ∈ Rd , let g : int K → Sd++ be a continuously differentiable local metric, and let πθ be the exponential target. Suppose that, for some ν̄ ≥ 1 and a universal constant γ ≥ 0, (i) g is SSC (Definition 1); (ii) g is ν̄-symmetric (Definition 2); (iii) g has γ-bounded mixed 23-trace (Definition 3). √

2

(ν0 ∥πθ )) For any ε ∈ (0, 1/2) and initial distribution ν0 , define L := log e (1+ dν̄)(1+χ . For a proposal ε2 −3/2 radius r ≍ L , the lazy Dikin walk satisfies TV τmix (ε; ν0 , Te ) = O dν̄L3 log

2
1 ∨ χ2 (ν0 ∥ πθ )
e dν̄ log4 1 ∨ χ (ν0 ∥ πθ ) . =O 2 2 ε ε

TV . Our argument builds on the work of Laddha, Lee, and See (35) for the definition of τmix Vempala [LLV20], who introduced SSC and ν̄-symmetry and developed arguments based on proposal overlap and cross-ratio isoperimetry. Their claimed dν̄ bound, however, has a gap. Their equation (2.2) controls the ellipsoid-volume ratio but does not check whether the current point is included in the Dikin ellipsoid centered at the proposal. Our new ingredient is condition (iii) which controls acceptance on a high-probability region under the stationary measure. When g is a Hessian metric, condition (i) implies condition (iii) with γ = 2 (Remark 1). Also, when g is the Hessian metric of a self-concordant barrier, the inner inclusion in condition (ii) is automatic. Condition (ii) supplies the comparison between cross-ratio distance and local norms used in isoperimetry. Ape 2) plied to the Lee–Sidford, Lewis-weight, and John metrics, Theorem 1 yields the conjectured O(d mixing bound for sampling from uniform and exponential targets on polytopes (Corollary 2).

3.2

Mixing with pointwise acceptance control

Theorem 1 controls acceptance only on a high-probability region. The standard pointwise argument instead uses SSC, LTSC, and ASC to obtain transition overlap for nearby points as shown by Kook and Vempala [KV24] and Jiang and Chen [JC25]. Together with ν̄-symmetry, ordinary conductance then gives a χ2 -contraction factor exp (−Ω(N/(dν̄))) after N steps [Koo26]. e 1/4 ) scaling factor. This For the LS metric, Kook’s verification of ASC uses an additional O(d e 9/4 ) mixing-time bound [Koo26, Theorem 1.1 and §1.2]. factor also increases ν̄ and yields an O(d We remove this dimension-dependent factor by combining SSC and bounded mixed 23-trace with the new fourth-order condition below to derive ASC. 7

Why a bootstrap condition? For F (t) := hT g(x + th)h, Taylor’s formula reduces its variation along a proposal path (up to t ≲ d−1/2 ) to the initial cubic term F ′ (0) = Jxg [ξ ⊗3 ] and the integral √ of F ′′ (t) = Qgxt [ξt⊗4 ]. SSC and the bounded mixed 23-trace condition control F ′ (0) at scale d, so it remains to control F ′′ (t) √ at scale d. A direct uniform bound on F ′′ (t) is too crude and, for the LS metric, loses a factor of d [CDWY18, KV24, JC25]. The higher-order analysis in [Koo26] suggests the scaling |F (j) (0)| ≲ dj/2 for j ≥ 1. More precisely, extending the corresponding base-point through order k would yield a d2+1/(k+1) mixing bound; the paper carries this out for k = 3. Heuristically, if the base-point estimates held at every order, then the formal Taylor expansion would give 1 + |F (t) − F (0)| ≤ 1 +

X tj j≥1

j!

√

|F (j) (0)| ≤ eCt d .

Observe that this bound has the same form as the bound produced by a Grönwall-type inequality. Hence, it motives finding an auxiliary function whose growth can be controlled in terms of itself. We therefore introduce ωt for suitable bootstrapping. For a fixed δ, conditions (B1)–(B3) below should be read as follows: (B1) initializes ω0 = Oδ (1) on a feasible path of length Oδ (d−1/2 ); (B2) keeps ωt = Oδ (1) along this path by Grönwall’s inequality; and (B3) converts this control into |F ′′ (t)| = Oδ (d). Thus, the argument closes through self-consistent pathwise control rather than a worst-case bound on the full fourth-order tensor. Definition 6 (Fourth-order bootstrap control). A C 2 local metric g has fourth-order bootstrap control if there is a function ω : int K × Rd → [1, ∞) with the following property. For every δ ∈ (0, 1/2), there are constants rδ > 0, ηδ , bδ ≥ 0, and cδ ≥ 1 that depend only on δ and are uniform in the dimension and all other problem parameters. For x ∈ int K, let ξ ∼ N(0, Id ),

h = g(x)−1/2 ξ,

xt = x + th.

There is an event of probability at least 1 − δ on which the following hold: √ (B1) Feasibility and initial bound. The segment {xt : 0 ≤ t ≤ rδ / d} lies in int K. On this interval, set ξt = g(xt )1/2 h and ωt = ω(xt , h). Then t 7→ ωt is continuous and ω0 ≤ cδ ; √ (B2) Bootstrap control. For 0 ≤ t ≤ rδ / d, √ Z t ωs ds; ωt ≤ ω0 + ηδ d 0

(B3) Fourth-order dominance.

√ For 0 ≤ t ≤ rδ / d, |Qgxt [ξt⊗4 ]| ≤ bδ d ωt (see (3)).

Here, rδ is the path radius, ηδ controls the cumulative growth in condition (B2), bδ is the dominance coefficient in condition (B3), and cδ bounds the initial value ω0 . Lemma 6 formalizes this argument and shows that SSC, bounded mixed 23-trace, and fourthorder bootstrap control together establish ASC. For a scaled LS metric, our verification of this e 2 ) mixing-time bound in χ2 -divergence. criterion leads to an O(d Theorem 2 (χ2 -contraction of the Dikin walk on a convex body). Let K ⊂ Rd be a bounded, full-dimensional convex body, let θ ∈ Rd , let g : int K → Sd++ be a C 2 local metric, and let πθ be the exponential target. Suppose that, for some ν̄ ≥ 1 and a universal constant γ ≥ 0,

8

(i) g is SSC (Definition 1); (ii) g is ν̄-symmetric (Definition 2); (iii) g has γ-bounded mixed 23-trace (Definition 3); (iv) g is LTSC (Definition 4); (v) g has fourth-order bootstrap control (Definition 6). There exist universal constants r ∈ (0, 1/2] and c > 0 such that, for any initial distribution ν0 , the lazy Dikin walk with proposal radius r satisfies, for every integer N ≥ 0, cN
2 χ2 (ν0 Te N ∥ πθ ) ≤ exp − χ (ν0 ∥ πθ ) . dν̄ In particular, for any ε ∈ (0, 1/2), 1 ∨ χ2 (ν0 ∥ πθ )
χ2 . τmix (ε; ν0 , Te ) = O dν̄ log ε

3.3

Sampling from polytopes and truncated positive-semidefinite cones

We provide four consequences of the two frameworks. Corollary 1 specializes Theorem 1 to weighted Dikin metrics on polytopes. Corollary 2 specializes it to the Lee–Sidford, Lewis-weight, and John metrics on polytopes, while Corollary 3 applies Theorem 1 to a hybrid of the PSD barrier and the Lee–Sidford metric on bounded truncated PSD cones. Both corollaries give TV-mixing bounds for exponential targets. Corollary 4 applies Theorem 2 to obtain χ2 -contraction for a Lee–Sidford metric on polytopes. The required metric regularities are verified in §6. Total-variation mixing on polytopes. The next corollary gives sufficient conditions for a weighted Dikin metric on a polytope to satisfy the assumptions of Theorem 1. Corollary 1 (Dikin walk specialized to polytopes). Let K = {x ∈ Rd : Ax ≥ b} be a bounded, full-dimensional polytope, where A ∈ Rm×d has full column rank and no zero rows, and b ∈ Rm . m Consider a local metric of the form g(x) = AT x Wx Ax , where wx ∈ R>0 , Wx = Diag wx , and x 7→ wx 1/2 is continuously differentiable. Let Bx = Wx Ax , Σx = Diag σ(Bx ), and define Rx : Rd → Rm by Rx (z) :=

1 D log wx [g(x)−1/2 z] − Ax g(x)−1/2 z . 2

(10)

Suppose that there are C ∈ [0, 1] and ν̄ ≥ 1 such that, for every x ∈ int K, 1/2

(i) ∥Σx Rx ∥op ≤ C; −1 (ii) Dg (x, 1) ⊆ K, equivalently, aT x,i g(x) ax,i ≤ 1 for every i ∈ [m];

(iii) Tr Wx ≤ ν̄. Then, g is SSC, ν̄-symmetric, and has 2C-bounded mixed 23-trace. In particular, it has bounded mixed 23-trace, so Theorem 1 applies.

9

Condition (i) controls SSC and the mixed 23-trace bound in the following way: since g(x) = 1/2 BxT Bx and DBx [h] = Diag(Rx z)Bx for h = g(x)−1/2 z, the bound on ∥Σx Rx ∥op ensures that

g(x) varies slowly. By (6), condition (ii) is equivalent to the pointwise leverage-score bound 1/2 σi (Wx Ax ) ≤ wx,i for every i ∈ [m]. Lastly, Conditions (ii) and (iii) imply ν̄-symmetry. In §6.2, we verify these conditions for the Lee–Sidford metric gLS , the Lewis-weight metric gLW , and the John metric gJ , and Corollary 1 implies the following dimension-square TV-mixing bound. Corollary 2 (Dimension-square TV-mixing on polytopes). Let K = {x ∈ Rd : Ax ≥ b} be a bounded, full-dimensional polytope, where A ∈ Rm×d has full column rank and no zero rows. Let πθ ∝ exp(−θT x) IK (x) be an exponential target on K, and let g be any of gLS , gLW , or gJ , as defined above. The corresponding symmetry parameters satisfy  2  d log m , g = gLS , ν̄g ≲ d log2 m , g = gLW ,   d log2 em d , g = gJ . Given ε ∈ (0, 1/2) and an initial distribution ν0 , set Lg := log[d log(em)(1 + χ2 (ν0 ∥ πθ ))/ε2 ]. Then, for some proposal radius, the lazy Dikin walk with local metric g satisfies dTV (ν0 Te N , πθ ) ≤ ε after N = O dν̄g L3g log

1 ∨ χ2 (ν0 ∥ πθ )
ε2

steps .

Remark 2. For the LS metric, one can instead use a better choice of pLS = 2 ∨ log m d . In this 2 em case, the symmetry parameter is improved to ν̄ ≲ d log d . Total-variation mixing on truncated positive-semidefinite cones. Theorem 1 also applies to exponential targets on truncated positive-semidefinite cones. In §6.3, we verify its assumptions for a hybrid metric on the domain K := {X ∈ Sd : X ⪰ 0 , ⟨Ai , X⟩ ≥ bi for i ∈ [m]} . The ambient dimension is n := d(d + 1)/2. Since the Hessian metric of the positive-semidefinite barrier controls directions outside the span of the linear constraints, the number m of such cone 4 ) = O(n e 2 ) bound, which is straints need not be at least n. The corollary below gives an O(d dimension-square in the ambient dimension. Corollary 3 (Dimension-square TV-mixing on truncated PSD cones). Let A1 , . . . , Am , Θ ∈ Sd and b ∈ Rm , and suppose that K = {X ∈ Sd : X ⪰ 0, ⟨Ai , X⟩ ≥ bi for i ∈ [m]} is bounded and full-dimensional in Sd . Let πΘ ∝ exp(−⟨Θ, X⟩) IK (X) be the exponential target, gLS be the LS component defined in §6.3, ϕPSD (X) := − log det X, and set g := d∇2 ϕPSD +gLS . Given ε ∈ (0, 1/2) 2 and an initial distribution ν0 , set Lg := log dm (1∨χε2(ν0 ∥πΘ )) . Then, for a suitable proposal radius, the lazy Dikin walk with local metric g satisfies dTV (ν0 Te N , πΘ ) ≤ ε after N steps, where N = O d4 L3g log2 (em) log

1 ∨ χ2 (ν0 ∥ πΘ )
ε2

steps .

χ2 -contraction on polytopes. Finally, we apply Theorem 2 to an LS metric on a polytope. e 2 ) mixing-time bound §6.4 verifies fourth-order bootstrap control for this metric. The resulting O(d e 9/4 ) bound [Koo26]. improves the previous O(d

10

Corollary 4 (χ2 -contraction on polytopes with a scaled LS metric). Let K = {x ∈ Rd : Ax ≥ b} be bounded and full-dimensional, where A has full column rank and no zero rows. Set p = 2 (1 + log m) 1−2/p and λ = p/2, let Wx be the ℓp -Lewis-weight matrix of Ax , and define gb(x) := Sλ2 AT Ax with x Wx 20 S = C0 (1 + log m) for a sufficiently large universal constant C0 . There exist universal constants r ∈ (0, 1/2] and c > 0 such that, for every exponential target πθ and every initial distribution ν0 , the lazy Dikin walk with metric gb and proposal radius r satisfies cN
χ2 (ν0 Te N ∥ πθ ) ≤ exp − 2 2 χ2 (ν0 ∥ πθ ). Sλ d In particular, for every ε ∈ (0, 1/2), 1 ∨ χ2 (ν0 ∥ πθ )
χ2 τmix (ε; ν0 , Te ) = O d2 log22 (em) log . ε AI disclosure.

The authors used ChatGPT Pro 5.5 and 5.6 for the following purposes:

• to obtain a preliminary version of Corollary 2 for Lee–Sidford metric, including a proof of Lemma 4 which is the key to simplify the acceptance-rate control in Theorem 1; and • to develop Corollary 4 based on a ChatGPT 5.6 Pro session shared by Victor Reis (July 16). Both authors then generalized the preliminary Lee–Sidford Dikin-walk proofs into the two generic frameworks of Theorems 1 and 2 and clarified which components of the AI-generated proofs were novel. ChatGPT Pro was also used to identify errors in the proofs and exposition. On August 21, Matthew Zhang and Sinho Chewi informed us that Yiping Lu had posted a note on his academic webpage claiming a d2 result for the Lee–Sidford walk by resolving conjectures posed in [Koo26]. The result and its proof may overlap with our Corollary 4. On August 26, we became aware of a paper by Song and Zhang on arXiv that claims a d2 result for the Lee–Sidford walk and may also overlap with Corollary 4.

4

Proof of Theorem 1 via s-conductance

Unlike earlier work on the Dikin walk [KN12, CDWY18, LLV20, KV24, JC25], our proof leverages s-conductance, which requires (1) one-step coupling and (2) an isoperimetric inequality. In contrast to conductance, s-conductance allows us to ignore a (potentially) bad region where the algorithm suffers from slow mixing. However, previous s-conductance arguments in the analysis of constrained sampling [Lov99, LV07, CE26] have resulted in an undesirable polynomial dependence on the warmness parameter and inverse accuracy (i.e., poly(M/ε)). Previous work has attempted to establish one-step coupling for arbitrary interior points by analyzing the proposal distributions (i.e., H ∼ N (0, g(x)−1 )). In the present work, we enlarge the probability space from the proposal variable H to the pair (X, H) and work with a joint law µ defined on this augmented space such that its X-marginal and the conditional distribution H | X = x correspond to the stationary measure πθ and the Dikin proposal Px , respectively. We then define a region Ξ consisting of points from which the acceptance probability of a proposal exceeds a certain threshold. Under a suitable choice of this threshold, we can establish one-step coupling within Ξ under regularity conditions on the local metric. A key technical challenge is to show that Ξ has high probability under πθ (Lemma 2). This is where the lifted joint measure µ comes in. We bound πθ (Ξc ) in terms of a “bad” event under the joint measure µ, whose probability can in turn be controlled via a moment estimate for the negative log proposal-density ratio under 11

SSC and bounded mixed 23-trace (Lemmas 4 and 5). This technique previously appeared in analyses of MALA and HMC by Wu, Schmidler, and Chen [WSC22] and Chen, Gatmiry, and Jiang [CGJ23]. The second ingredient, an isoperimetric inequality derived from ν̄-symmetry, is standard. It follows from self-concordance, the local-norm comparison implied by ν̄-symmetry, and cross-ratio isoperimetry. Combining the one-step coupling and the isoperimetric inequality, we can bound the s-conductance as in Lemma 3, following a standard conductance argument. Finally, using the standard conductance-to-mixing result of Lovász–Simonovits (Proposition 1), we prove Theorem 1.

4.1

Acceptance control and one-step coupling

Recall that Px and Tx are the proposal and one-step transition distributions from x. We first use the following standard SSC proposal-overlap estimate [LLV20, KV24, JC25]. The proof is standard and recalled in §B.1. Lemma 1 (Proposal overlap). Suppose that g is SSC and 0 < r ≤ 1/2. For any x, y ∈ int K such η that ∥x − y∥g(x) ≤ 10 = 10r√d , we have dTV (Px , Py ) ≤ 1/4. Next, we control the probability loss from rejections when passing from proposal overlap to transition overlap. Let (X, H) ∼ µ have the joint distribution defined by
X ∼ πθ , H | X = x ∼ N 0, g(x)−1 . (11) Under µ, define the feasible-proposal and half-space events by E := {(x, h) : x + ηh ∈ int K} ,

Dθ := {(x, h) : ⟨θ, h⟩ ≤ 0} .

For a > 0, define the bad-proposal event by  px+ηh (x) Bθ,a := E c ∪ (x, h) ∈ Dθ ∩ E : < e−a . px (x + ηh)

(12)

Thus, a bad proposal is either infeasible or feasible and downhill with log-proposal ratio below −a. The next lemma defines a (high-probability) set Ξ on which bad proposals have conditional probability at most τ . It bounds πθ (Ξc ) and combines this control with Lemma 1 to obtain transition overlap between nearby points in Ξ. We defer its proof to §4.4. Lemma 2 (Acceptance control and transition overlap). Fix a proposal radius r > 0 and set η = √ r/ d. Let g be SSC and have γ-bounded mixed 23-trace on int K for some γ ≥ 0. Fix a > 0 and τ ∈ (0, 1/8). For the bad event Bθ,a in (12), define 
Ξ := x ∈ int K : PH∼N(0,g(x)−1 ) (x, H) ∈ Bθ,a ≤ τ . Then, for every k ≥ 2, ea 2r(2 + γ) k 3/2
k µ(E c ) + . (13) τ a τ If r ≤ 1/2, then all x, y ∈ Ξ with ∥x − y∥g(x) ≤ η/10 satisfy
1 dTV (Tx , Ty ) ≤ 1 − e−a − 2τ . (14) 4 a0 1 For a concrete choice of parameters, let k ≥ 2 and set a0 = log 67 , τ0 = 16 , and r = 4(2+γ) k3/2 (which ensures r < 1/2). Substituting these choices into Lemma 2 gives 19 πθ (Ξc ) ≤ k + 16µ(E c ) , 2 (15) 3 η 1 − dTV (Tx , Ty ) ≥ whenever x, y ∈ Ξ and ∥x − y∥g(x) ≤ . 28 10 πθ (Ξc ) ≤

12

4.2

From one-step coupling to mixing

We use two standard geometric facts from Dikin-walk conductance arguments [LLV20, KV24, JC25]. For distinct x, y ∈ int K, let p and q be the endpoints of the chord through x and y, ordered as p, x, y, q. The cross-ratio distance is dK (x, y) :=

∥x − y∥ ∥p − q∥ . ∥p − x∥ ∥q − y∥

For nonempty A, B ⊆ K, define dK (A, B) := inf x∈A, y∈B dK (x, y). Fact 1 (Log-concave cross-ratio isoperimetry, [LV07, Theorem 2.5]). For any log-concave distribution π on K and every measurable partition K = S1 ∪· S2 ∪· S3 with S1 , S2 ̸= ∅, π(S3 ) ≥ dK (S1 , S2 ) π(S1 ) π(S2 ) . Fact 2 (Cross-ratio/local-norm comparison, [LLV20, Lemma 2.3]). Suppose that a local metric g on int K is ν̄-symmetric. Then, for all distinct x, y ∈ int K, 1 dK (x, y) ≥ √ min{∥x − y∥g(x) , ∥x − y∥g(y) } . ν̄ Using this isoperimetric inequality, we turn transition overlap into an s-conductance bound. Recall that for a πθ -reversible Markov kernel T, its ergodic flow and s-conductance are defined by Z QT (A, B) := Tx (B) πθ (dx) , A

Φs (T) :=

QT (A, Ac ) , πθ (A)∈(s,1/2] πθ (A) − s inf

for 0 ≤ s <

1 . 2

e for the lazy version of T. Note that Φ0 is the ordinary conductance. We write T The next standard lemma turns one-step coupling in Ξ into an s-conductance bound [Lov99, LLV20, KV24, JC25]. The proof is deferred to §B.2. Lemma 3 (Transition overlap to s-conductance). Let g be an SC local metric on int K. Suppose that ζ ≥ 0, ∆ ∈ (0, 1], δ ∈ [0, 1), ν̄ > 0, and Ξ ⊆ int K satisfy πθ (Ξc ) ≤ ζ , dTV (Tx , Ty ) ≤ δ whenever x, y ∈ Ξ and ∥x − y∥g(x) ≤ ∆ , √ ∥x − y∥g(x) ∧ ∥x − y∥g(y) ≤ ν̄ dK (x, y) for distinct x, y ∈ Ξ . ∆ 1 Set ϑ := 1 ∧ 2√ . Then, for every s ∈ [ 8ζ ϑ , 2 ), ν̄

e ≥ (1 − δ) ϑ . Φs (T) 64 We then use conductance to bound the mixing time. Proposition 1 (Mixing from conductance [LS88, LS93]). The following holds for any k ∈ Z≥0 :
e k ∥ πθ ) ≤ χ2 (ν0 ∥ πθ ) exp −kΦ0 (T) e 2 , χ2 (ν0 T r (16) 2 e 2
p 1 k e , πθ ) ≤ sχ2 (ν0 ∥ πθ ) + χ (ν0 ∥ πθ ) exp − kΦs (T) , dTV (ν0 T 0<s< . s 2 2 2 The first estimate is the standard L Cheeger bound in the normalization of Lovász and Simonovits [LS93, Lemma 1.7 and Corollary 1.8]; see also Lawler and Sokal [LS88]. The second follows from the Lovász–Simonovits s-conductance bound [LS93, Corollary 1.6 and Remark 1] by Cauchy–Schwarz, since πθ is atom-free. 13

4.3

Proof of Theorem 1

Proof of Theorem 1. Choose an integer ℓ and a radius r satisfying √
dν̄ 1 ∨ χ2 (ν0 ∥ πθ ) ℓ ≍ log ≍ L, r ≍ ℓ−3/2 , ε2

r η := √ , d

where the implicit constants in the choices of ℓ and r are taken sufficiently large and sufficiently small, respectively, so that ℓ ≥ 2 and r ≤ 1/2. The inclusion Dg (x, 1) ⊆ K follows from ν̄-symmetry. Conditionally on X = x, write H = g(x)−1/2 ξ with ξ ∼ N(0, Id ). Gaussian concentration bounds the infeasibility probability as √
d
c µ(E ) ≤ P ∥ξ∥ ≥ ≤ exp −Ω(d/r2 ) . r Take the small implicit constant in the choice of r so that r ≤ a0 /[4(2 + γ) ℓ3/2 ]. Let Ξ be the region in Lemma 2 corresponding to a = a0 and τ = τ0 , and use the acceptance and overlap bounds with k = ℓ. Together with the infeasibility estimate above, we have
πθ (Ξc ) ≤ exp −Ω(ℓ) , dTV (Tx , Ty ) ≤ 25/28

whenever x, y ∈ Ξ and ∥x − y∥g(x) ≤ η/10 .

η ∆ Set ∆ := 10 and ϑ := 1 ∧ 2√ ≍ √rdν̄ . By ν̄-symmetry and Fact 2, for all distinct x, y ∈ int K, ν̄

∥x − y∥g(x) ∧ ∥x − y∥g(y) ≤

√ ν̄ dK (x, y) .

Increasing the implicit constant in the choice of ℓ, if necessary, ensures that ζ := πθ (Ξc ) ≤

ε2 ϑ
. 32 1 + χ2 (ν0 ∥ πθ )

2

For s := 4 (1+χ2ε(ν0 ∥π )) , the bound on ζ ensures that s ≥ 8ζ/ϑ. Hence, Lemma 3 with δ = 25/28 θ yields Φs (Te ) ≳ ϑ. Substituting this bound into Proposition 1 shows that the lazy Dikin walk has TV-distance at most ε after O ϑ−2 log

1 ∨ χ2 (ν0 ∥ πθ )
dν̄ 1 ∨ χ2 (ν0 ∥ πθ )
= O 2 log 2 ε r ε2

steps .

The claim follows from r−2 ≍ ℓ3 ≍ L3 .

4.4

Proof of Lemma 2

We prove the two conclusions separately. To bound πθ (Ξc ), we separate infeasible proposals and reduce the feasible bad-proposal event to an initial derivative moment. To prove transition overlap, we lower-bound the proposal mass accepted from both points on a common downhill half-space. We first represent the negative log proposal-density ratio along the proposal path. For t ∈ [0, η] and every (x, h) such that x + th ∈ int K, define 1 1 Θt (x, h) := − log det g(x + th) + hT g(x + th)h , 2 2

14

Θ̇t (x, h) := ∂t Θt (x, h) .

By the proposal density in (1), on E, log

px+ηh (x) = Θ0 (x, h) − Θη (x, h) . px (x + ηh)

(17)

Consequently, under µ, Bθ,a ∩ E = {(x, h) ∈ Dθ ∩ E : Θη (x, h) − Θ0 (x, h) > a} . For k ≥ 1, define the Lk -norm of the derivative at time t = 0 by  
1/k Rk := ∥Θ̇0 ∥Lk (µ) = Eµ |Θ̇0 (X, H)|k . We now bound the derivative moment at each time t by Rk and then control the tail probability. Lemma 4 (Tail bound of the bad event). Fix a > 0, η > 0, k ≥ 1, and let g be C 1 on int K. Then,
ηRk
k . µ(Bθ,a ∩ E) = µ {(x, h) ∈ Dθ ∩ E : Θη (x, h) − Θ0 (x, h) ≥ a} ≤ ea a Proof. For t ∈ [0, η], define Et := {(x, h) ∈ int K × Rd : x + th ∈ int K}. Note that Eη = E. Recall that the joint law (X, H) ∼ µ in (11) has the following density on int K × Rd : dµ(x, h) =

1 exp −⟨θ, x⟩ − Θ0 (x, h) dxdh . d/2 Zθ (2π)

For t ∈ [0, η], define a measure on Dθ ∩ Et by de µt (x, h) := e−{Θt (x,h)−Θ0 (x,h)} dµ(x, h) , and set it to zero outside this set. For every nonnegative measurable φ, the change of variables y = x + th yields Z φ(x + th, h) de µt (x, h) Z
1 = φ(y, h) Iint K (y) Iint K (y − th) I{⟨θ,h⟩≤0} (h) exp −⟨θ, y⟩ + t⟨θ, h⟩ − Θ0 (y, h) dydh d/2 Z (2π) Zθ ≤ φ(y, h) dµ(y, h) , where the inequality follows from t⟨θ, h⟩ ≤ 0 on Dθ . Since Θ̇t (x, h) = Θ̇0 (x + th, h), choosing φ(y, h) = |Θ̇0 (y, h)|k yields Z k

Θ̇t (x, h) de µt (x, h) ≤ Rkk .

For µ-almost every (x, h) ∈ E, convexity of K implies (x, h) ∈ Et for every t ∈ [0, η]. We integrate the absolute derivative only over times when the increment is at most a. For (x, h) ∈ Dθ ∩ E, define Z η Ja (x, h) := Θ̇t (x, h) I{Θt (x,h)−Θ0 (x,h)≤a} dt , 0

and set Ja (x, h) = 0 otherwise. For such (x, h), suppose that Θη (x, h) − Θ0 (x, h) ≥ a, and define the first hitting time by t⋆ := inf{t ∈ [0, η] : Θt (x, h) − Θ0 (x, h) ≥ a}. Continuity gives Θt⋆ (x, h) − Θ0 (x, h) = a and Θt (x, h) − Θ0 (x, h) ≤ a for 0 ≤ t ≤ t⋆ . Therefore, Z t⋆ a = Θt⋆ (x, h) − Θ0 (x, h) = Θ̇t (x, h) dt ≤ Ja (x, h) . 0

15

On Dθ ∩ E, dµ = eΘt −Θ0 de µt . At the times included in Ja , this factor is at most ea . By Jensen’s inequality, Z ηZ k Θ̇t IDθ ∩E (x, h) I{Θt (x,h)−Θ0 (x,h)≤a} dµdt Eµ [Jak ] ≤ η k−1 Z0 η Z k k−1 =η Θ̇t IDθ ∩E (x, h) I{Θt (x,h)−Θ0 (x,h)≤a} eΘt −Θ0 de µt dt 0 Z ηZ k ≤ ea η k−1 Θ̇t de µt dt ≤ ea η k Rkk . 0

Applying Markov’s inequality, we have
ηRk
k µ {(x, h) ∈ Dθ ∩ E : Θη (x, h) − Θ0 (x, h) ≥ a} ≤ µ(Ja ≥ a) ≤ a−k Eµ [Jak ] ≤ ea , a which completes the proof. It remains to bound Rk . Whenever x + th ∈ int K, differentiation along the path yields
 1 Θ̇t (x, h) = Dg(x + th)[h, h, h] − Tr g(x + th)−1 Dg(x + th)[h] . 2

(18)

Lemma 5 (Rk -moment). Let g be SSC and have γ-bounded mixed 23-trace on int K for some γ ≥ 0. Then, for every k ≥ 2, √ √ √ √ Rk ≤ 6 (k − 1)3/2 d + γ kd ≤ 2k 3/2 d (2 + γ) . (19) Proof. Fix x ∈ int K, write g = g(x) and J = Jx , and let H ∼ N(0, g −1 ). For ξ := g 1/2 H ∼ N(0, Id ), the derivative identity (18) becomes 2Θ̇0 (x, H) = J [ξ, ξ, ξ] − ⟨Tr12 J , ξ⟩ .

(20)

Using Jijk = Jjik , define the symmetrization of J by J ijk := 13 (Jijk + Jikj + Jjki ). It satisfies 3 Tr12 J = Tr12 J + 2 Tr23 J .

(21)

Define the third-order Hermite polynomial X HJ (ξ) := J ijℓ (ξi ξj ξℓ − δij ξℓ − δiℓ ξj − δjℓ ξi ) , ijℓ

where δij = 1 when i = j and 0 otherwise. Using J [ξ, ξ, ξ] = J [ξ, ξ, ξ], we have (21)

J [ξ, ξ, ξ] = HJ (ξ) + 3 ⟨Tr12 J , ξ⟩ = HJ (ξ) + ⟨Tr12 J , ξ⟩ + 2 ⟨Tr23 J , ξ⟩ . Substituting this decomposition into (20) yields 2Θ̇0 (x, H) = HJ (ξ) + 2 ⟨Tr23 J , ξ⟩ .

(22)

We bound HJ (ξ) using SSC and ⟨Tr23 J , ξ⟩ using the mixed 23-trace assumption. Since symmetrization is an orthogonal projection in the Frobenius inner product, ∥J ∥F ≤ ∥J ∥F . By SSC, ∥J ∥{12}{3} ≤ 2. Applying this bound to each coordinate direction and summing, we obtain ∥J ∥2F =

d X d X ℓ=1 i,j=1

16

2 Jijℓ ≤ 4d .

  By a direct Gaussian moment calculation, E HJ (ξ)2 = 3! ∥J ∥2F . By Gaussian hypercontractivity [Jan97, Theorem 5.8], √ √  
1/k
1/2 √ E |HJ (ξ)|k ≤ (k − 1)3/2 E[HJ (ξ)2 ] = 6 (k − 1)3/2 ∥J ∥F ≤ 2 6 (k − 1)3/2 d . √ √ Applying the same bound to the linear term and using k − 1 ≤ k, we obtain √  
1/k √ E |⟨Tr23 J , ξ⟩|k ≤ k ∥Tr23 J ∥ ≤ γ kd . Applying the triangle inequality to (22) in Lk , we obtain, for every x ∈ int K, √ √  
1/k √ EN(0,g(x)−1 ) |Θ̇0 (x, H)|k ≤ 6 (k − 1)3/2 d + γ kd . Integrating the conditional k-th-moment bound over X ∼ πθ proves the first inequality in (19). The second follows from k ≥ 2. Proof of Lemma 2. We first bound πθ (Ξc ). By Lemmas 4 and 5, µ(Bθ,a ) ≤ ea

ηRk
k 2r(2 + γ) k 3/2
k + µ(E c ) ≤ ea + µ(E c ) . a a

By Markov’s inequality and the tower property,
Eπ [Pµ (Bθ,a | X)] µ(Bθ,a ) πθ (Ξc ) = PX∼πθ Pµ (Bθ,a | X) > τ ≤ θ = τ τ a 3/2 c
e 2r(2 + γ)k µ(E ) k ≤ + . τ a τ We next prove transition overlap. For u ∈ Ξ, let Bθ,a (u) := {z ∈ Rd : (u, z−u η ) ∈ Bθ,a } be the set of bad proposal endpoints from u. Then, Pu [Bθ,a (u)] = PN(0,g(u)−1 ) [(u, H) ∈ Bθ,a ] ≤ τ . Fix distinct x, y ∈ Ξ satisfying ∥x − y∥g(x) ≤ η/10. By Lemma 1, dTV (Px , Py ) ≤ 1/4. Since the proposal-overlap bound is symmetric, we may relabel x and y so that ⟨θ, x⟩ ≤ ⟨θ, y⟩. For Dx− := {z ∈ Rd : ⟨θ, z⟩ ≤ ⟨θ, x⟩}, note that ⟨θ, z⟩ ≤ ⟨θ, x⟩ ≤ ⟨θ, y⟩ for every z ∈ Dx− . By Gaussian symmetry, Px (Dx− ) = 1/2. Therefore, Z 1 min{px (z), py (z)} dz ≥ Px (Dx− ) − dTV (Px , Py ) ≥ . 4 Dx− R Let qu (z) := pu (z) αg (u, z) be the density of accepted moves from u. Then, Tu (A) ≥ A qu (z) dz for every measurable A ⊆ Rd . For u ∈ {x, y} and z ∈ Dx− \ Bθ,a (u), the proposal is feasible and downhill from u, and pz (u)/pu (z) ≥ e−a . In the acceptance ratio (2), the target-density factor is at least one for a downhill proposal. Hence αg (u, z) ≥ e−a and qu (z) ≥ e−a pu (z). It follows that Z 1 − dTV (Tx , Ty ) ≥ min{qx (z), qy (z)} dz Dx− \[Bθ,a (x)∪Bθ,a (y)]

≥ e−a

Z

≥ e−a

1 − 2τ . 4

Dx−

 min{px (z), py (z)} dz − Px Bθ,a (x) − Py Bθ,a (y)

Rearranging gives the claimed transition-overlap bound. 17

5

Proof of Theorem 2 via ordinary conductance

In the previous section, we constructed a high-probability region Ξ on which every point has high acceptance probability and established one-step coupling among nearby points in this region. We now prove Theorem 2, showing that high acceptance probability and one-step coupling can be extended throughout int K under additional regularity assumptions on the local metric g. The proof consists of three steps. First, Lemma 6 uses SSC, bounded mixed 23-trace, and fourth-order bootstrap control to establish ASC. Second, proposal overlap from SSC combines with LTSC and ASC to establish transition overlap for nearby points throughout int K. Third, ν̄-symmetry and cross-ratio isoperimetry convert this overlap into an ordinary conductance lower bound (not just s-conductance). Proposition 1 then yields χ2 -contraction. The second and third steps follow standard Dikin-walk arguments [KV24, JC25]. The additional step is Lemma 6, which uses SSC and bounded mixed 23-trace to control the initial cubic term and fourth-order bootstrap control to bound the integral remainder in Taylor’s formula along a Gaussian proposal path.

5.1

A fourth-order bootstrap criterion for ASC and one-step coupling

We first control the initial derivative and the integral remainder along a Gaussian proposal path. Lemma 6 (Fourth-order bootstrap criterion for ASC). If g is SSC, has bounded mixed 23-trace, and has fourth-order bootstrap control, then g is ASC. Proof. Fix ρ ∈ (0, 1/2) and x ∈ int K. We verify the event in Definition 5 with a radius that is uniform in x and d. Let ξ ∼ N(0, Id ), and set h = g(x)−1/2 ξ and xt = x + th. Whenever xt ∈ int K, set ξt = g(xt )1/2 h and F (t) = hT g(xt )h. For every feasible η ≥ 0 and Y = x + ηh, |∥Y − x∥2g(Y ) − ∥Y − x∥2g(x) | = η 2 |F (η) − F (0)| .

(23)

Thus, it suffices to control the variation of F along the proposal path. On every feasible segment, differentiation yields F ′ (t) = Jxgt [ξt⊗3 ] and F ′′ (t) = Qgxt [ξt⊗4 ]. Hence, for every η ≥ 0 such that {xt : 0 ≤ t ≤ η} ⊆ int K, Taylor’s formula yields Z η (η − t) Qgxt [ξt⊗4 ] dt . (24) F (η) − F (0) = η Jxg [ξ ⊗3 ] + 0

We bound the initial derivative and the integral remainder separately. Write J = Jxg . The Gaussian decomposition from the proof of Lemma 5 expresses the initial derivative as F ′ (0) = HJ (ξ) + ⟨Tr12 J + 2 Tr23 J , ξ⟩ , where J and HJ are, respectively, the symmetrization and the third-order Hermite polynomial defined there. SSC controls the Hermite term, Remark 1 controls Tr12 J , and bounded mixed 23-trace controls Tr23 J . Applying the moment bounds from that proof with k = ⌈2 + log(2/ρ)⌉ and then Markov’s inequality shows that, with probability at least 1 − ρ/2, √ 2
3/2 |F ′ (0)| ≤ M3,ρ d for M3,ρ ≍ 1 + log . ρ For the integral remainder, apply Definition 6 with δ = ρ/2. On its event, which√has probability at least 1 − ρ/2, feasibility in condition (B1) keeps the path in int K up to rρ/2 / d. The initial bound in condition (B1), the integral inequality in condition (B2), and Grönwall’s inequality imply √ √ ωt ≤ ω0 exp(ηρ/2 d t) ≤ cρ/2 exp(ηρ/2 rρ/2 ) for 0 ≤ t ≤ rρ/2 / d . 18

Combining this estimate with the fourth-order bound in condition (B3), we obtain |Qgxt [ξt⊗4 ]| ≤ M4,ρ/2 d

for M4,ρ/2 := bρ/2 cρ/2 exp(ηρ/2 rρ/2 ) .

The intersection of the two events has probability at least 1 − ρ. Define 
1/2 ρ 2ρ rρ⋆ := min rρ/2 , , . M3,ρ 1 ∨ M4,ρ/2 The three terms in this minimum respectively ensure path feasibility, an initial-derivative contribution at most ρ, and an integral remainder at most ρ in Taylor’s formula (24). For any 0 < r ≤ rρ⋆ , √ set η := r/ d and Y = x + ηh. Then Y ∼ N(x, r2 g(x)−1 /d). On the intersection of the two events, r ≤ rρ/2 , so condition (B1) ensures that the segment {xt : 0 ≤ t ≤ η} is feasible. We may therefore apply Taylor’s formula (24); combining the preceding bounds with (23) yields M4,ρ/2 r2
2ρr2 ≤ . 2 d These feasibility and increment bounds hold with probability at least 1 − ρ. Moreover, M3,ρ and the parameters in Definition 6 at δ = ρ/2 depend only on ρ and universal constants. Hence so does rρ⋆ . Since x was arbitrary, taking rρASC = rρ⋆ proves the claim. |∥Y − x∥2g(Y ) − ∥Y − x∥2g(x) | = η 2 |F (η) − F (0)| ≤ η 2 M3,ρ r +

We next combine proposal overlap with LTSC and ASC to obtain transition overlap for nearby points throughout int K. The following result essentially appeared in previous work [KV24, JC25], and we defer its streamlined proof to §B.3. Lemma 7 (Pointwise transition overlap). Let g : int K → Sd++ be SSC, LTSC, and ASC. Set 1 ρ⋆ := 64 and r0 := 1 ∧ rρASC , where rρASC > 0 is a radius given by Definition 5. There are universal ⋆ ⋆ constants c0 ∈ (0, 1/2] and δ0 ∈ (0, 1) such that for every exponential target πθ , the Dikin kernel with proposal radius r = c0 r0 satisfies η c0 r0 dTV (Tx , Ty ) ≤ δ0 whenever ∥x − y∥g(x) ≤ = √ . 10 10 d

5.2

Proof of Theorem 2

We now derive ordinary conductance and χ2 -contraction from pointwise transition overlap. Proof of Theorem 2. By Lemma 6, SSC, bounded mixed 23-trace, and fourth-order bootstrap control imply ASC; at ρ⋆ = 1/64, the corresponding ASC radius is universal. Together with SSC and LTSC, Lemma 7 then yields a proposal radius r ∈ (0, 1/2] and a universal constant δ0 ∈ (0, 1). Then, dTV (Tx , Ty ) ≤ δ0 whenever ∥x − y∥g(x) ≤ ∆ := 10r√d ≍ √1d . The kernel T is πθ -reversible, SSC implies self-concordance, and πθ (int K) = 1. Moreover, ν̄√ symmetry and Fact 2 imply ∥x − y∥g(x) ∧ ∥x − y∥g(y) ≤ ν̄ dK (x, y) for all distinct x, y ∈ int K. Since ∆ ≤ 1, the preceding bounds verify the hypotheses of Lemma 3 with T = T , Ξ = int K, ζ = s = 0, δ = δ0 , and the displayed ∆. Therefore, r 1 Φ0 (Te ) ≳ √ ≍ √ . dν̄ dν̄ Substituting this conductance bound into Proposition 1 yields, for a universal constant c > 0, χ2 (ν0 Te N ∥ πθ ) ≤ exp −

cN
2 χ (ν0 ∥ πθ ) . dν̄

Solving this inequality for N gives the stated χ2 mixing-time bound and completes the proof. 19

6

Applications

This section proves the four corollaries stated in §3.3. In §6.1, we prove Corollary 1 by reducing the assumptions of Theorem 1 to three conditions for general weighted Dikin metrics on polytopes. §6.2 verifies these conditions for the Lee–Sidford, Lewis-weight, and John metrics and proves Corollary 2. §6.3 verifies the conditions of Theorem 1 for a hybrid metric combining the Hessian of the positive-semidefinite barrier with an LS component and proves Corollary 3. Finally, §6.4 verifies the conditions in Theorem 2 for a scaled LS metric and proves Corollary 4.

6.1

Mixing framework for weighted Dikin walks on polytopes

The proof has two steps. The row-derivative operator bound in condition (i) yields SSC and bounded mixed 23-trace, while the ellipsoid-containment and weight-trace bounds in conditions (ii) and (iii) yield ν̄-symmetry. Proof of Corollary 1. Fix x ∈ int K and suppress the dependence on x when it is clear from context. SSC and mixed 23-trace. For B = W 1/2 Ax , set U := Bg −1/2 and P := U U T . Then, U T U = Id , P is an orthogonal projection, and Σ = Diag P . For h = g −1/2 z, differentiating B = W 1/2 Ax gives DB[h] = Diag(Rz) B . Since g = B T B, differentiation yields the key identity g −1/2 Dg[g −1/2 z] g −1/2 = 2U T Diag(Rz)U .

(25)

Here, ◦ denotes the Hadamard product and P ◦2 := P ◦ P . As Σ − P ◦2 = P ◦ (Im − P ) ⪰ 0, 1 −1/2 ∥g Dg[g −1/2 z] g −1/2 ∥2F = (Rz)T P ◦2 (Rz) ≤ ∥Σ1/2 Rz∥2 ≤ C 2 ∥z∥2 4

for z ∈ Rd .

Thus, ∥Jxg ∥{12}{3} ≤ 2C ≤ 2, so g is SSC. T For the mixed trace, let uT i and ri be the i-th rows of U and R, and set qi := ⟨ui , ri ⟩. Taking the mixed 23-trace in the factorization (25) yields Tr23 Jxg = 2U T q. Since ∥ui ∥2 = Pii = Σii , ∥Tr23 Jxg ∥ ≤ 2 ∥q∥ ≤ 2

m X

Σii ∥ri ∥2

1/2

= 2 ∥Σ1/2 R∥F

i=1

√ √ ≤ 2 d ∥Σ1/2 R∥op ≤ 2C d .

(26)

The SSC and mixed-trace bounds verify conditions (i) and (iii) of Theorem 1. ν̄-symmetry. The ellipsoid Dg (x, 1) is symmetric about x, so condition (ii) of the corollary implies Dg (x, 1) ⊆ K ∩ (2x − K). For the outer inclusion, if x + h ∈ K ∩ (2x − K), then ∥Ax h∥∞ ≤ 1. Condition (iii) therefore gives ∥h∥2g(x) =

m X

2 wx,i (aT x,i h) ≤ Tr Wx ≤ ν̄ .

i=1

√ Hence, K ∩ (2x − K) ⊆ Dg (x, ν̄), so g is ν̄-symmetric. The claim follows from Theorem 1.

20

6.2

Lee–Sidford, Lewis-weight, and John metrics

We now verify (i)–(iii) of Corollary 1 for the Lee–Sidford, Lewis-weight, and John metrics in Lemmas 8–10. Each proof checks the row-derivative operator bound in (i), the equivalent leveragescore form of (ii), and the weight-trace bound in (iii), in this order. The normalizing factors in these metrics are chosen so that the bound in (i) is at most one. Lemma 8 (Lee–Sidford metric). The Lee–Sidford metric gLS in (7) satisfies (i)–(iii) of Corollary 1 with C = 1 and ν̄ = ν̄LS := Λ2LS m2/pLS d1−2/pLS ≲ d log2 m. cx := Λ2 (Wx(p) )1−2/p . Fix x ∈ int K and abbreviate Proof. Set p := pLS and Λ := ΛLS , and write W (p) (p) g := gLS (x), W := Wx , and w := wx . Set β := 21 − p1 and U := ΛW β Ax g −1/2 . Note that P U T U = Id , i wi = d, and 0 < wi ≤ 1. Let Rx be the operator in (10) for the effective weight cx . matrix W For (i), the derivative identities of Lee and Sidford [LS19, Lemmas 24 and 31] provide a symmetric matrix N such that 0 ⪯ N ⪯ pI and β D log wx(p) [h] = −βW −1/2 N W 1/2 Ax h

for every direction h .

cx )[h] = β D log wx(p) [h] and 1 + βp = p/2 = Λ, for When p = 2, we take N = 0. Since 21 D log(diag W h = g −1/2 z, 1 W 1/2 Rx z = − (I + βN ) W 1/p U z . Λ Hence, 1 ∥W 1/2 Rx ∥op ≤ ∥I + βN ∥op ∥W 1/p ∥op ∥U ∥op ≤ 1 . (27) Λ cx1/2 Ax ) = w shows that the leverage-score matrix in Corollary 1 is W . Thus, The identity σ(W inequality (27) proves condition (i) with C = 1. 1−2/p cx )i . For (iii), For (ii), the same identity, Λ ≥ 1, and 0 < wi ≤ 1 give wi ≤ Λ2 wi = (diag W P Hölder’s inequality and i wi = d give cx = Λ2 Tr W

m X

1−2/p

wi

≤ Λ2 m2/p d1−2/p = ν̄LS .

i=1

The choice of pLS gives

dp2LS m
2/pLS ≲ d log2 m . 4 d Therefore, conditions (i)–(iii) hold with C = 1 and the claimed ν̄. ν̄LS =

We next consider the Lewis-weight metric rather than the powers appearing in the LS metric. Lemma 9 (Lewis-weight metric). The Lewis-weight metric gLW in (8) satisfies conditions (i)–(iii) of Corollary 1 with C = 1 and ν̄ = ν̄LW := Λ2LW d ≲ d log2 m. (p

)

(p

)

Proof. Write wxLW := wx LW and WxLW := Wx LW . Set ρLW := 2m2/(pLW +2) , so ΛLW = (1 + √ pLW /2) ρLW . Fix x and write W := WxLW and g0 := AT x W Ax . For (i), Lee and Sidford [LS19, Lemmas 24, 26, and 31] give a symmetric matrix N satisfying D log wxLW [h] = −W −1/2 N W 1/2 Ax h ,

0 ⪯ N ⪯ pLW Im , 21

max i

σi (W 1/2 Ax ) ≤ ρLW . LW wx,i

(28)

−1/2

Let U := W 1/2 Ax g0

and Σ := Diag σ(W 1/2 Ax ). The row-derivative operator for g0 is 1
R0 = −W −1/2 Im + N U . 2

By (28) and U T U = Id , ∥Σ1/2 R0 ∥op ≤

√

ρLW 1 +

pLW
= ΛLW . 2

Scaling g0 by Λ2LW leaves Σ unchanged and divides the row-derivative operator by ΛLW . Thus, (i) holds with C = 1. For (ii),
LW LW σi (Λ2LW W )1/2 Ax = σi (W 1/2 Ax ) ≤ ρLW wx,i ≤ Λ2LW wx,i . P LW For (iii), i wx,i = d gives Tr(Λ2LW W ) = Λ2LW d = ν̄LW . Our choice of pLW gives m2/(pLW +2) = O(1) and ΛLW = O(log m), so ν̄LW ≲ d log2 m. Thus, (i)–(iii) hold with C = 1 and the claimed ν̄. We finally turn to the John metric. Lemma 10 (John metric). The John metric gJ in (9) satisfies (i)–(iii) of Corollary 1 with C = 1 and ν̄ = ν̄J := 6(1 + κ)2 d ≲ d log2 em d . Proof. Fix x and suppress its subscript. Write J := AT x ZAx , so that gJ (x) = λJ J. Let αJ −1 T αJ /2 P := Z αJ /2 Ax (AT , x Z Ax ) Ax Z

Λ := Diag(diag P ) − P ◦2 ,

and set K := (Z − αJ Λ)−1 Λ. For (i), after translating to our sign convention, the calculus formula of Chen et al. [CDWY18, Lemma 9(a)] shows that x 7→ ζx is continuously differentiable and gives the first identity below. Chen et al. [CDWY18, Lemma 10], with c1 = 0 and c2 = 1, give the second: D log ζx [h] = −2KAx h , K T ZK ⪯ κ2 Z . (29) Hence, the row-derivative operator for the base metric J is R0 = −(Im + K)Ax J −1/2 . Let Σ0 := Diag σ(Z 1/2 Ax ). Chen et al. [CDWY18, Lemma 3(d)] prove that Σ0 ⪯ 4Z. Combining this bound with (29) yields 1/2

∥Σ0 R0 ∥op ≤ 2(1 + κ) ∥Z 1/2 Ax J −1/2 ∥op = 2(1 + κ) . 1/2

Scaling J by λJ = 4(1 + κ)2 divides R0 by λJ and leaves Σ0 unchanged, so (i) holds with C = 1. For (ii),
σi (λJ Z)1/2 Ax = σi (Z 1/2 Ax ) ≤ 4ζx,i ≤ λJ ζx,i . P P For (iii), the identity i σi = d gives m i=1 ζx,i = d + mβJ = 3d/2. Therefore, Tr(λJ Z) = 6(1 + κ)2 d = ν̄J . The definition of κ gives the stated bound. Thus, (i)–(iii) hold with C = 1 and the claimed ν̄. Proof of Corollary 2. Lemmas 8–10 verify the conditions of Corollary 1 with C = 1 and the displayed values of ν̄g . Thus, the corollary gives the universal p mixed-23-trace constant γ = 2. For all three metrics, ν̄g ≲ d log2 (em), and hence 1 + dν̄g ≲ d log(em). It follows that the quantity L in Theorem 1 satisfies L ≲ Lg . Substitution into Theorem 1 gives the stated bound.

22

6.3

Proof of Corollary 3: truncated PSD cones

Let n := d(d + 1)/2 and define A : Sd → Rm by (AH)i := ⟨Ai , H⟩. After discarding zero constraint −1 rows, assume that ρ := rank A ≥ 1. For X ∈ int K, let SX := Diag(AX − b) and AX := SX A. Set p := 2 ∨ log

m , ρ

ΛLS :=

p , 2

β :=

1 1 − . 2 p

Choose a fixed linear isometry V : Rρ → Sd with range(V ) = (ker A)⊥ . Then, AX V has full column rank ρ for every X ∈ int K. Let WX be the ℓp -Lewis-weight matrix of AX V . The resulting LS component is positive semidefinite on Sd and has the fixed kernel ker A. We use the hybrid metric g(X) := gPSD (X) + gLS (X), where gPSD (X)[H1 , H2 ] := d ∇2 ϕPSD (X)[H1 , H2 ] = d Tr(X −1 H1 X −1 H2 ) , 1−2/p

gLS (X)[H1 , H2 ] := Λ2LS ⟨AX H1 , WX

AX H2 ⟩ .

Applying the proof of Lemma 8 to AX V on this fixed ρ-dimensional subspace shows that gLS is continuously differentiable, satisfies the SSC derivative bound on (ker A)⊥ , and satisfies the symmetry estimate for the linear-constraint domain with ν̄LS := Λ2LS m2/p ρ1−2/p ≲ ρ log2

em ≤ n log2 (em) . ρ

Kook and Vempala prove that gPSD is SSC and d2 -symmetric [KV24, Corollary E.24 and Lemma E.21]. Since symmetry parameters add [KV24, Lemma D.11], the hybrid metric g is O(n log2 m)-symmetric. We next verify SSC of the sum and the mixed 23-trace bound. Fix X, let g1 := gPSD and g2 := gLS , and write W := WX and wLS := diag WX . We suppress the dependence on X, so g, gi , and Dgi below denote g(X), gi (X), and Dgi (X), respectively. Define 1/2 Ti := gi g −1/2 for i = 1, 2. We first verify SSC of the sum. For z ∈ Rn , set h := g −1/2 z and     T1 M1 0 †/2 †/2 Mi := gi Dgi [h] gi , T := , M := , T2 0 M2 where † denotes the Moore–Penrose inverse. Here, g1 is positive definite, while g2 has the fixed kernel ker A. Since T1T T1 + T2T T2 = I, we have T T T = I. The SSC bounds for g1 and for g2 on its range give ∥Mi ∥F ≤ 2 ∥h∥gi = 2 ∥Ti z∥. Consequently, SSC of g follows from ∥g −1/2 Dg[h] g −1/2 ∥F = ∥T T M T ∥F ≤ ∥M ∥F ≤ 2 (∥T1 z∥2 + ∥T2 z∥2 )1/2 = 2 ∥z∥ . −1/2

For the mixed-trace calculation, define J1 [u, v, w] := Dg1 [g1

−1/2

w][g1

−1/2

u, g1

v]. Observe that

J g [u, v, w] = Dg1 [g −1/2 w][g −1/2 u, g −1/2 v] + Dg2 [g −1/2 w][g −1/2 u, g −1/2 v] = J1 [T1 u, T1 v, T1 w] + Dg2 [g −1/2 w][g −1/2 u, g −1/2 v] . Let ti be the mixed-23 trace of each term. We now bound the norms of t1 and t2 , respectively. For t1 , let u be a unit vector and let {ei } be an orthonormal basis. Since J1 is fully symmetric, ⟨t1 , u⟩ =

n X i=1

J1 [T1 u, T1 ei , T1 ei ] =

n X

J1 [T1 ei , T1 ei , T1 u] = ⟨J1 [ ·, ·, T1 u], T1 T1T ⟩ .

i=1

23

Since T1T T1 + T2T T2 = I, we have T1T T1 ⪯ I and ∥T1 ∥op ≤ 1. Using SSC of g1 , √ √ ∥t1 ∥ ≤ ∥J1 [ ·, ·, T1 u]∥F ∥T1 T1T ∥F ≤ 2 ∥T1 u∥ n ≤ 2 n . For t2 , let B = ΛLS W β AX , Ū = Bg −1/2 , and R̄z := β D log wLS [g −1/2 z] − AX g −1/2 z. Repeating the factorization in (25), we obtain g −1/2 Dg2 [g −1/2 z] g −1/2 = 2Ū T Diag(R̄z)Ū . Applying the mixed-trace calculation used in (26) with Σ̄ := Diag[diag(Ū Ū T )], we obtain √ ∥t2 ∥ ≤ 2 n ∥Σ̄1/2 R̄∥op . †/2

Now, define U = Bg2 . Then, Ū = U T2 , so Ū Ū T = U T2 T2T U T ⪯ U U T . This implies Σ̄ ⪯ Σ = Diag[diag(U U T )]. On the range of g2 , we have R̄ = R2 T2 , where R2 is the row-derivative operator †/2

†/2

R2 z := β D log wLS [g2 z] − AX g2 z . Hence, applying the operator bound (27) to R2 yields √ √ √ ∥t2 ∥ ≤ 2 n ∥Σ1/2 R̄∥op ≤ 2 n sup ∥T2 u∥ ≤ 2 n . u:∥u∥=1

√ Therefore, ∥Tr23 J g ∥ ≤ 4 n, so g has 4-bounded mixed 23-trace. Together with the SSC and symmetry bounds above, this verifies the three assumptions of Theorem 1. Moreover,

log

e(1 +

√

nν̄ ≲ n2 log2 m ≲ d4 log2 m ,
nν̄) 1 + χ2 (ν0 ∥ πΘ ) ≲ Lg . ε2

Substitution into Theorem 1 proves Corollary 3.

6.4

χ2 -contraction for the Lee–Sidford metric

We prove Corollary 4 by verifying the five conditions of Theorem 2 for the scaled LS metric gb. The main new estimate is ∥Nt′ ∥op ≤ 6p2 (ωt − 1) in Lemma 12. Substitution into the standard path estimates establishes bootstrap control (B2) and fourth-order dominance (B3). Set 2 α 1 1 p p := pLS = 2 (1 + log m) , α := 1 − , β := = − , λ := ΛLS = . p 2 2 p 2 (p)

(p)

Throughout this subsection, write wx := wx and Wx := Wx , and define the baseline metric α g(x) := AT x W x Ax .

We use g for the main calculations, λ2 g = gLS as the normalized LS metric, and gb = Sλ2 g as the final metric in Corollary 4. Lemma 8 verifies conditions (i)–(iii) for gLS with C = 1 and ν̄ = λ2 m2/p d1−2/p ≤ eλ2 d. Corollary 1 therefore shows that gLS is SSC, has bounded mixed 23-trace, and has symmetry parameter at most eλ2 d. Convexity of x 7→ log det g(x) [LLV20, Lemma 4.3] and identity (5) show that g is LTSC. Since λ ≥ 1, gLS is also LTSC. Scaling gLS up by S preserves SSC, bounded mixed 23-trace, and LTSC, and multiplies its symmetry parameter by S. Hence, gb satisfies (i)–(iv), with symmetry parameter ν̄ ≤ eSλ2 d. It remains to verify condition (v), first for g and then for the scaled gb. We first record a few Lewis-weight identities. 24

Fact 3 (Lewis-weight derivatives [LS19, Definition 20 and Lemma 24, 31, 47]). For x ∈ int K, set β Px := Wxβ Ax g(x)−1 AT x Wx ,

Λ̄x := I − Wx−1/2 Px◦2 Wx−1/2 , Nx := 2Λ̄x (I − αΛ̄x )−1 . Then, Px is the orthogonal projector onto col(Wxβ Ax ), Nx is symmetric, and the maps x 7→ Px and x 7→ Nx are smooth. Moreover, for every h ∈ Rd , 0 ⪯ Λ̄x ⪯ I, 0 ⪯ Nx ⪯ pI,

diag Px = wx , D log wx [h] = −Wx−1/2 Nx Wx1/2 Ax h .

(30)

Fix x ∈ int K. Conditions (B1)–(B3) are invariant under invertible affine changes of coordinates, so we may assume x = 0 and g(0) = Id . Let h ∼ N(0, Id ) and xt = th. Set ξt := g(xt )1/2 h and F (t) := hT g(xt )h. Along the path, write At = Axt , wt = wxt , Wt = Wxt , Pt := Pxt , Nt = Nxt , and ℓt := log wt , and set 1/2

ιt := At h ,

vt := Wt

1/2

ιt = Wt

At h ,

−1/2

qt := Wt

(Wtβ ιt )◦2 .

Fact 4 (Fourth-order identity for the LS metric [Koo26, §3.1]). For every t such that xt ∈ int K, F ′′ (t) = D2 g(xt )[h, h][h, h] = Qgxt [ξt⊗4 ] X
α 4 =6 wt,i ιt,i + 2α ⟨Nt vt , qt ◦ ιt ⟩ − 2β (qt′ )T Nt vt + qtT Nt vt′ + qtT Nt′ vt .

(31)

i

The bottleneck. [Koo26, Lemma 3.3 and 3.4] already control the four terms (at the required scale) in decomposition (31) that do not contain Nt′ . For the remaining term, the direct estimate √ e 3/2 ), whereas condition (B3) requires an e d) in [Koo26] gives only |qtT Nt′ vt | = O(d ∥Nt′ ∥op = O( O(d)-bound times the certificate introduced below. Motivated by this, we introduce the following certificate. For y ∈ int K and h ∈ Rd , define Dy (h) := Diag(β D log wy [h] − Ay h) . The identity D(Wyβ Ay )[h] = Dy (h) Wyβ Ay expresses this derivative as row scaling by Dy (h). Since Py is the orthogonal projector onto col(Wyβ Ay ) and determines Ny through Fact 3, define ωLS (y, h) := 1 + ∥Dy (h) Py ∥op . Why this certificate? Along the path, let Dt := Dxt (h) and ωt := ωLS (xt , h). Differentiating its orthogonal projector Pt = σ(Wtβ At ) gives Pt′ = (I − Pt ) Dt Pt + Pt Dt (I − Pt ) . Hence, ∥Pt′ ∥op ≤ 2 ∥Dt Pt ∥op = 2 (ωt − 1). Passing from Pt′ to Nt′ is the key nontrivial step, and Lemma 12 proves ∥Nt′ ∥op ≤ 6p2 (ωt − 1). Combined with the remaining path estimates, this bound controls qtT Nt′ vt and hence F ′′ (t) at the scale required for (B3). The same bound controls the contribution of Nt′ to Dt′ and yields a differential inequality for Dt Pt , which √ gives (B2) upon integration. Thus, ωt can address a previous bottleneck without the extra d loss of the direct estimate. Lemma 13 makes these two consequences precise. In Lemma 11, we streamline the argument of Lemma 3.3 in [Koo26], tracking the dependence on p, m, δ explicitly. It verifies (B1) and records the required path estimates, with its proof deferred to §C. The proofs of Lemmas 12 and 13 are deferred to the end of the subsection. 1/2 for δ ∈ (0, 1/2). Below, set κδ := p2 (1 + log 8m δ ) 25

Lemma 11 (Lewis-weight path estimates). Fix δ ∈ (0, 1/2) and write κ = κδ . There are universal √ constants c, C > 0 and an event Eδ of probability at least 1 − δ such that, for 0 ≤ t ≤ cκ −4 / d, xt ∈ int K , √ ∥h∥g(xt ) ≤ Cκ d , √ ∥ℓ′t ∥∞ + ∥Dt ∥op ≤ Cκ 2 d , √ ∥Nt vt ∥ + ∥qt ∥ ≤ Cκ 2 d , √ ∥qt′ ∥ ≤ Cκ 4 d .

ω0 ≤ Cκ , ∥ιt ∥∞ ≤ Cκ , √ ∥vt ∥ ≤ Cκ d , √ ∥vt′ ∥ ≤ Cκ 3 d ,

Moreover, t 7→ ωt is continuous on this segment. Lemma 12 (Derivative bound for Nt ). For every t for which xt ∈ int K, ∥Nt′ ∥op ≤ 6p2 (ωt − 1). Lemma 13 (Bootstrap control and fourth-order dominance). Fix δ ∈ (0, 1/2) and write √ κ = κδ . There exists C ≍ 1 such that, on the event Eδ in Lemma 11, for every 0 ≤ t ≤ cκ −4 / d, √ Z t ωs ds , |Qgxt [ξt⊗4 ]| ≤ Cκ 6 d ωt . ωt ≤ ω0 + Cκ 4 d 0

Proof of Corollary 4. Fix δ ∈ (0, 1/2). Since the base point x is arbitrary, Lemma 11 verifies condition (B1), including continuity, and Lemma 13 verifies (B2)–(B3) on the same event Eδ . e We now check the effects of O(1)-scaling of gLS on the problem parameters. Intuitively, this should not affect the final complexity, but we provide the scaling details for completeness. After adjusting universal constants, baseline parameters for (g, ωLS ) are rδ = cκδ−4 ,

bδ = Cκδ6 ,

ηδ = Cκδ4 ,

cδ = Cκδ .

Set S := C0 (1 + log m)20 , L := Sλ2 , and gb := Lg, where C0 is a sufficiently large universal constant. Fix once and for all δ⋆ = 1/32, set κ⋆ := κδ⋆ , and define √
ω bLS (x, b h) := 1 + κ⋆−1 ωLS (x, L b h) − 1 . As δ⋆ is fixed, ω bLS does not depend on the running value of δ. The corresponding parameters are √ ηδ cδ − 1 bbδ = κ⋆ bδ , ηbδ = √ , b cδ = 1 + rbδ = L rδ , . (32) L κ⋆ L To verify this scaling rule, fix x ∈ int K and ξ ∼ N(0, Id ), and set h = g(x)−1/2 ξ and b h = gb(x)−1/2 ξ = L−1/2 h. Write ξt := g(x + th)1/2 h, ξbt := gb(x + tb h)1/2b h.

ωt := ωLS (x + th, h), ω bt := ω bLS (x + tb h, b h),

√ Since x + tb h = x + (t/ L)h,

ω bt = 1 + κ⋆−1 (ωt/√L − 1),

Qgb

√ [ξb⊗4 ] = L−1 Qg [ξ ⊗4√ ]. x+(t/ L)h t/ L x+tb h t

√ √ The same event Eδ gives feasibility and continuity for 0 ≤ t ≤ L rδ / d, and ω b0 ≤ 1 + (cδ − 1)/κ⋆ ; hence condition (B1) holds. On this interval, ωs/√L ≤ κ⋆ ω bs . Applying the baseline conditions (B2)– (B3), using the preceding identities for ω bt and Qgb, and changing variables in condition (B2), yields Z t Z t ηδ √ ηδ √ ω bt ≤ ω b0 + √ d ωs/√L ds ≤ ω b0 + √ d ω bs ds, κ⋆ L L 0 0 26

bδ κ⋆ bδ [ξbt⊗4 ]| ≤ d ωt/√L ≤ dω bt . b x+th L L

|Qgb

The displayed inequalities verify conditions (B2) and (B3), thereby establishing the scaling rule (32). By the definition of κδ and the choice δ⋆ = 1/32, r 1 κδ ≤ 1 + log . (33) κ⋆ δ Moreover, κ⋆8 ≲ (1 + log m)20 , so increasing C0 if necessary ensures S ≥ Cκ⋆8 . Since λ ≥ 1, we have L ≥ S ≥ Cκ⋆8 . Substituting rδ = cκδ−4 , ηδ = Cκδ4 , bδ = Cκδ6 , and cδ = Cκδ into (32), the comparison in (33) shows that rbδ is bounded below by a positive constant depending only on δ, while ηbδ , bbδ , and b cδ are bounded above by constants depending only on δ. Decreasing rbδ to its lower bound and increasing the other three parameters to their upper bounds shows that gb has fourthorder bootstrap control in the sense of Definition 6. Thus, gb satisfies all conditions of Theorem 2, with symmetry parameter ν̄ ≤ eSλ2 d. The theorem therefore yields cN
χ2 (ν0 Te N ∥ πθ ) ≤ exp − 2 2 χ2 (ν0 ∥ πθ ) . Sλ d Finally, λ = 1 + log m, so Sλ2 = C0 (1 + log m)22 as claimed. Deferred proofs of Lemmas 12 and 13. Proof of Lemma 12. Fix t. Along the path, write Ps = Pxs , Λ̄s = Λ̄xs , and Ns = Nxs . At s = t, suppress subscripts and write P = Pt , D = Dt , W = Wt , w = wt , Λ̄ = Λ̄t , N = Nt , and ω = ωt . Then, ∥DP ∥op = ω − 1. We first reduce the claim to a bound on Λ̄′ . Set Rs = (I − αΛ̄s )−1 and write R = Rt . Since 0 ⪯ Λ̄ ⪯ I, we have ∥R∥op ≤ p/2. Moreover, R′ = αRΛ̄′ R and I + αΛ̄R = R. Differentiating N = 2Λ̄R 2 therefore gives N ′ = 2RΛ̄′ R and ∥N ′ ∥op ≤ p2 ∥Λ̄′ ∥op . Thus, it suffices to prove ∥Λ̄′ ∥op ≤ 12(ω − 1). To control Λ̄′ , define the following linear map Ψs : Rm×m → Rm , where the domain is equipped with the Frobenius norm. A direct calculation using Ps2 = Ps also gives Ψs X := Ws−1/2 diag(Ps XPs ) ,

−1/2 ◦2 Ψs ΨT Ps Ws−1/2 , s = Ws

Λ̄s = I − Ψs ΨT s .

d At s = t, write Ψ = Ψt and Ψ′ = ds Ψs s=t . Since 0 ⪯ Λ̄ ⪯ I, we have ∥Ψ∥op ≤ 1, and hence ′ ′ ∥Λ̄ ∥op ≤ 2 ∥Ψ ∥op . It remains to prove ∥Ψ′ ∥op ≤ 6 (ω − 1). w′ Let us define Γ := 12 W −1 W ′ = Diag( 2wii ). Differentiating Ψs at s = t gives

Ψ′ X = W −1/2 diag(P ′ XP + P XP ′ − ΓP XP ) . For Bs := Wsβ As , differentiating Ps = Bs (BsT Bs )−1 BsT using Bs′ = Ds Bs gives Ps′ = (I − Ps )Ds Ps + Ps Ds (I − Ps )

∥P ′ ∥op ≤ 2 ∥DP ∥op = 2 (ω − 1) .

Using w = diag P with the formula for P ′ , observe that (P DP )ii wi′ = Dii − . 2wi wi Since wi = Pii = ∥P ei ∥2 , the quotient (P DP )ii /wi is bounded by ∥P DP ∥op . Consequently, ∥Γ − D∥op ≤ ∥P DP ∥op ≤ ω − 1 ,

∥ΓP ∥op ≤ ∥DP ∥op + ∥(Γ − D)P ∥op ≤ 2 (ω − 1) . 27

(34)

For any M, X ∈ Rm×m , rowwise Cauchy–Schwarz with Pii = wi gives ∥W −1/2 diag(M XP )∥ ≤ ∥M X∥F ,

∥W −1/2 diag(P XM T )∥ ≤ ∥XM T ∥F .

Applying these inequalities with M = P ′ and M = ΓP yields ∥Ψ′ X∥ ≤ (2 ∥P ′ ∥op + ∥ΓP ∥op ) ∥X∥F ≤ 6 (ω − 1)∥X∥F . Combining the bounds on Λ̄′ and Ψ′ proves ∥Nt′ ∥op ≤

p2 ∥Λ̄′ ∥op ≤ p2 ∥Ψ′ ∥op ≤ 6p2 (ωt − 1) , 2

which completes the proof. √ Proof of Lemma 13. Work on Eδ for 0 ≤ t ≤ cκ −4 / d. Lemma 12, together with p2 ≤ κ and ωt = 1 + ∥Dt Pt ∥op ≥ 1, gives ∥Nt′ ∥op ≤ Cκ (ωt − 1) ≤ Cκωt throughout the interval. We first prove bootstrap control by bounding ∥Dt′ Pt ∥op and ∥Dt Pt′ ∥op . Write zt = βℓ′t − ιt , so −1/2 ′ Nt vt . Hence, that Dt = Diag zt . Fact 3 and direct differentiation give ι′t = −ι◦2 t and ℓt = −Wt zt′ = − For y, r ∈ Rm , the identity −1/2

∥Diag(Wt

β ′ ◦2 −1/2 ′ −1/2 (ℓ ) − βWt Nt vt − βWt Nt vt′ + ι◦2 t . 2 t

2 j (Pt )ij = (Pt )ii = wt,i and the inequality ∥·∥op ≤ ∥·∥F imply

P

y) Pt ∥op ≤ ∥y∥ ,

∥Diag(r◦2 ) Pt ∥op ≤ ∥r∥∞ ∥(Diag r) Pt ∥op .

We use the first inequality to bound the two middle terms in zt′ and the second one to handle the rest. Using (Diag ℓ′t ) Pt = β −1 (Dt Pt + (Diag ιt )Pt ) (which follows from ℓ′t = β −1 (zt + ιt )), together with Lemmas 11 and 12, we obtain √ √ √ ∥Dt′ Pt ∥op ≤ Cκ 4 d ωt + Cκ d ∥Nt′ ∥op ≤ Cκ 4 d ωt . √ √ Also,√by (34) and Lemma 11, ∥Dt Pt′ ∥op ≤ Cκ 2 d (ωt − 1) ≤ Cκ 4 d ωt . Hence, ∥(Dt Pt )′ ∥op ≤ Cκ 4 d ωt . By integrating this derivative bound, √ Z t ωt ≤ ω0 + ∥Dt Pt − D0 P0 ∥op ≤ ω0 + Cκ 4 d ωs ds . 0

For fourth-order dominance, Lemmas 11 and 12 give X α 4 wt,i ιt,i ≤ ∥ιt ∥2∞ ∥h∥2g(xt ) ≤ Cκ 4 d , i

|⟨Nt vt , qt ◦ ιt ⟩| ≤ Cκ 5 d , |(qt′ )T Nt vt | + |qtT Nt vt′ | ≤ Cκ 6 d , |qtT Nt′ vt | ≤ Cκ 3 d ∥Nt′ ∥op ≤ Cκ 4 dωt . Therefore, by Fact 4, |Qgxt [ξt⊗4 ]| = |F ′′ (t)| ≤ Cκ 6 dωt . Acknowledgements. The authors thank the FIM–Institute for Mathematical Research at ETH Zürich for supporting the conference “Scalable MCMC Sampling”, where this project was initiated. The authors also thank Santosh Vempala and Minhui Jiang for discussions at an early stage of the project. YK is supported in part by NSF Awards CCF-2504995, CCF-2236669, and CCF-2504994. YK thanks Victor Reis for sharing a preliminary proof of Corollary 4 found by ChatGPT 5.6 Pro based on [Koo26]. 28

References [CDWY18] Yuansi Chen, Raaz Dwivedi, Martin J. Wainwright, and Bin Yu. Fast MCMC sampling algorithms on polytopes. Journal of Machine Learning Research, 19(55):1–86, 2018. [CE26] Yuansi Chen and Ronen Eldan. Hit-and-Run mixing via localization schemes. Discrete & Computational Geometry, 75(3):747–794, 2026. [CGJ23] Yuansi Chen, Khashayar Gatmiry, and Minhui Jiang. When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm? arXiv preprint arXiv:2304.04724, 2023. [CP15] Michael B. Cohen and Richard Peng. lp row sampling by Lewis weights. In Symposium on Theory of Computing, STOC ’15, pages 183–192, New York, NY, USA, 2015. ACM. [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. [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. [Dik67] Iliya Iosiphovich Dikin. Iterative solution of problems of linear and quadratic programming. In Soviet Math. Dokl., volume 8, pages 674–675, 1967. [Jan97] Svante Janson. Gaussian Hilbert Spaces. Cambridge University Press, 1 edition, June 1997. [JC25] Minhui Jiang and Yuansi Chen. Regularized Dikin walks for sampling truncated logconcave measures, mixed isoperimetry and beyond worst-case analysis. In Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 3017–3078. PMLR, 30 Jun–04 Jul 2025. [JLLV26] He Jia, Aditi Laddha, Yin Tat Lee, and Santosh S. Vempala. Reducing isotropy and volume to KLS: faster rounding and volume algorithms. Journal of the ACM, 73(2), April 2026. [Kar84] Narendra Karmarkar. A new polynomial-time algorithm for linear programming. In Symposium on Theory of Computing, STOC ’84, pages 302–311. ACM Press, 1984. [Kla23] Bo’az Klartag. Logarithmic bounds for isoperimetry and slices of convex sets. Ars Inveniendi Analytica, (4):1–17, 2023. [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. [KN12] Ravi Kannan and Hariharan Narayanan. Random walks on polytopes and an affine interior point method for linear programming. Mathematics of Operations Research, 37(1):1–20, 2012. [Koo26] Yunbum Kook. Beyond the d2.5 -mixing bound for Dikin walks on polytopes. arXiv preprint arXiv:2607.13943, 2026.

29

[KV24] Yunbum Kook and Santosh S. Vempala. Gaussian cooling and Dikin walks: the interiorpoint method for logconcave sampling. In Conference on Learning Theory, volume 247, pages 3137–3240. PMLR, 2024. [KV25a] 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. [KV25b] Yunbum Kook and Santosh S. Vempala. Zeroth-order logconcave sampling. arXiv preprint arXiv:2507.18021, 2025. [KV26a] Yunbum Kook and Santosh S. Vempala. Spectral gaps of Hit-and-Run and Coordinate Hit-and-Run. arXiv preprint arXiv:2608.16878, 2026. [KV26b] 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. [LLV20] Aditi Laddha, Yin Tat Lee, and Santosh S. Vempala. Strong self-concordance and sampling. In Symposium on Theory of Computing, pages 1212–1222. ACM, June 2020. [Lov90] László Lovász. How to compute the volume? biläumstagung, pages 138–151, 1990.

Jber. d. Dt. Math.-Verein, Ju-

[Lov99] László Lovász. Hit-and-Run mixes fast. Mathematical Programming, 86(3):443–461, 1999. [LS88] Gregory F. Lawler and Alan D. Sokal. Bounds on the L2 spectrum for Markov chains and Markov processes: A generalization of Cheeger’s inequality. Transactions of the American Mathematical Society, 309(2):557–580, 1988. [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. √ [LS19] Yin Tat Lee and Aaron Sidford. Solving linear programs with rank linear system solves. arXiv preprint arXiv:1910.08033, 2019. [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. [Nar16] Hariharan Narayanan. Randomized interior point methods for sampling and optimization. The Annals of Applied Probability, 26(1):597–641, 2016.

30

[NN94] Yurii Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms in convex programming. Society for Industrial and Applied Mathematics (SIAM), January 1994. [SV16] Sushant Sachdeva and Nisheeth K. Vishnoi. The mixing time of the Dikin walk in a polytope—a simple proof. Operations Research Letters, 44(5):630–634, 2016. [Vai96] Pravin M. Vaidya. A new algorithm for minimizing convex functions over convex sets. Mathematical Programming, 73(3, Ser. A):291–341, 1996. [WSC22] Keru Wu, Scott Schmidler, and Yuansi Chen. Minimax mixing time of the metropolisadjusted Langevin algorithm for log-concave sampling. Journal of Machine Learning Research, 23(270):1–63, 2022.

A

Deferred preliminaries

Notation. For k ∈ N, let [k] := {1, . . . , k}, and write a ∨ b and a ∧ b for max{a, b} and min{a, b}. We use ⟨u, v⟩ = uT v for the Euclidean inner product of vectors and ⟨U, V ⟩ = Tr(U T V ) for the Frobenius inner product of matrices. The norm ∥u∥ is Euclidean, while ∥U ∥op and ∥U ∥F are the operator and Frobenius norms. We write Ik and 1 for the identity matrix and all-ones vector, with dimensions omitted when clear. We write N(µ, Σ) for a Gaussian distribution with mean µ and covariance Σ. The spaces of symmetric, positive-semidefinite, and positive-definite k × k matrices are Sk , Sk+ , and Sk++ . We write U ⪯ V when V − U is positive semidefinite and col U for the column space of U . For a vector v and a square matrix U , Diag v is the diagonal matrix with diagonal v, while diag U is the diagonal vector of U . Vector inequalities and scalar functions applied to vectors are interpreted entrywise. Markov chains, mixing, and warm starts. We use standard Markov-chain notation; see, for example, Jiang and Chen [JC25, §1.1]. We take int K as the state space. Let T be a Markov transition kernel on int K, and write Tx := T(x, ·). Its action on a probability measure µ is Z Tx (E) µ(dx) , E ∈ B(int K) . (µT)(E) := int K

Thus, ν0 TN is the law after N steps from an initial distribution ν0 , and a probability measure π is stationary if πT = π. For a kernel with stationary distribution π and ε > 0, define  TV τmix (ε; ν0 , T) := inf N ∈ Z≥0 : dTV (ν0 TN , π) ≤ ε , (35)  2 χ τmix (ε; ν0 , T) := inf N ∈ Z≥0 : χ2 (ν0 TN ∥ π) ≤ ε . (36) e := (I + T)/2, where I is the identity kernel. For M ≥ 1, the initialization The lazy version of T is T ν0 is M -warm with respect to π if ν0 (E) ≤ M π(E) for every K). Equivalently, ν0 ≪ π R E ∈ B(int 0 2 and dν0 /dπ ≤ M almost surely. Note that 1 + χ2 (ν0 ∥ π) = int K ( dν ) dπ ≤ M. dπ

B

Deferred proofs for Sections 4 and 5

B.1

Proof of Lemma 1

The proposal-overlap argument uses only strong self-concordance. We use the following consequence of SSC [LLV20, Lemma 1.2]. 31

Fact 5. If g is SSC on int K, then, for any x, y ∈ int K with ∥x − y∥g(x) < 1, ∥g(x)−1/2 (g(y) − g(x)) g(x)−1/2 ∥F ≤

2∥x − y∥g(x) . (1 − ∥x − y∥g(x) )2

Proof of Lemma 1. Let δ := ∥x − y∥g(x) and M := g(x)−1/2 g(y)g(x)−1/2 . The matrix M is symmetric positive definite; let λ1 , . . . , λd be its eigenvalues. Since δ ≤ η/10 ≤ 1/20, Fact 5 implies ∥M − Id ∥F ≤

2δ 9 9 1 ≤ δ≤ < . 2 (1 − δ) 4 80 8

Hence, all eigenvalues of M satisfy λi ∈ [7/8, 9/8]. Using the Gaussian density (1) directly, Z py (z) 2 KL(Py ∥ Px ) = 2 py (z) log dz px (z) Z Z 1 1 det g(y) 2 + ∥z − x∥g(x) py (z) dz − 2 ∥z − y∥2g(y) py (z) dz . = log det g(x) η 2 η The relevant Gaussian moment identities are Z
∥z − x∥2g(x) py (z) dz = η 2 Tr g(x)g(y)−1 + ∥y − x∥2g(x) , Z ∥z − y∥2g(y) py (z) dz = η 2 d . Substituting these identities, we obtain 2

∥y − x∥g(x)
det g(y) + Tr g(x)g(y)−1 − d + det g(x) η2

2 KL(Py ∥ Px ) = log =

=

d X

log λi +

i=1 d X

d X δ2 (λ−1 − 1) + i η2 i=1

(λ−1 i − 1 + log λi ) +

i=1

δ2 . η2

Using λ−1 − 1 + log λ ≤ (λ − 1)2 on [7/8, 9/8] and δ/η ≤ 1/10, we conclude that d

KL(Py ∥ Px ) ≤

1 X δ2  1 1 1
1 + < . (λi − 1)2 + 2 < 2 η 2 64 100 64 i=1

By Pinsker’s inequality, r dTV (Px , Py ) ≤

1 1 1 KL(Py ∥ Px ) < √ < , 2 4 8 2

which completes the proof.

32

B.2

Proof of the conductance bound from transition overlap

The following is the standard local-norm comparison for a self-concordant local metric [LLV20, Lemma 1.1]. For Hessian metrics, see also Nesterov and Nemirovskii [NN94, Theorem 2.1.1]. Lemma 14 (Local-norm comparison under self-concordance). Let g be a self-concordant local metric on int K, and let x, y ∈ int K. If h := y − x satisfies ∥h∥g(x) < 1, then ∥h∥g(y) ≤

∥h∥g(x) . 1 − ∥h∥g(x)

Proof. The claim is immediate when h = 0. Otherwise, set xt := x + th and ϕ(t) := ∥h∥g(xt ) . By self-concordance of g, Dg(xt )[h][h, h] ϕ′ (t) = ≤ ϕ(t)2 . 2ϕ(t) Hence, (1/ϕ)′ (t) ≥ −1. Integrating over [0, 1], we obtain 1 1 ≥ − 1, ϕ(1) ϕ(0) which is equivalent to the claimed inequality. Proof of Lemma 3. Set a := (1 − δ)/2. Fix a measurable set A such that s < πθ (A) ≤ 1/2, and consider the partition A1 := {x ∈ A ∩ Ξ : Tx (Ac ) < a} , A2 := {y ∈ Ac ∩ Ξ : Ty (A) < a} , A3 := K \ (A1 ∪ A2 ) . For any x ∈ A1 and y ∈ A2 , the definitions imply Tx (A) > 1 − a and Ty (A) < a. Hence, dTV (Tx , Ty ) ≥ Tx (A) − Ty (A) > 1 − 2a = δ . The transition-overlap hypothesis implies that ∥x − y∥g(x) > ∆. We claim that ∥x − y∥g(y) ≥ ∆/2. Otherwise, Lemma 14, applied with base point y, would force a contradiction: ∥x − y∥g(x) ≤

∥x − y∥g(y) ∆/2 < ≤ ∆. 1 − ∥x − y∥g(y) 1 − ∆/2

If A1 and A2 are nonempty, the assumed cross-ratio comparison implies ∆ dK (A1 , A2 ) ≥ √ ≥ ϑ . 2 ν̄ Suppose πθ (A1 ) ≤ πθ (A)/2. Since s ≥ 8ζ/ϑ and ϑ ≤ 1, we have ϑs ≥ 8ζ and s ≥ 8ζ. Thus, Z
c QT (A, A ) ≥ Tx (Ac ) πθ (dx) ≥ a πθ (A) − ζ − πθ (A1 ) (A∩Ξ)\A1

≥a

aϑ
πθ (A) −ζ ≥ πθ (A) − s . 2 2

c

) If πθ (A2 ) ≤ πθ (A , apply the same argument to Ac . Reversibility and πθ (Ac ) ≥ πθ (A) prove the 2 same bound.

33

c

) Now consider the case πθ (A1 ) > πθ 2(A) and πθ (A2 ) > πθ (A . Fact 1 and πθ (Ac ) ≥ 1/2 yield 2

πθ (A3 ) ≥ dK (A1 , A2 ) πθ (A1 ) πθ (A2 ) ≥

ϑ ϑπθ (A) πθ (A) πθ (Ac ) ≥ . 4 8

Every x ∈ A3 ∩ Ξ ∩ A satisfies Tx (Ac ) ≥ a, and x ∈ A3 ∩ Ξ ∩ Ac satisfies Tx (A) ≥ a. By reversibility, 2QT (A, Ac ) = QT (A, Ac ) + QT (Ac , A) ≥ a πθ (A3 ∩ Ξ) . Since πθ (A3 ∩ Ξ) ≥ πθ (A3 ) − ζ and ζ ≤ ϑs/8, it follows that QT (A, Ac ) ≥

aϑ a ϑπθ (A) −ζ ≥ (πθ (A) − s) . 2 8 16

In all cases, QT (A, Ac ) ≥ aϑ (πθ (A) − s) /16. Taking the infimum over A and using a = (1−δ)/2, we obtain Φs (T) ≥ (1 − δ)ϑ/32. Lazification halves the ergodic flow, proving the claim.

B.3

One-step coupling under SSC, LTSC, and ASC

Proof of Lemma 7. Choose a sufficiently small universal c0 ∈ (0, 1/2] and set r = c0 r0 . For u ∈ int K, write z = u + ηh, where h ∼ N(0, g(u)−1 ), and whenever u + th ∈ int K, set F (t) := hT g(u + th)h ,

ℓ(t) := log det g(u + th) .

When the proposal is feasible, the log proposal-density ratio satisfies log

1
1 pz (u) = ℓ(η) − ℓ(0) − F (η) − F (0) . pu (z) 2 2

Except on an event of probability at most ρ⋆ , ASC ensures feasibility and |F (η) − F (0)| ≤ 2ρ⋆ . By convexity, the entire proposal segment is feasible whenever the proposal is feasible. Writing ξ = g(u)1/2 h, direct differentiation gives the identity for ℓ′ (0), SSC gives the trace bound, and SSC together with LTSC gives the lower bound on ℓ′′ (t): √ ℓ′ (0) = ⟨Tr12 Jug , ξ⟩ , ∥Tr12 Jug ∥ ≤ 2 d , ℓ′′ (t) ≥ −5F (t) . Gaussian concentration, the local-norm comparison in Lemma 14, and Taylor’s formula therefore show, after decreasing c0 if necessary, that ℓ(η) − ℓ(0) ≥ −C outside an additional event of probability at most 2ρ⋆ , where C is universal. This proposal-density-ratio estimate is standard; see [KV24, (G.3)] and [JC25, (55)]. Set a⋆ = C/2 + ρ⋆ . Since 3ρ⋆ < 1/16, for every u ∈ int K, Pu (Guc ) ≤

1 , 16

 pz (u) Gu := z ∈ int K : ≥ e−a⋆ . pu (z)

For x = y, the claim is immediate. For distinct x, y ∈ int K satisfying the local-norm condition in the lemma, we apply the transition-overlap argument in the proof of Lemma 2, with Ξ = int K, a = a⋆ , τ = 1/16, and the bad endpoint set Guc at each u. The preceding bound on Pu (Guc ) verifies the required bad-set estimate, while the definition of Gu gives the same feasibility and proposaldensity-ratio guarantee. Therefore, 1 − dTV (Tx , Ty ) ≥ e−a⋆ and the claim holds with δ0 = 1 − e−a⋆ /8 ∈ (0, 1). 34

1 2
e−a⋆ − = , 4 16 8

C

Lewis-weight path estimates

To prove Lemma 11, we adapt the proof of Lemma 3.3 in [Koo26], which establishes the Gaussian estimates at the base point and along the path while tracking p, m, δ explicitly. Lewis-weight derivative and closeness estimates. Recall from Fact 3 that Px is an orthogonal projector with diag PxP= wx , that 0 ⪯ Nx ⪯ pI, and that both matrices depend smoothly on x. Thus 0 < wx,i ≤ 1 and i wx,i = d. For the path xt = x + th, write At = Axt , Wt = Wxt , wt = wxt , and Nt = Nxt . Let ςt = Axt − b. For a ∈ {β, −1/p}, the coordinatewise closeness estimate in [LS19, Lemma 35] has coefficient at √ most Cp2 , since m1/(p+2) ≤ e and |a| ≤ 1/2. Hence, d log (wta /ςt ) ∞ ≤ Cp2 ∥h∥AT Wt At . t dt √ Proof of Lemma 11. Write κ = κδ and Tδ = cκ −4 / d. We use the affine normalization and Gaussian path from §6.4. We first construct Eδ and establish the required path bounds. In addition to the path notation in Fact 4, set −1/p

ρt := Wt

zt := βℓ′t − ιt ,

ιt ,

Dt = Diag zt . −1/2

′ Also, Fact 3 and direct differentiation give ι′t = −ι◦2 N t vt . t and ℓt = −Wt β Since g(0) = Id , W0 A0 has orthonormal columns and its i-th row has squared norm w0,i . Hence, −1/2

ρ0,i = w0,i (W0β A0 h)i ∼ N(0, 1). By Fact 3 and z0 = βℓ′0 − ι0 , each coordinate of z0 is a centered Gaussian linear form. The closeness estimate with a = β, together with AT 0 W0 A0 ⪯ g(0) = Id , bounds the norm of each coefficient vector by Cp2 . Gaussian concentration, a union bound over the rows, and the standard Gaussian norm bound yield an event Eδ of probability at least 1 − δ on which √ ∥h∥ ≤ Cκ d , ∥ρ0 ∥∞ + ∥z0 ∥∞ ≤ Cκ . 1/p

Since ι0,i = w0,i ρ0,i and 0 < w0,i ≤ 1, ∥ι0 ∥∞ ≤ Cκ, and on the same event, ω0 = 1 + ∥D0 P0 ∥op ≤ 1 + ∥z0 ∥∞ ≤ Cκ . The slack identity ςt,i = ς0,i (1 + tι0,i ) and the bound Tδ ∥ι0 ∥∞ ≤ 1/2, after reducing c, ensure that the whole segment {xt : 0 ≤ t ≤ Tδ } lies in int K. Since λ2 g is SSC (and hence SC) and ∥xt − x0 ∥λ2 g(0) = tλ∥h∥ ≤ Ccλκ −3 , Lemma 14, together √ with κ ≥ p2 , gives ∥h∥g(xt ) ≤ Cκ d for 0 ≤ t ≤ Tδ . Since AT t Wt At ⪯ g(xt ), the RHS of the √ 2 closeness estimate is at most Cκ d for both a = β and a = −1/p. Its integral over [0, Tδ ] is at most Ccκ −2 . Moreover, −1/p

ρt,i = (aT i h)

wt,i

ςt,i

d wtβ zt = log . dt ςt

,

The estimate with a = −1/p gives |ρt,i | ≤ C|ρ0,i |, while the estimate with a = β bounds zt directly. Since zt = βℓ′t −ιt and β has a universal positive lower bound, we obtain, uniformly on the segment, √ ∥ρt ∥∞ + ∥ιt ∥∞ ≤ Cκ , ∥ℓ′t ∥∞ + ∥zt ∥∞ ≤ Cκ 2 d . 35

1/2+1/p

Using (vt )i = wt,i

1/2

ρt,i and (qt )i = wt,i ρ2t,i , together with

√ ∥vt ∥ ≤ Cκ d,

P

i wt,i = d and 0 ⪯ Nt ⪯ pI,

√ ∥Nt vt ∥ + ∥qt ∥ ≤ Cκ 2 d.

Direct differentiation, as in the proof of Lemma 3.3 in [Koo26], gives vt′ = −ιt ◦ vt −

1 (Nt vt ) ◦ ιt , 2

1 2
′ − ℓ ◦ qt − 2ιt ◦ qt , ℓ′t ◦ qt = −(Nt vt ) ◦ ρ◦2 t . 2 p t √ √ Consequently, ∥vt′ ∥ ≤ Cκ 3 d and ∥qt′ ∥ ≤ Cκ 4 d. Since the maps t 7→ Dt and t 7→ Pxt are smooth, the function t 7→ ωt = 1 + ∥Dt Pxt ∥op is continuous on this segment. These estimates prove all claims of the lemma. qt′ =

36

Related documents

• On local large deviations for decoupled random walks#677399
• On local large deviations for decoupled random walks#674202
• Entropic repulsion to the middle layer#984490
• On sequences of martingales with jumps on Riemannian submanifolds#925725
• Kac's Walk on Rotation Matrices Mixes in $\boldsymbol{Θ(n^2)}$ Steps: A Proof Discovered with AI#820675