Understand
In a recent series of papers it has been established that variants of Gradient Descent/Ascent and Mirror Descent exhibit last iterate convergence in convex-concave zero-sum games.
- Specifically, \cite{DISZ17, LiangS18} show last iterate convergence of the so called "Optimistic Gradient Descent/Ascent" for the case of \textit{unconstrained} min-max optimization.
- Moreover, in \cite{Metal} the authors show that Mirror Descent with an extra gradient step displays last iterate convergence for convex-concave problems (both constrained and unconstrained), though their algorithm does not follow the online learning framework; it uses extra information rather than \textit{only} the history to compute the next iteration.
- In this work, we show that "Optimistic Multiplicative-Weights Update (OMWU)" which follows the no-regret online learning framework, exhibits last iterate convergence locally for convex-concave games, generalizing the results of \cite{DP19} where last iterate convergence of OMWU was shown only for the \textit{bilinear case}.
Built on
Zur theorie der gesellschaftsspiele
J Von Neumann · 1928
Earlier work this paper cites.
Iterative solutions of games by fictitious play
G.W Brown · 1951
Earlier work this paper cites.
An iterative method of solving a game
J. Robinson · 1951
Earlier work this paper cites.
Prediction, Learning, and Games
Nikolo Cesa-Bianchi and Gabor Lugosi · 2006
Earlier work this paper cites.
Discrete Dynamical Systems
Oded Galor · 2007
Earlier work this paper cites.
Mohammad Sal Moslehian · 2011
Earlier work this paper cites.
Similar
The multiplicative weights update method: a meta-algorithm and applications
Sanjeev Arora, Elad Hazan, and Satyen Kale · 2012
Cited alongside, same era.
Fast convergence of regularized learning in games
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire · 2015
Cited alongside, same era.
Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos
Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras · 2017
Cited alongside, same era.
Multiplicative weights update in zero-sum games
James P. Bailey and Georgios Piliouras · 2018
Cited alongside, same era.
Training GANs with Optimism
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng · 2018
Cited alongside, same era.
Then
The limit points of (optimistic) gradient descent in min-max optimization
Constantinos Daskalakis and Ioannis Panageas · 2018
Later among the works it cites.
Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks
Tengyuan Liang and James Stokes · 2018
Later among the works it cites.
Mirror descent in saddle-point problems: Going the extra (gradient) mile
Panayotis Mertikopoulos, Houssam Zenati, Bruno Lecouat, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras · 2018
Later among the works it cites.
Last-iterate convergence rates for min-max optimization
Jacob D. Abernethy, Kevin A. Lai, and Andre Wibisono · 2019
Later among the works it cites.
Last-iterate convergence: Zero-sum games and constrained min-max optimization
Constantinos Daskalakis and Ioannis Panageas · 2019
Later among the works it cites.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…