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, Daskalakis et al. (2018); Liang and Stokes (2018) show last iterate convergence of the so called “Optimistic Gradient Descent/Ascent" for the case of unconstrained min-max optimization. Moreover, in Mertikopoulos et al. (2018) 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 uses vanishing step-sizes. In this work, we show that "Optimistic Multiplicative-Weights Update (OMWU)" with constant stepsize, exhibits last iterate convergence locally for convex-concave games, generalizing the results of Daskalakis and Panageas (2019) where last iterate convergence of OMWU was shown only for the bilinear case. To the best of our knowledge, this is the first result about last-iterate convergence for constrained zero sum games (beyond the bilinear case) in which the dynamics use constant step-sizes.