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

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.