论文标题
动量外部何时最佳？基于多项式的分析
When is Momentum Extragradient Optimal? A Polynomial-Based Analysis
论文作者
论文摘要
由于其在可区分游戏中的强大收敛属性，该外部方法已经获得了知名度。与单目标优化不同，游戏动力学涉及复杂的相互作用，该复杂的交互作用由散布在复杂平面上的游戏矢量场的雅各布的特征值所反映。这种复杂性可能会导致简单的梯度方法差异，甚至对于双线性游戏，而外部方法可以达到融合。在最近经过证实的双线性游戏外部方法\ citep {azizizian2020Acceleration}的动量外部方法的融合的基础上，我们使用基于多项式的分析来识别这种方法进一步加速融合的三种不同的情况。这些场景涵盖了特征值位于（正）真实线上，与复合物共轭旁边的真实线上或仅像复杂的共轭物一样存在。此外，我们为达到最快收敛速率的每种情况得出了超参数。
The extragradient method has gained popularity due to its robust convergence properties for differentiable games. Unlike single-objective optimization, game dynamics involve complex interactions reflected by the eigenvalues of the game vector field's Jacobian scattered across the complex plane. This complexity can cause the simple gradient method to diverge, even for bilinear games, while the extragradient method achieves convergence. Building on the recently proven accelerated convergence of the momentum extragradient method for bilinear games \citep{azizian2020accelerating}, we use a polynomial-based analysis to identify three distinct scenarios where this method exhibits further accelerated convergence. These scenarios encompass situations where the eigenvalues reside on the (positive) real line, lie on the real line alongside complex conjugates, or exist solely as complex conjugates. Furthermore, we derive the hyperparameters for each scenario that achieve the fastest convergence rate.
