Accelerating Smooth Games by Manipulating Spectral Shapes

By Waïss Azizian, Damien Scieur, Ioannis Mitliagkas, Simon Lacoste-Julien, Gauthier Gidel. 2020

50 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Simon Lacoste-Julien
2. Gauthier Gidel
3. Ioannis Mitliagkas
4. Nicolas Loizou
5. Constantinos Daskalakis
6. Hugo Berard
7. Peter Richtárik
8. Pascal Vincent

In Computational Theory and Mathematics

1. Nicolas Loizou
2. Pascal Vincent
3. Hugo Berard
4. Gauthier Gidel
5. Asuman E. Ozdaglar
6. Franck Iutzeler
7. Jérôme Malick
8. Constantinos Daskalakis

In Numerical Analysis

1. Simon Lacoste-Julien
2. Gauthier Gidel
3. Sarath Pattathil
4. Ioannis Mitliagkas
5. Constantinos Daskalakis
6. Waïss Azizian
7. Noah Golowich
8. Hugo Berard

In Optimization & Training

1. Simon Lacoste-Julien
2. Gauthier Gidel
3. Nicolas Loizou
4. Ioannis Mitliagkas
5. Peter Richtárik
6. Hugo Berard
7. Pascal Vincent
8. Waïss Azizian

Citations in the corpus

• Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “Deterministic Hamiltonian Gradient Descent Hamiltonian gradient descent (HGD) has been proposed as an efficient method for solving min-max problems in Balduzzi et al. (2018). To the best of our knowledge, the first convergence analysis of the method is presented in Abernethy et al.”
• Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling (2020, methodology): “We terminate our analysis with a dedicated treatment of affine operators which are commonly studied as a first step to understand the training of GANs [1, 6, 9, 17, 23, 39].”
• Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems (2020, background): “Azizian et al. (2020) describe a class of strongly convex-strongly concave functions for which first-order algorithms such as EG can be accelerated.”
• Linear Lower Bounds and Conditioning of Differentiable Games (2019, background): “4 of Azizian et al. (2020).”
• Tight last-iterate convergence rates for no-regret learning in multi-player games (2020, background): “Definition 5 ( p -SCLIs [ASSS15, ASM + 20]) .”