11:10
官方账号arXiv cs.LG@Yunbum Kook
推荐理由：这篇理论论文把 Dikin walk 采样的混合时间从 $d^{2.5}$ 降到了 $d^{2.25}$，离理论下界 $d^{2}$ 更近了，搞采样理论的同学可以关注。
混合时间
共 1 条相关 AI 资讯
7月16日
11:10
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 混沌分解。