Doubly Optimal No-Regret Learning in Monotone Games

Understand

We consider online learning in multi-player smooth monotone games.

• Existing algorithms have limitations such as (1) being only applicable to strongly monotone games; (2) lacking the no-regret guarantee; (3) having only asymptotic or slow $O(\frac{1}{\sqrt{T}})$ last-iterate convergence rate to a Nash equilibrium.
• While the $O(\frac{1}{\sqrt{T}})$ rate is tight for a large class of algorithms including the well-studied extragradient algorithm and optimistic gradient algorithm, it is not optimal for all gradient-based algorithms.
• We propose the accelerated optimistic gradient (AOG) algorithm, the first doubly optimal no-regret learning algorithm for smooth monotone games.