Source-linked AI summary
On two proofs of $d^2$ mixing of weighted Dikin walks
Yuansi Chen, Yunbum Kook
TL;DR
The paper asks how to obtain dimension-square mixing guarantees for weighted Dikin walks when sampling exponential distributions on polytopes and truncated PSD cones. It develops high-probability and pointwise acceptance frameworks, yielding eO(d^2) total-variation mixing for several polytope metrics and eO(d^2) χ^2-divergence mixing for a suitably scaled Lee–Sidford metric.
Problem
Prior weighted Dikin-walk analyses had not established the conjectured eO(d^2) bound, with the previous Lee–Sidford result giving eO(d^(9/4)) warm-start mixing.
Method
The paper introduces a high-probability acceptance framework and a second framework using pointwise acceptance, spectral-gap analysis, and fourth-order bootstrap control.
Results
The frameworks yield eO(d^2) total-variation mixing for Lee–Sidford, Lewis-weight, and John metrics on polytopes, plus stronger χ^2-divergence guarantees for Lee–Sidford.
Takeaways & Limitations
Weighted Dikin walks achieve the conjectured dimension-square mixing scale for polytope sampling, while the hybrid truncated-PSD application gives eO(n^2) mixing.
Takeaways & Limitations
The pointwise-acceptance framework requires additional regularity assumptions, including average self-concordance with a dimension-independent radius and a specified bad-event control.
Abstract
from arXiv · showhide
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, $\barν$-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 to the Lee--Sidford, Lewis-weight, and John metrics yields an $\widetilde O(d^2)$ mixing bound for sampling from polytopes, while applying it to a hybrid barrier yields an $\widetilde O(d^4)$ mixing bound for sampling 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 scaled Lee--Sidford metric, this yields an $\widetilde O(d^2)$ mixing bound in $χ^2$-divergence, improving on the previous $\widetilde O(d^{9/4})$ bound.
1 Introduction
The paper develops weighted Dikin walks to reduce representation dependence in polytope sampling and establishes dimension-square mixing through two complementary frameworks.
- Motivation: Sampling from high-dimensional convex bodies supports polynomial-time volume algorithms, motivating efficient general-purpose samplers.The paper situates uniform sampling as a fundamental algorithmic primitive and discusses Ball walk, Hit-and-Run, and In-and-Out.
- Motivation: Polytopes offer explicit inequality descriptions that Dikin walks exploit through position-dependent Gaussian proposals based on barrier Hessians.The original logarithmic-barrier Dikin walk mixes in eO(md), but this dependence varies with redundant constraints.
- Prior approaches: Reducing constraint dependence motivates weighted barriers and metrics, including Vaidya, Lewis-weight, and John constructions.These methods were developed partly to improve the m-dependence of interior-point and sampling complexity.
- Contributions: The paper proves eO(d^2) total-variation mixing for several polytope metrics and strengthens the Lee–Sidford result to χ^2-divergence.Its first framework controls acceptance on a high-probability region; the second obtains pointwise acceptance under additional assumptions.
2 Preliminaries
The preliminaries define the Dikin walk, its local metrics and proposal mechanism, and the regularity conditions used to analyze acceptance and mixing.
- Basic setup: The paper studies exponential targets on convex bodies and uses total variation and χ^2-divergence as mixing criteria.The notation includes the target distribution, divergence definitions, and the relation 4d^2 TV ≤ χ^2.
- The Dikin walk: A Dikin walk uses a position-dependent local metric to generate Gaussian proposals, then applies a Metropolis–Hastings correction.The proposal can be written as Y = x + ηH with H conditioned on x distributed as N(0, g(x)^-1).
- Weighted metrics: Weighted Dikin metrics on polytopes are constructed from constraint slacks and weights, and the resulting process is called a weighted Dikin walk.Leverage scores characterize a key feasibility relation between the metric and its constraint weights.
- Regularity conditions: The analysis assumes regularity properties including self-concordance, strong self-concordance, symmetry, and mixed-23-trace bounds.SSC strengthens the usual derivative control, while ν̄-symmetry measures local ellipsoid approximation to the centrally symmetric part of the body.
- Regularity conditions: For Hessian metrics, SSC implies a bounded mixed-23-trace condition with bound 2.The paper also introduces second-derivative tensors, lower-trace self-concordance, and average self-concordance for later analyses.
- Specialized metrics: The applications use Lee–Sidford, Lewis-weight, and John metrics as specialized weighted Dikin metrics.Their definitions involve normalized scaling parameters and, for weighted constructions, leverage-score and Lewis-weight quantities.
3 Main results
The paper develops two complementary frameworks for analyzing weighted Dikin walks: total-variation mixing from high-probability acceptance control and χ2-contraction from pointwise acceptance control. These frameworks yield dimension-square bounds for several polytope metrics, a dimension-square-in-ambient-dimension bound for truncated PSD cones, and an improved χ2 bound for a scaled Lee–Sidford metric.
- High-probability acceptance control: The first framework proves total-variation mixing using SSC, ν̄-symmetry, and bounded mixed 2/3-trace, while controlling acceptance only on a high-probability region.It therefore avoids assumptions on second derivatives of the metric.
- Pointwise acceptance control: The second framework adds LTSC and fourth-order bootstrap control to obtain pointwise acceptance, a spectral gap, and χ2-contraction.The bootstrap argument controls pathwise variation through an auxiliary function rather than uniformly bounding the full fourth-order tensor.
- Polytope consequences: Applying Theorem 1 to the Lee–Sidford, Lewis-weight, and John metrics yields an Õ(d^2) mixing bound for uniform and exponential targets on polytopes.The result resolves the conjectured dimension-square bound for these metrics.
- Pointwise acceptance control: For a suitably scaled Lee–Sidford metric, the fourth-order criterion yields an Õ(d^2) χ2 mixing bound, improving the previous Õ(d^9/4) result.The new condition removes the additional Õ(d^1/4) scaling factor used in the previous ASC verification.
- Truncated PSD cones: The same framework gives an Õ(d^4) = Õ(n^2) total-variation bound for exponential sampling on truncated PSD cones, where n = d(d + 1)/2 is the ambient dimension.A hybrid metric combines the PSD barrier with the Lee–Sidford metric.
4 Proof of Theorem 1 via s-conductance
The proof replaces worst-case acceptance control with high-probability control on a good region, then combines local transition overlap with cross-ratio isoperimetry through s-conductance to obtain mixing.
- Proof strategy: s-conductance permits the analysis to ignore a potentially bad region while requiring one-step coupling and an isoperimetric inequality.The proof uses this framework instead of ordinary conductance, avoiding the previously undesirable polynomial dependence on warmness and inverse accuracy.
- Acceptance control: The lifted joint law of the stationary point and Gaussian proposal identifies a high-probability region Ξ where bad proposals have small conditional probability.The complement of Ξ is bounded through a bad event under the joint measure, rather than by controlling acceptance at every point.
- Conductance: The isoperimetric argument combines ν̄-symmetry, local-norm comparison, and cross-ratio isoperimetry to convert transition overlap into an s-conductance lower bound.The resulting bound is inserted into the Lovász–Simonovits conductance-to-mixing proposition.
- Transition overlap: Nearby points in Ξ have overlapping proposals and transitions, with 1 − dTV(Tx, Ty) ≥ 3/28 at the selected parameters.Proposal overlap is first established, then rejection losses are controlled on a common downhill half-space.
- Mixing bound: The resulting lazy Dikin walk reaches total-variation distance ε after the bound obtained by substituting the s-conductance estimate into the mixing proposition.The proof chooses the proposal radius and iteration count so that the good-region and overlap estimates apply simultaneously.
5 Proof of Theorem 2 via ordinary conductance
The second proof extends acceptance and transition-overlap control from a high-probability region to the entire interior using fourth-order bootstrap control, enabling ordinary conductance and χ2-contraction.
- Bootstrap to ASC: The proof first uses SSC, bounded mixed 23-trace, and fourth-order bootstrap control to establish average self-concordance.This is the new ingredient needed to control acceptance pointwise rather than only on a stationary high-probability region.
- Transition overlap: Proposal overlap together with LTSC and ASC yields transition overlap for nearby points throughout int K.Unlike the first framework, the good region is the full interior, so the resulting conductance is ordinary rather than s-conductance.
- χ2 mixing: ν̄-symmetry and cross-ratio isoperimetry convert global transition overlap into ordinary conductance, and the conductance bound yields χ2-contraction.The proof then solves the resulting contraction inequality for the χ2 mixing time.
- Pathwise control: SSC controls the initial cubic derivative term, while fourth-order bootstrap control bounds the integral remainder in Taylor’s formula along Gaussian proposal paths.The argument separately controls feasibility, the initial derivative, and the remainder with high probability.
- Pointwise acceptance: The resulting path estimates provide a proposal radius uniform in the base point and dimension, supporting pointwise acceptance control throughout int K.The event guarantees feasibility and the required increment bounds with probability at least 1 − ρ.
6 Applications
The applications verify the abstract regularity conditions for weighted Dikin metrics, obtaining dimension-square total-variation mixing on polytopes and a corresponding bound for a hybrid metric on truncated PSD cones.
- Corollaries: The four corollaries specialize the two theorems to weighted polytope metrics, a hybrid PSD–Lee–Sidford metric, and a scaled Lee–Sidford metric.The required metric regularities are verified separately in the applications section.
- General weighted metrics: Weighted Dikin metrics satisfy SSC and bounded mixed 23-trace through row-derivative bounds, while ellipsoid containment and weight-trace bounds establish ν̄-symmetry.This reduces Theorem 1’s assumptions to three checkable conditions for general weighted Dikin metrics.
- Polytope metrics: The Lee–Sidford, Lewis-weight, and John metrics each satisfy the required conditions with C = 1 and their displayed symmetry parameters.The metric-specific proofs check the row-derivative, leverage-score, and weight-trace conditions in that order.
- Polytope metrics: For the Lee–Sidford and Lewis-weight metrics, the verified symmetry parameters are bounded by approximately d log^2 m, while the John metric has ν̄J ≲ d log^2 em.These estimates produce the dimension-square TV-mixing result after substitution into Theorem 1.
X A. Set
For the scaled Lee–Sidford metric, a Lewis-weight certificate controls projector variation and resolves the fourth-order bottleneck, allowing Theorem 2 to deliver χ2-contraction.
- Hybrid metric: The hybrid PSD–Lee–Sidford metric is formed by adding the PSD barrier metric to an LS component with fixed kernel ker A.The LS component is constructed on the orthogonal complement of the constraint operator’s kernel.
- Hybrid metric: SSC for the sum follows by combining the component SSC bounds through the operators T1 and T2.The proof bounds the normalized derivative of the sum by the component norms and obtains the SSC inequality.
- Hybrid metric: The hybrid metric has O(n log^2 m)-symmetry and 4-bounded mixed 23-trace, which together verify the assumptions needed for the total-variation corollary.The symmetry parameters of the component metrics add.
- Scaled Lee–Sidford metric: The certificate controls projector variation, the N′ contribution, and a differential inequality for the path quantity, establishing bootstrap conditions (B2) and (B3).These estimates avoid the extra d loss of the direct bound.
- χ2 contraction: After eO(1)-scaling, the metric satisfies all conditions of Theorem 2, whose conductance argument yields the stated χ2 mixing bound.The scaling preserves the relevant regularity conditions while increasing the symmetry parameter by the scaling factor.
A Deferred preliminaries
The preliminaries establish notation for vectors, matrices, norms, inner products, positive-semidefinite ordering, Markov kernels, stationarity, lazification, warm starts, and χ^2-divergence.
- The paper defines Euclidean and Frobenius inner products, corresponding vector and matrix norms, identity objects, and Gaussian notation.
- It introduces symmetric, positive-semidefinite, and positive-definite matrix spaces, along with semidefinite ordering, column spaces, and entrywise vector operations.
- A Markov transition kernel acts on probability measures by integrating transition probabilities over measurable sets.
- The law after N steps is ν0T^N, while a stationary distribution satisfies πT = π.
- The lazy kernel is eT = (I + T)/2, and an M-warm start is dominated by M times the stationary distribution.
B.1 Proof of Lemma 1
The proof compares nearby Gaussian proposals under a strongly self-concordant metric, showing that the local metric distortion is controlled enough to bound proposal overlap and acceptance-related quantities.
- Strong self-concordance bounds the normalized change in the local metric by 2∥x − y∥g(x)/(1 − ∥x − y∥g(x))^2.
- For δ = ∥x − y∥g(x) ≤ 1/20, every eigenvalue of the relative metric matrix lies in [7/8, 9/8].
- The proof uses the Gaussian density directly to control the proposal comparison for nearby points.
- Relevant Gaussian moment identities are substituted into the comparison calculation to complete the bound.
- The eigenvalue control is converted into the final numerical estimate using λ^-1 − 1 + log λ ≤ (λ − 1)^2 on [7/8, 9/8].
B.2 Proof of the conductance bound from transition overlap
The conductance proof turns transition overlap into separation of local-norm regions, then combines that separation with reversibility and set partitioning to obtain a conductance lower bound.
- Self-concordance gives the local-norm comparison ∥h∥g(y) ≤ ∥h∥g(x)/(1 − ∥h∥g(x)) for nearby points.
- The proof partitions a measurable set A according to transition probabilities and compares points lying in opposite parts.
- Transition overlap forces points from opposite parts to be separated by more than Δ in the local norm at x and at least Δ/2 at y.
- The cross-ratio comparison yields dK(A1, A2) ≥ Δ/(2√ν̄) ≥ ϑ.
- Reversibility and the measure assumptions produce a conductance bound Φs(T) ≥ (1 − δ)ϑ/32, with lazification halving the ergodic flow.
B.3 One-step coupling under SSC, LTSC, and ASC
The coupling proof analyzes Gaussian proposals along feasible segments and uses ASC, SSC, and LTSC to control feasibility and proposal-density ratios outside small-probability bad events.
- The proposal is generated as z = u + ηh with h sampled from N(0, g(u)^−1), and the metric along the segment is tracked through F(t) and ℓ(t).
- For feasible proposals, the proof examines the log proposal-density ratio.
- ASC ensures feasibility and controls |F(η) − F(0)| outside an event of probability at most ρ⋆, while SSC and LTSC bound the metric-determinant terms.
- Gaussian concentration, local-norm comparison, and Taylor expansion show that ℓ(η) − ℓ(0) ≥ −C outside an additional event of probability at most 2ρ⋆.
- With a⋆ = C/2 + ρ⋆ and 3ρ⋆ < 1/16, the resulting bound supports the transition-overlap argument and yields δ0 = 1 − e^−a⋆/8.
C Lewis-weight path estimates
The proof constructs a high-probability Gaussian event and controls Lewis-weight path quantities along a segment, using coordinatewise closeness and smoothness estimates.
- Proof setup: The proof adapts an earlier Gaussian-estimate argument while tracking p, m, and δ explicitly.It establishes Gaussian estimates both at the base point and along the path.
- Lewis-weight properties: Lewis weights satisfy 0 < w_x,i ≤ 1, sum_i w_x,i = d, and arise as diagonal entries of a smoothly varying orthogonal projector.The associated matrix N_x obeys 0 ⪯ N_x ⪯ pI.
- Path estimates: The coordinatewise closeness estimate applies to a ∈ {β, −1/p} with coefficient at most Cp^2.The bound uses m^(1/(p+2)) ≤ √e and |a| ≤ 1/2.
- High-probability event: Gaussian concentration and a union bound produce an event E_δ of probability at least 1 − δ controlling the path initialization.At the base point, the relevant coordinates are centered Gaussian linear forms whose coefficient norms are bounded by Cp^2.
- Uniform path control: The slack identity and T_δ∥ι_0∥∞ ≤ 1/2 keep the entire segment inside int K.Subsequent self-concordance and closeness estimates uniformly control h, ρ_t,i, z_t, and related quantities along the segment.