Accelerating Smooth Games by Manipulating Spectral Shapes

Understand

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.