On Multiplicative Weights Update and Mirror-Prox Methods for Zero-Sum Games

We follow up on a recent line of works that attempt to establish last-iterate convergence results for iterative first-order methods in min-max optimization. Our work focuses on extra gradient learning algorithms for finding Nash equilibria in bilinear zero-sum games, motivated by related questions in online learning. A typical drawback of several first-order methods, including the standard versions of gradient descent and multiplicative weight updates, is that they converge only in an average sense, but not w.r.t. their last iterate. We propose a new algorithm, that can be considered as a variant of the Mirror Prox method (Nemirovski 2004), using a large learning rate parameter for the intermediate gradient step and a small learning rate in the final step of each iteration, and prove that it attains last- iterate convergence. Furthermore, we perform experimental comparisons against other recently proposed algorithms (such as the optimistic variant of the multiplicative weights update method, by Daskalakis and Panageas (2019)), and show that our algorithm has significant practical potential since it offers substantial gains in terms of accelerated convergence.