On two proofs of d2 mixing of weighted Dikin walks
Not on the map. Why?
Abstract (arXiv)
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, barnu-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(d2) mixing bound for sampling from polytopes, while applying it to a hybrid barrier yields an widetilde O(d4) mixing bound for sampling from truncated PSD cones. Our second result establishes stronger chi2-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(d2) mixing bound in chi2-divergence, improving on the previous widetilde O(d9/4) bound.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 12 of its 34 references that are in the map. First posted on arXiv 28 Aug 2026.
Builds on
12 of 34 references.
References · 12
- 2024In-and-Out: Algorithmic Diffusion for Sampling Convex Bodiescited by 18
- 2017Fast MCMC sampling algorithms on polytopescited by 17
- 2023When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?cited by 12
- 2024Sampling and Integration of Logconcave Functions by Algorithmic Diffusioncited by 12
- 2019Strong Self-Concordance and Samplingcited by 11
- 2020Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithmscited by 9
- 2015The Mixing Time of the Dikin Walk in a Polytope - A Simple Proofcited by 7
- 2025Zeroth-order Logconcave Samplingcited by 5
- 2026A unified complexity bound for logconcave samplingcited by 3
- 2024Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysiscited by 2
- 2026Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Runcited by 2
- 2026Beyond the d2.5-mixing bound for Dikin walks on polytopescited by 1
Built on by
Not cited yet.