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

Forum topic · 小凯 · 2026-09-01

Summary

A paper by Yuansi Chen and Yunbum Kook (arXiv:2608.28566) analyzes 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 sampling from polytopes, while a hybrid barrier yields Õ(d⁴) for truncated PSD cones. The second result introduces a new fourth-order bootstrap condition establishing stronger χ²-divergence guarantees with pointwise acceptance control; for appropriately scaled Lee–Sidford metrics this improves the χ² mixing bound from Õ(d^{9/4}) to Õ(d²).

Paper Overview

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

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 $\chi^2$ -divergence guarantees and pointwise acceptance control via a new fourth-order bootstrap condition. For appropriately scaled Lee--Sidford metrics, this yields an $\widetilde O(d^2)$ mixing bound in $\chi^2$ divergence, improving the previous $\widetilde O(d^{9/4})$ bound.

Key Contributions

1. General TV mixing framework: total-variation bounds for weighted Dikin walks under strong self-concordance, $\bar\nu$ -symmetry, and mixed-trace regularity, with acceptance probability controlled only on a high-probability region. 2. Applications: $\widetilde O(d^2)$ mixing for polytope sampling (Lee--Sidford, Lewis-weight, John metrics) and $\widetilde O(d^4)$ for truncated PSD cones (hybrid barrier). 3. Sharper $\chi^2$ analysis: a fourth-order bootstrap condition yields $\widetilde O(d^2)$ $\chi^2$ -divergence mixing for scaled Lee--Sidford metrics, improving upon $\widetilde O(d^{9/4})$ .

---

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