Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes
share
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, <cit.> show last iterate convergence of the so called "Optimistic Gradient Descent/Ascent" for the case of unconstrained min-max optimization. Moreover, in <cit.> 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 only 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 <cit.> where last iterate convergence of OMWU was shown only for the bilinear case. We complement our results with experiments that indicate fast convergence of the method.
READ FULL TEXT