On two proofs of $d^2$ mixing of weighted Dikin walks
2026-08-28 • Data Structures and Algorithms
Data Structures and AlgorithmsMachine Learning
AI summaryⓘ
The authors analyze how quickly a type of random walk called weighted Dikin walks can sample from certain complex mathematical shapes like polytopes and truncated positive-semidefinite cones. They develop new methods to better estimate the acceptance rate of steps in the random walk, which improves the theoretical speed of mixing, or how fast the walk produces useful random samples. Their work provides improved guarantees for the sampling time under different settings, using advanced mathematical conditions related to the geometry of the spaces. This includes more efficient sampling bounds for both polytopes and PSD cones compared to previous results.
weighted Dikin walkmixing timepolytopespositive-semidefinite conetotal variation distanceMetropolis–Hastings algorithmself-concordanceLee–Sidford metricchi-squared divergencesampling algorithms
Authors
Yuansi Chen, Yunbum Kook
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ν$-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.