Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 9 min ago
PreprintCC BY 4.0arXiv

On two proofs of d2 mixing of weighted Dikin walks

  • Yuansi Chen
  • Yunbum Kook
Open at sourcePDFDOICite

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 to the Lee--Sidford, Lewis-weight, and John metrics yields an Õ(d2) mixing bound for sampling from polytopes, while applying it to a hybrid barrier yields an Õ(d4) 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 Õ(d2) mixing bound in χ2-divergence, improving on the previous Õ(d9/4) bound.

Related

  1. Quadratic mixing for the Lee--Sidford Dikin walk
    Yiping Lu
    arXivPreprintCC BY 4.0Full textProbabilityStatisticsarXiv
  2. Two new proofs of Chui's Conjecture in Weighted Bergman Spaces
    Georgia Corbett
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv
  3. The Weighted Walks in Quadrant with Finite Groups: an Algebro-Geometric Approach
    Vladimir Dragovic, Milena Radnovic
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. Finding Simple Proofs for First-Order Optimization
    Daniel Berg Thomsen, Manu Upadhyaya, Baptiste Goujaud +2
    HALPreprintPublisher termsFull textOptimisation & controlHAL
  5. An introduction to the strategy of transcendence proofs
    Michel Waldschmidt
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{chen2026proofs,
  title = {{On two proofs of $d^2$ mixing of weighted Dikin walks}},
  author = {Yuansi Chen and Yunbum Kook},
  howpublished = {arXiv},
  year = {2026},
  month = aug,
  doi = {10.48550/arxiv.2608.28566},
  eprint = {2608.28566},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.28566},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On two proofs of d^2 mixing of weighted Dikin walks
AU  - Yuansi Chen
AU  - Yunbum Kook
PY  - 2026
DA  - 2026/08/28
PB  - arXiv
DO  - 10.48550/arxiv.2608.28566
UR  - https://arxiv.org/abs/2608.28566
AB  - 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 to the Lee--Sidford, Lewis-weight, and John metrics yields an Õ(d^2) mixing bound for sampling from polytopes, while applying it to a hybrid barrier yields an Õ(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 Õ(d^2) mixing bound in χ^2-divergence, improving on the previous Õ(d^9/4) bound.
ER  -