Reproduce “On two proofs of $d^2$ mixing of weighted Dikin walks” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Yuansi Chen, Yunbum Kook
The authors analyze Metropolis-corrected Dikin walks using high-probability acceptance control for total-variation mixing and a fourth-order bootstrap for pointwise acceptance and chi-square contraction. For bounded, full-dimensional polytopes with exponential targets, Lee–Sidford, Lewis-weight, and John metrics give a roughly O(d²) iteration bound in total variation. A scaled Lee–Sidford metric gives chi-square mixing in O(d² log²²(em) log((1∨χ²)/ε)), with logarithmic dependence on constraint count.
Key insights
- It is possible to derive Total-Variation mixing bounds for MCMC algorithms by controlling Metropolis-Hastings acceptance probabilities only within a high-probability region of the state space, relaxing the need for global pointwise control.
- A novel 'fourth-order bootstrap control' condition allows for self-consistent bounding of higher-order derivative terms of the local metric along proposal paths, which is crucial for establishing robust Average Self-Concordance without dimension-dependent scaling.
- Combining existing metric regularity conditions with new analytical tools like the high-probability region acceptance and fourth-order bootstrap control enables a deeper and more precise understanding of Dikin walk convergence.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.