Accelerating Smooth Games by Manipulating Spectral Shapes
This work addresses numerical challenges in solving smooth games, which is important for optimization in machine learning and game theory, but it is incremental as it builds on existing gradient-based methods and spectral analysis.
The paper tackles the problem of accelerating convergence in smooth games by analyzing spectral shapes of gradient dynamics, proposing an optimal algorithm for bilinear games and identifying conditions for acceleration in strongly monotone operators, with results including an accelerated version of consensus optimization.
We use matrix iteration theory to characterize acceleration in smooth games. We define the spectral shape of a family of games as the set containing all eigenvalues of the Jacobians of standard gradient dynamics in the family. Shapes restricted to the real line represent well-understood classes of problems, like minimization. Shapes spanning the complex plane capture the added numerical challenges in solving smooth games. In this framework, we describe gradient-based methods, such as extragradient, as transformations on the spectral shape. Using this perspective, we propose an optimal algorithm for bilinear games. For smooth and strongly monotone operators, we identify a continuum between convex minimization, where acceleration is possible using Polyak's momentum, and the worst case where gradient descent is optimal. Finally, going beyond first-order methods, we propose an accelerated version of consensus optimization.