这篇理论论文把 Dikin walk 采样的混合时间从 $d^{2.5}$ 降到了 $d^{2.25}$，离理论下界 $d^{2}$ 更近了，搞采样理论的同学可以关注。
Kannan 和 Narayanan 于 2009 年提出 Dikin walk 用于对多面体均匀采样。Chen 等人在 2017 年使用 Lewis-weight 势垒将混合时间改进至 $d^{2.5}$ 并猜想最优界为 $d^{2}$。本论文将 Dikin walk 的混合时间从 $d^{2.5}$ 改进至 $d^{2.25}$，基于缩放后的 Lee–Sidford 度量，从热启动出发达到指数精度。主要技术是改进的 Lee–Sidford 度量平均自和谐性，结合高阶展开、移动正交标架计算及 Wiener 混沌分解。
Beyond the $d^{2.5}$-mixing bound for Dikin walks on polytopes
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 mixing time should be $d^{2}$. We make progress toward this conjecture by improving the previous $d^{2.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 $d^{2.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.