License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.27
URN: urn:nbn:de:0030-drops-101204
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10120/
Go to the corresponding LIPIcs Volume Portal

Daskalakis, Constantinos ; Panageas, Ioannis

Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization

pdf-format:
LIPIcs-ITCS-2019-27.pdf (0.6 MB)

Abstract

Motivated by applications in Game Theory, Optimization, and Generative Adversarial Networks, recent work of Daskalakis et al [Daskalakis et al., ICLR, 2018] and follow-up work of Liang and Stokes [Liang and Stokes, 2018] have established that a variant of the widely used Gradient Descent/Ascent procedure, called "Optimistic Gradient Descent/Ascent (OGDA)", exhibits last-iterate convergence to saddle points in unconstrained convex-concave min-max optimization problems. We show that the same holds true in the more general problem of constrained min-max optimization under a variant of the no-regret Multiplicative-Weights-Update method called "Optimistic Multiplicative-Weights Update (OMWU)". This answers an open question of Syrgkanis et al [Syrgkanis et al., NIPS, 2015].
The proof of our result requires fundamentally different techniques from those that exist in no-regret learning literature and the aforementioned papers. We show that OMWU monotonically improves the Kullback-Leibler divergence of the current iterate to the (appropriately normalized) min-max solution until it enters a neighborhood of the solution. Inside that neighborhood we show that OMWU becomes a contracting map converging to the exact solution. We believe that our techniques will be useful in the analysis of the last iterate of other learning algorithms.

BibTeX - Entry

@InProceedings{daskalakis_et_al:LIPIcs:2018:10120,
  author =	{Constantinos Daskalakis and Ioannis Panageas},
  title =	{{Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{27:1--27:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10120},
  URN =		{urn:nbn:de:0030-drops-101204},
  doi =		{10.4230/LIPIcs.ITCS.2019.27},
  annote =	{Keywords: No regret learning, Zero-sum games, Convergence, Dynamical Systems, KL divergence}
}

Keywords: No regret learning, Zero-sum games, Convergence, Dynamical Systems, KL divergence
Collection: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 08.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI