Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes
This work addresses a theoretical gap in online learning for game theory, though it is incremental as it extends known methods to more general settings.
The authors tackled the problem of achieving last iterate convergence in no-regret learning for constrained min-max optimization in convex-concave games, showing that Optimistic Multiplicative-Weights Update (OMWU) exhibits local last iterate convergence, generalizing prior results from bilinear cases.
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, \cite{DISZ17, LiangS18} show last iterate convergence of the so called "Optimistic Gradient Descent/Ascent" for the case of \textit{unconstrained} min-max optimization. Moreover, in \cite{Metal} 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 \textit{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 \cite{DP19} where last iterate convergence of OMWU was shown only for the \textit{bilinear case}. We complement our results with experiments that indicate fast convergence of the method.