Beyond the $d^{2.5}$-mixing bound for Dikin walks on polytopes
Merged summary
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.
Sources (1)
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.