Accelerating Smooth Games by Manipulating Spectral Shapes

Waïss Azizian, Damien Scieur, Ioannis Mitliagkas, Simon Lacoste-Julien, Gauthier Gidel
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:1705-1715, 2020.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-azizian20a, title = {Accelerating Smooth Games by Manipulating Spectral Shapes}, author = {Azizian, Wa\"iss and Scieur, Damien and Mitliagkas, Ioannis and Lacoste-Julien, Simon and Gidel, Gauthier}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {1705--1715}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/azizian20a/azizian20a.pdf}, url = {https://proceedings.mlr.press/v108/azizian20a.html}, 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. } }
Endnote
%0 Conference Paper %T Accelerating Smooth Games by Manipulating Spectral Shapes %A Waïss Azizian %A Damien Scieur %A Ioannis Mitliagkas %A Simon Lacoste-Julien %A Gauthier Gidel %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-azizian20a %I PMLR %P 1705--1715 %U https://proceedings.mlr.press/v108/azizian20a.html %V 108 %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.
APA
Azizian, W., Scieur, D., Mitliagkas, I., Lacoste-Julien, S. & Gidel, G.. (2020). Accelerating Smooth Games by Manipulating Spectral Shapes. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:1705-1715 Available from https://proceedings.mlr.press/v108/azizian20a.html.

Related Material