mlsanityData to 7 Oct 2026

On two proofs of d2 mixing of weighted Dikin walks

arXiv 2608.28566 ↗First posted 28 Aug 2026cs.DS cs.LG math.OCcited by 0

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

  1. 2024In-and-Out: Algorithmic Diffusion for Sampling Convex Bodiescited by 18
  2. 2017Fast MCMC sampling algorithms on polytopescited by 17
  3. 2023When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?cited by 12
  4. 2024Sampling and Integration of Logconcave Functions by Algorithmic Diffusioncited by 12
  5. 2019Strong Self-Concordance and Samplingcited by 11
  6. 2020Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithmscited by 9
  7. 2015The Mixing Time of the Dikin Walk in a Polytope - A Simple Proofcited by 7
  8. 2025Zeroth-order Logconcave Samplingcited by 5
  9. 2026A unified complexity bound for logconcave samplingcited by 3
  10. 2024Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysiscited by 2
  11. 2026Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Runcited by 2
  12. 2026Beyond the d2.5-mixing bound for Dikin walks on polytopescited by 1

Built on by

Not cited yet.