A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games

By Waïss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, Gauthier Gidel. 2019

24 citations recorded by the source corpus.

We consider differentiable games: multi-objective minimization problems, where the goal is to find a Nash equilibrium. The machine learning community has recently started using extrapolation-based variants of the gradient method. A prime example is the extragradient, which yields linear convergence in cases like bilinear games, where the standard gradient method fails. The full benefits of extrapolation-based methods are not known: i) there is no unified analysis for a large class of games that includes both strongly monotone and bilinear games; ii) it is not known whether the rate achieved by extragradient can be improved, e.g. by considering multiple extrapolation steps. We answer these questions through new analysis of the extragradient's local and global convergence properties. Our analysis covers the whole range of settings between purely bilinear and strongly monotone games. It reveals that extragradient converges via different mechanisms at these extremes; in between, it exploits the most favorable mechanism for the given problem. We then present lower bounds on the rate of convergence for a wide class of algorithms with any number of extrapolations. Our bounds prove that the extragradient achieves the optimal rate in this class, and that our upper bounds are tight. Our precise characterization of the extragradient's convergence behavior in games shows that, unlike in convex optimization, the extragradient method may be much faster than the gradient method.

Subfields: Artificial Intelligence, Management Science and Operations Research, 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

In Management Science and Operations Research

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Reducing Noise in GAN Training with Variance Reduced Extragradient (2019, methodology): “Daskalakis et al. (2018) proposed a method called Optimistic-Adam inspired by game theory.”
Accelerating Smooth Games by Manipulating Spectral Shapes (2020, methodology): “Ibrahim et al. (2019); Azizian et al. (2019) extended this framework to multi-player games, but they consider lower and upper-bounds on the eigenvalues of the Jacobian of the game rather than their distribution in the complex plane.”
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2019, background): “…a line of algorithmic research on convex-concave minimax optimization in both continuous time [Kose, 1956, Cherukuri et al., 2017] and discrete time [Uzawa, 1958, Golshtein, 1974, Korpelevich, 1976, Nemirovski, 2004, Nedi´c and Ozdaglar, 2009, Mokhtari et al., 2019b,a, Azizian et al., 2019].”
Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems (2020, methodology): “In particular, we could use (Azizian et al., 2019, Lemmas 5 & 12) to conclude that a lower bound of 1 − k 3 · 4 holds in (30), which is smaller than 1 − 6 k 2 ( √ L/µ 1) 2 for sufﬁciently large k (e.g., k > 10 ).”