arXiv Analytics

Sign in

arXiv:1807.04252 [math.OC]AbstractReferencesReviewsResources

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

Constantinos Daskalakis, Ioannis Panageas

Published 2018-07-11Version 1

Motivated by applications in Game Theory, Optimization, and Generative Adversarial Networks, recent work of Daskalakis et al. and Liang and Stokes has 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 {\em unconstrained} convex-concave min-max optimization problems. We show that the same holds true in the more general problem of {\em constrained} min-max optimization under a variant of the Multiplicative-Weights-Update method called "Optimistic Multiplicative-Weights Update (OMWU)". The generality of the constrained problem, which in particular captures all Linear Programming, requires fundamentally different techniques for analyzing the progress of OMWU towards min-max solutions. 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 experiment with zero-sum games to measure how the convergence rate scales with the dimension.

Related articles: Most relevant | Search more
arXiv:1606.04244 [math.OC] (Published 2016-06-14)
Optimal Control and Zero-Sum Games for Markov Chains of Mean-Field Type
arXiv:1307.4686 [math.OC] (Published 2013-07-17, updated 2014-04-15)
On martingale problems with continuous-time mixing and values of zero-sum games without Isaacs condition
arXiv:1405.4658 [math.OC] (Published 2014-05-19, updated 2015-04-13)
Ergodicity conditions for zero-sum games