On Two Proofs of d² Mixing of Weighted Dikin Walks

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 provides a general total-variation mixing bound under strong self-concordance, ν̄-symmetry, and mixed-trace regularity of the local metric, with the key idea of controlling the Metropolis-Hastings acceptance probability on a high-probability region rather than at every point. Applying this framework to 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 and pointwise acceptance control via a new fourth-order bootstrap condition. For appropriately scaled Lee-Sidford metrics, this yields an Õ(d²) mixing bound in χ²-divergence, improving the previous Õ(d^{9/4}) bound.

Paper Overview

Field: Machine Learning Authors: Yuansi Chen, Yunbum Kook Published: 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 using 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.

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

On Two Proofs of d² Mixing of Weighted Dikin Walks

Summary

Paper Overview

Abstract

Tags