%0 Journal Article %1 azizian2020accelerating %A Azizian, Waïss %A Scieur, Damien %A Mitliagkas, Ioannis %A Lacoste-Julien, Simon %A Gidel, Gauthier %D 2020 %K game-theory geometry optimization readings %T Accelerating Smooth Games by Manipulating Spectral Shapes %U http://arxiv.org/abs/2001.00602 %X 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.

@article{azizian2020accelerating, abstract = {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.}, added-at = {2020-01-09T18:34:52.000+0100}, author = {Azizian, Waïss and Scieur, Damien and Mitliagkas, Ioannis and Lacoste-Julien, Simon and Gidel, Gauthier}, biburl = {https://www.bibsonomy.org/bibtex/2500b285125bf4efdc8588081a724941a/kirk86}, description = {[2001.00602] Accelerating Smooth Games by Manipulating Spectral Shapes}, interhash = {4fa8ec63228ec4b2e40079d6614b423a}, intrahash = {500b285125bf4efdc8588081a724941a}, keywords = {game-theory geometry optimization readings}, note = {cite arxiv:2001.00602}, timestamp = {2020-01-09T18:34:52.000+0100}, title = {Accelerating Smooth Games by Manipulating Spectral Shapes}, url = {http://arxiv.org/abs/2001.00602}, year = 2020 }