Dikin Walk 采样再提速：多面体上的混合界从 d^2.5 推向 d^2.25

导语

多面体上的均匀采样和指数采样，是随机算法、凸优化与机器学习中反复出现的基础问题。如何在高维约束区域内高效地产生近似样本，直接影响体积估计、贝叶斯推断、随机优化等任务的理论复杂度。最新提交到 arXiv 的论文《Beyond the $d^{2.5}$-mixing bound for Dikin walks on polytopes》围绕 Dikin walk 的混合时间给出新进展：在多面体指数采样场景下，使用缩放后的 Lee–Sidford 度量，可从 warm start 在 $d^{2.25}$ 次迭代内混合。

核心要点

• 问题背景：Dikin walk 最早由 Kannan 和 Narayanan 于 2009 年提出，灵感来自内点法。它利用障碍函数诱导的局部几何来构造随机游走，因此具有仿射不变性。
• 既有结果：对位于 $\mathbb{R}^d$、由 $m$ 个线性不等式定义的多面体，基于对数障碍的 Dikin walk 曾被证明混合时间为 $md$。2017 年，Chen、Dwivedi、Wainwright 和 Yu 使用 Lewis-weight barrier 将界限改进到 $d^{2.5}$，并猜测正确阶数应为 $d^2$。
• 本次改进：新论文没有直接达到 $d^2$，但把 warm start 下的指数采样混合界推进到 $d^{2.25}$，突破了此前 $d^{2.5}$ 的门槛。
• 技术关键：作者证明 Lee–Sidford 度量具有更强的平均自协调性质，从而能在随机 Dikin 提案方向上保证 Metropolis 过滤步骤有较高接受概率。
• 分析方法：论文指出，过去分析基本受限于二阶控制；本工作采用更系统的高阶分析，包括递归瓶颈项的选择性高阶展开、Lewis 权重高阶导数的移动正交标架计算，以及通过多重随机积分进行 Wiener chaos 分解，以控制产生的高斯多项式。

意义与影响

这项结果的价值首先体现在理论采样复杂度上。Dikin walk 的性能由障碍几何决定，而本文表明，合适的 Lee–Sidford 度量不仅能改善局部提案的形状，还能通过更细致的高阶概率分析提升整体混合界。这意味着内点法中的几何工具仍可能继续为高维采样算法带来复杂度改进。

其次，$d^{2.25}$ 并非终点，而是朝 $d^2$ 猜想迈出的中间一步。论文给出的高阶分析框架，可能比单个指数改进更有长期意义：它为处理 Dikin walk 中复杂的权重导数和随机提案接受率提供了新的技术路径。

需要注意的是，论文讨论的是理论迭代复杂度，并未在摘要中声称给出实际系统加速或实验结果。对于关注凸体采样、随机游走算法和优化几何的研究者而言，这是一项偏基础但重要的进展。

来源：arXiv