Timezone: »

 
Poster
Finite-Time Last-Iterate Convergence for Learning in Multi-Player Games
Yang Cai · Argyris Oikonomou · Weiqiang Zheng

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #836
in Poster Session 1 »
We study the question of last-iterate convergence rate of the extragradient algorithm by Korpelevich [1976] and the optimistic gradient algorithm by Popov [1980] in multi-player games. We show that both algorithms with constant step-size have last-iterate convergence rate of $O(\frac{1}{\sqrt{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 work by Hsieh et al. [2019], Golowich et al. [2020a,b], who 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 Golowich et al. [2020a,b]. At the core of our results lies a new notion -- the tangent residual, which we use to measure the proximity to equilibrium. We use the tangent residual (or a slight variation of the tangent residual) as the the potential function in our analysis of the extragradient algorithm (or the optimistic gradient algorithm) and prove that it is non-increasing between two consecutive iterates.
Keywords: smooth monotone games · last-iterate convergence rate · Nash equilibrium · learning in games
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Yang Cai (Yale University)
Argyris Oikonomou (Yale University)
Argyris Oikonomou

Argyris Oikonomou is a PhD Student in the department of Computer Science at Yale, advised by Yang Cai. Argyris completed his undergraduate studies at the National Technical University of Athens. His research interests are in mechanism design and algorithmic game theory.

Weiqiang Zheng (Yale University)

More from the Same Authors