Title: Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization,
Abstract: Motivated by applications in Game Theory, Optimization, and Generative
Adversarial Networks, recent work of Daskalakis et al~\cite{DISZ17} and
follow-up work of Liang and Stokes~\cite{LiangS18} 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 {\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 no-regret
Multiplicative-Weights-Update method called "Optimistic Multiplicative-Weights
Update (OMWU)". This answers an open question of Syrgkanis et al~\cite{SALS15}.
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.