2026-08-18T13:47:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10120 2024-03-06T10:45:25Z ddc:004 open_access

Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization Daskalakis, Constantinos Panageas, Ioannis No regret learning Zero-sum games Convergence Dynamical Systems KL divergence 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Constantinos Daskalakis and Ioannis Panageas 2019 Is Part Of LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2019.27 urn:nbn:de:0030-drops-101204 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.27 eng https://creativecommons.org/licenses/by/3.0/legalcode