# Beyond the d2.5-mixing bound for Dikin walks on polytopes

arXiv: https://arxiv.org/abs/2607.13943 · HTML: https://mlsanity.com/paper/2607.13943/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 41 references that are in the map.
- First posted on arXiv 15 Jul 2026.

## Builds on (most cited first, 16 of 16)

- [Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space](https://mlsanity.com/paper/2202.01908/) (2022)
- [In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies](https://mlsanity.com/paper/2405.01425/) (2024)
- [Fast MCMC sampling algorithms on polytopes](https://mlsanity.com/paper/1710.08165/) (2017)
- [The entropic barrier: a simple and optimal universal self-concordant barrier](https://mlsanity.com/paper/1412.1587/) (2014)
- [Sampling and Integration of Logconcave Functions by Algorithmic Diffusion](https://mlsanity.com/paper/2411.13462/) (2024)
- [Strong Self-Concordance and Sampling](https://mlsanity.com/paper/1911.05656/) (2019)
- [Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integrators](https://mlsanity.com/paper/2210.07219/) (2022)
- [Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms](https://mlsanity.com/paper/2008.02146/) (2020)
- [The Mixing Time of the Dikin Walk in a Polytope - A Simple Proof](https://mlsanity.com/paper/1508.01977/) (2015)
- [Faster logconcave sampling from a cold start in high dimension](https://mlsanity.com/paper/2505.01937/) (2025)
- [Universal Barrier is n-Self-Concordant](https://mlsanity.com/paper/1809.03011/) (2018)
- [Zeroth-order Logconcave Sampling](https://mlsanity.com/paper/2507.18021/) (2025)
- [John's Walk](https://mlsanity.com/paper/1803.02032/) (2018)
- [R'enyi-infinity constrained sampling with d3 membership queries](https://mlsanity.com/paper/2407.12967/) (2024)
- [Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk](https://mlsanity.com/paper/2410.05700/) (2024)
- [Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis](https://mlsanity.com/paper/2412.11303/) (2024)

## Built on by (most cited first, 2 of 2)

- [A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra](https://mlsanity.com/paper/2608.25273/) (2026)
- [On two proofs of d2 mixing of weighted Dikin walks](https://mlsanity.com/paper/2608.28566/) (2026)

## Abstract (arXiv)

Inspired by interior-point methods (IPM) for structured convex optimization, Kannan and Narayanan introduced the Dikin walk for sampling uniformly from polytopes in 2009. As in IPMs, the Dikin walk is affine-invariant, and its convergence is governed by the barrier geometry used to define its local proposal. They showed that the Dikin walk with the logarithmic barrier for a polytope in ℝd with m linear inequalities mixes in md iterations. In 2017, Chen, Dwivedi, Wainwright, and Yu improved this to d2.5 using a Lewis-weight barrier, and conjectured that the correct mixing time should be d2. We make progress toward this conjecture by improving the previous d2.5-mixing bound. For exponential sampling over a polytope, we prove that the Dikin walk with a scaled Lee--Sidford metric mixes from a warm start in d2.25 iterations. This also yields an improved cold-start complexity via a known annealing framework. The main technical ingredient is improved average self-concordance of the Lee--Sidford metric, which gives high acceptance probability for the Metropolis filter along a random Dikin proposal. While previous analyses were effectively limited to second-order control due to technical difficulties, we develop a principled higher-order analysis. The proof combines a selective higher-order expansion of recursive bottleneck terms, a moving orthonormal-frame calculus for higher derivatives of the Lewis weights, and Wiener-chaos decompositions via multiple stochastic integrals to control the resulting Gaussian polynomials.