Timezone: »

 
Poster
Tight last-iterate convergence rates for no-regret learning in multi-player games
Noah Golowich · Sarath Pattathil · Constantinos Daskalakis

Thu Dec 10 09:00 PM -- 11:00 PM (PST) @ Poster Session 6 #1858
in Poster Session 7 »

We study the question of obtaining last-iterate convergence rates for no-regret learning algorithms in multi-player games. We show that the optimistic gradient (OG) algorithm with a constant step-size, which is no-regret, achieves a last-iterate rate of O(1/√T) with respect to the gap function in smooth monotone games. This result addresses a question of Mertikopoulos & Zhou (2018), who asked whether extra-gradient approaches (such as OG) can be applied to achieve improved guarantees in the multi-agent learning setting. The proof of our upper bound uses a new technique centered around an adaptive choice of potential function at each iteration. We also show that the O(1/√T) rate is tight for all p-SCLI algorithms, which includes OG as a special case. As a byproduct of our lower bound analysis we additionally present a proof of a conjecture of Arjevani et al. (2015) which is more direct than previous approaches.

Keywords: Variational Inference · Probabilistic Methods · Algorithms -> Kernel Methods; Algorithms -> Nonlinear Dimensionality Reduction and Manifold Learning; Probabilistic Methods

Author Information

Noah Golowich (Massachusetts Institute of Technology)
Sarath Pattathil (Massachusetts Institute of Technology)
Constantinos Daskalakis (MIT)

More from the Same Authors