Finite-Time Last-Iterate Convergence for Learning in Multi-Player Games

We study the question of last-iterate convergence rate of the extragradient algorithm by [Kor76] and the optimistic gradient algorithm by [Pop80] in multi-player games. We show that both algorithms with constant step-size have last-iterate convergence rate of O ( 1 √ T ) to a Nash equilibrium in terms of the gap function in smooth monotone games, where each player’s action set is an arbitrary convex set . Previous results only study the unconstrained setting, where each player’s action set is the entire Euclidean space. Our results address an open question raised in several recent works [HIMM19, GPD20, GPDO20], which ask for last-iterate convergence rate of either the extragradient or the optimistic gradient algorithm in the constrained setting. Our convergence rates for both algorithms are tight and match the lower bounds by [GPD20, GPDO20]. At the core of our results lies a new notion – the tangent residual , which we use to measure the proximity to a Nash equilibrium. We use the tangent residual (or a modification of the tangent residual) as the the potential function in our analysis of the extragradient algorithm (or the optimistic gradient algorithm).