Beyond the $d^{2.5}$-mixing bound for Dikin walks on polytopes

TL;DR — This paper improves the mixing-time bound for the Dikin walk, a random-walk MCMC method for sampling from polytopes, advancing toward a long-standing conjecture. It matters as foundational progress in sampling and convex-geometry algorithms underlying optimization and probabilistic ML.

• Beats the prior $d^{2.5}$ mixing bound: proves the Dikin walk with a scaled Lee–Sidford metric mixes in $d^{2.25}$ iterations (from a warm start) for exponential sampling over a polytope in $\mathbb{R}^d$, moving toward the conjectured $d^2$ optimum.
• The warm-start result also yields improved cold-start complexity via a known annealing framework.
• Key technical advance is improved average self-concordance of the Lee–Sidford metric, giving high Metropolis-filter acceptance along random Dikin proposals.
• Introduces a principled higher-order analysis (beyond prior second-order-limited methods), combining selective higher-order expansions, a moving orthonormal-frame calculus for Lewis-weight derivatives, and Wiener-chaos decompositions to bound the resulting Gaussian polynomials.