On Two Proofs of d² Mixing of Weighted Dikin Walks — arXiv 2608.28566

Forum topic · 小凯 · 2026-09-01

Summary

This paper by Yuansi Chen and Yunbum Kook (arXiv:2608.28566) studies the mixing time of weighted Dikin walks for sampling from exponential distributions on polytopes and truncated positive-semidefinite (PSD) cones. The first result gives a general total-variation mixing bound under strong self-concordance, ν̄-symmetry, and mixed-trace regularity of 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²) mixing bound for polytope sampling, while a hybrid barrier yields an Õ(d⁴) bound for truncated PSD cones. The second result establishes stronger χ²-divergence guarantees with pointwise acceptance control via a new fourth-order bootstrap condition; for suitably scaled Lee–Sidford metrics this gives an Õ(d²) χ² mixing bound, improving the previous Õ(d^{9/4}) bound.

Overview

Field: Machine Learning Authors: Yuansi Chen, Yunbum Kook Published: 2026-08-28 arXiv: 2608.28566

Abstract (translated)

The paper studies the mixing time of weighted Dikin walks for sampling from exponential distributions on polytopes and truncated positive-semidefinite (PSD) cones. Two main results are presented:

1. Total-variation bound. A general mixing bound under strong self-concordance, $\bar\nu$ -symmetry, and mixed-trace regularity of 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 polytope sampling, while applying it to a hybrid barrier yields an $\widetilde O(d^4)$ mixing bound for truncated PSD cone sampling.

2. χ²-divergence bound. Using a new fourth-order bootstrap condition, the authors establish stronger χ²-divergence guarantees and pointwise acceptance control. For suitably scaled Lee–Sidford metrics, this yields an $\widetilde O(d^2)$ mixing bound in χ²-divergence, improving the previous $\widetilde O(d^{9/4})$ bound.

Original 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, $\bar\nu$ -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 χ²-divergence guarantees and pointwise accep...

--- *Auto-collected on 2026-09-01*