Accelerating Smooth Games by Manipulating Spectral Shapes
  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.
