负动量让极小极大优化收敛更快更普遍。
Negative Momentum for Convex-Concave Optimization
- 提出负动量机制解决极小极大优化发散问题。
- 在凸-凹优化中实现全局收敛，强凸-强凹下加速收敛。
- 为对抗算法提供新工具，适合优化研究者参考。
本文重新审视极小极大优化中的动量机制。虽然动量在凸优化中能加速梯度动态，但直接用于极小极大优化会导致发散。令人意外的是，Gidel 等人（2019）发现负动量可修复收敛性。然而，至今其潜力仍不明确：（1）通用性：在基础的凸-凹优化设置下能否实现全局收敛？这是极小极大算法的标准测试场景；（2）快速收敛：在强凸-强凹优化中（唯一已知全局收敛的非线性情形）能否实现加速收敛？近期研究甚至认为不可能。本文正面回答这两个问题。结果表明，负动量可实现比以往认知更广泛、更快速的收敛，使其与主流竞争算法处于同等地位。
原文摘要 · Abstract (English)
This paper revisits momentum in the context of min-max optimization. Momentum is a celebrated mechanism for accelerating gradient dynamics in settings like convex minimization, but its direct use in min-max optimization makes gradient dynamics diverge. Surprisingly, Gidel et al. 2019 showed that negative momentum can help fix convergence. However, despite these promising initial results and progress since, the power of momentum remains unclear for min-max optimization in two key ways. (1) Generality: is global convergence possible for the foundational setting of convex-concave optimization? This is the direct analog of convex minimization and is a standard testing ground for min-max algorithms. (2) Fast convergence: is accelerated convergence possible for strongly-convex-strong-concave optimization (the only non-linear setting where global convergence is known)? Recent work has even argued that this is impossible. We answer both these questions in the affirmative. Together, these results put negative momentum on more equal footing with competitor algorithms, and show that negative momentum enables convergence significantly faster and more generally than was known possible.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。