揭示乐观乘法权重算法慢收敛的几何原因,给出精确量化分析。
When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation

- 将对偶迭代视为能量耗散的乐观梯度下降。
- 证明在纯策略边界附近收敛受几何瓶颈限制,提出新线性收敛率。
- 发现不同距离度量下收敛速度不可通用,适合博弈论与优化研究者。
本文研究乐观乘法权重更新算法(OMWU)在双人零和博弈中的收敛性。近期工作已发现某些情况下OMWU的末次迭代可收敛极慢,但其发生条件与原因仍不明确。本文提出新分析框架,将算法对偶迭代视为关于能量函数的乐观偏置梯度下降,并证明能量具有耗散性。通过建立耗散幅度的紧界,定量揭示了当原始迭代接近单纯形边界时出现的几何瓶颈。这进一步导出在唯一且内部纳什均衡博弈中,关于KL散度的新线性末次迭代收敛率。相比先前结果,该速率对博弈特有常数的依赖更优,且我们证明此依赖关系是紧的。此外,这些几何洞察带来新的统一收敛率分离:一方面,在KL散度与总变差距离下,末次迭代收敛率存在常数下界;另一方面,在2×2情形下,首次获得关于对偶间隙的全新${ ilde O}(T^{-1/2})$最佳迭代率,显著优于此前成果。综上表明,不同距离度量下的统一收敛保证无法互通。
原文摘要 · Abstract (English)
This paper studies the convergence of the Optimistic Multiplicative Weights Update algorithm (OMWU) in two player zero-sum games. Recent works have identified instances on which the last-iterate of OMWU can converge arbitrarily slowly, but understanding when and why this slow convergence occurs has remained open. In this work, we develop a new analysis framework that gives sharp, quantitative explanations for this behavior. Our analysis is based on viewing the algorithm's dual iterates as an optimistic skew-gradient descent with respect to an energy function. We prove over the dual iterates that energy is dissipative, and by establishing tight bounds on the magnitude of dissipation, our analysis quantifies the geometric bottlenecks that arise when the corresponding primal iterates are close to the simplex boundary. This further translates into a new linear last-iterate convergence rate in KL divergence on games with a unique and interior Nash equilibrium. Compared to prior work, this new rate contains a much sharper dependence on game-specific constants, and we prove this dependence is optimal. Moreover, these geometric insights further translate into new separations on uniform convergence rates for OMWU. On the one hand, we prove constant lower bounds on the uniform best-iterate convergence rate in KL divergence and total variation distance from Nash. On the other hand, we establish for the $2\times 2$ setting a new ${\widetilde O}(T^{-1/2})$ best-iterate rate in duality gap, improving substantially over prior work. Together, this shows in general that uniform convergence rate guarantees do not transfer across different measures of distance to Nash.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。