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

Abstract

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.

Fixing typos and adding invertibility assumption

References in corpus (3)

• Fast Convergence of Regularized Learning in Games
• Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos
• Last-iterate convergence rates for min-max optimization

Cited by in corpus (5)

• SGD Learns One-Layer Networks in WGANs
• Near-Optimal No-Regret Learning in General Games
• Tight last-iterate convergence rates for no-regret learning in multi-player games
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization
• On the Impossibility of Convergence of Mixed Strategies with No Regret Learning