{"id":"arxiv/2607.13943","url":"https://arxiv.org/abs/2607.13943","tags":["cs.DS","cs.LG","math.OC"],"score":0,"title":"Beyond the $d^{2.5}$-mixing bound for Dikin walks on polytopes","domain":"cs.DS","source":"arxiv","authors":["Yunbum Kook"],"reviews":0,"subject":"cs.DS","summary":"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 $\\mathbb{R}^{d}$ with $m$ linear inequalities mixes in $md$ iterations. In 2017, Chen, Dwivedi, Wainwright, and Yu improved this to $d^{2.5}$ using a Lewis-weight barrier, and conjectured that the correct…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-15","reactions":{}}