Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes

In a recent series of papers it has been established that variants of Gradient Descent/Ascent and Mirror Descent exhibit last iterate convergence in convex-concave zero-sum games. Specifically, citeDISZ17, LiangS18 show last iterate convergence of the so called "Optimistic Gradient Descent/Ascent" for the case of textitunconstrained min-max optimization. Moreover, in citeMetal the authors show that Mirror Descent with an extra gradient step displays last iterate convergence for convex-concave problems (both constrained and unconstrained), though their algorithm does not follow the online learning framework; it uses extra information rather than textitonly the history to compute the next iteration. In this work, we show that "Optimistic Multiplicative-Weights Update (OMWU)" which follows the no-regret online learning framework, exhibits last iterate convergence locally for convex-concave games, generalizing the results of citeDP19 where last iterate convergence of OMWU was shown only for the textitbilinear case. We complement our results with experiments that indicate fast convergence of the method.