A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Games
This work addresses the lack of unified convergence analysis for gradient-based methods in game theory, which is incremental but important for optimizing algorithms in machine learning applications like adversarial training.
The authors tackled the problem of analyzing gradient-based methods for finding Nash equilibria in differentiable games, providing a unified and tight convergence analysis for extragradient, optimistic gradient, and consensus optimization methods across a spectrum from bilinear to strongly monotone games, showing that extragradient can be much faster than standard gradient descent.
We consider differentiable games where the goal is to find a Nash equilibrium. The machine learning community has recently started using variants of the gradient method (GD). Prime examples are extragradient (EG), the optimistic gradient method (OG) and consensus optimization (CO), which enjoy linear convergence in cases like bilinear games, where the standard GD fails. The full benefits of theses relatively new methods are not known as there is no unified analysis for both strongly monotone and bilinear games. We provide new analyses of the EG's local and global convergence properties and use is to get a tighter global convergence rate for OG and CO. Our analysis covers the whole range of settings between bilinear and strongly monotone games. It reveals that these methods converge via different mechanisms at these extremes; in between, it exploits the most favorable mechanism for the given problem. We then prove that EG achieves the optimal rate for a wide class of algorithms with any number of extrapolations. Our tight analysis of EG's convergence rate in games shows that, unlike in convex minimization, EG may be much faster than GD.