动能Langevin算法加速梦碎！Strang分裂采样下界曝光，O(√κ)迭代神话被证伪
Provable Non-Acceleration of Standard Strang Splittings of Kinetic Langevin Dynamics
📖 AI 总结
本文针对动力学Langevin动力学的标准Strang分裂算法（如OBABO和BAOAB）在马尔可夫链蒙特卡洛采样中的加速性能进行了严格分析。作者证明了，在仅依赖曲率边界和维度的固定步长与摩擦参数设定下，这些算法无法实现理论上预期的O(√κ)迭代加速（κ为条件数）。通过将优化中的非加速定理迁移至采样场景，研究建立了OBABO等六种Strang分裂的总变差混合时间下界，表明冷启动混合在光滑强凸目标类上无法达到弹道加速。同时，文章给出了OBABO在固定参数下的O(κ)步上界（含对数因子），从而确定其最优条件数依赖为线性。这一发现填补了采样算法加速理论的关键空白，对高维采样器的设计与调参具有重要指导意义。
🔑 关键词速览
| Strang splitting | 一种将动力学算子分解为多个子步骤的数值方法，常用于Langevin动力学的离散化。 |
| Kinetic Langevin dynamics | 描述粒子在势场中运动并受摩擦和随机力影响的随机微分方程，用于采样。 |
| Total variation mixing time | 马尔可夫链从初始分布收敛到目标分布所需步数，以全变差距离度量。 |
| Condition number | 衡量目标分布曲率异质性的指标，影响采样算法的收敛速度。 |
| Heavy-ball recursion | 一种带动量的优化递归，此处用于连接采样与优化中的非加速现象。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅