Optimistic Gradient Descent/Ascent in Zero-Sum Games

memory of the optimization through an additional historical step, and was recently shown by Daskalakis et al. to exhibit last-iterate convergence in (unconstrained) bilinear zero-sum games.
In the first part of our work, we provide a comprehensive and precise analysis of OGDA, deriving a closed-form
solution of the dynamics; subsequently, we employ tools from spectral theory to discover several surprising
properties of the dynamics. Importantly, we show that the limit points are the orthogonal projection of the initial state
to the space of attractors. Inspired by this geometric property, we propose a variant of projected OGDA that simulates Von Neumann's alternating projections method, converging with a surprising near-linear rate for a natural
class of (constrained) zero-sum games.

Moreover, building on the intuition of OGDA, we consider a general class of optimization algorithms,
which we refer to as Historical Gradient Descent/Ascent (HGDA), that incorporates multiple historical steps
in the optimization algorithm. Based on a frequency domain representation of the dynamics derived through the
Z-transform, we reduce the convergence of HGDA to a Nash equilibrium to the stability of a polynomial, for which
efficient algorithmic schemes are well-established in mathematics and control theory. Therefore, we establish a
broad family of optimization algorithms -- containing OGDA as a special case -- that exhibit last-iterate convergence
to the space of equilibria of the game.

This is a joint work with Paolo Penna from ETH, and the material that I will cover appear in the following:
https://arxiv.org/pdf/2010.00109.pdf
https://arxiv.org/pdf/2010.03211.pdf

--------------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.