When is Momentum Extragradient Optimal? A Polynomial-Based Analysis
This work addresses convergence issues in game optimization for researchers and practitioners, but it is incremental as it builds on prior momentum extragradient analysis.
The paper tackles the problem of accelerating convergence in differentiable games by analyzing when the momentum extragradient method is optimal, identifying three eigenvalue scenarios where it achieves further accelerated convergence and deriving optimal hyperparameters for each.
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.