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. Namely, our algorithm achieves both (i) the optimal $ O(sqrt{T}) $ regret in the adversarial setting under smooth and convex loss functions and (ii) the optimal $ O(\frac{1}{T}) $ last-iterate convergence rate to a Nash equilibrium in multi-player smooth monotone games. As a byproduct of the accelerated last-iterate convergence rate, we further show that each player suffers only an $ O(\log T) $ individual worst-case dynamic regret, providing an exponential improvement over the previous state-of-the-art $ O(sqrt{T}) $ bound.

Type

Publication

Proceedings of the 40th International Conference on Machine Learning (ICML)

Click the *Cite* button above to demo the feature to enable visitors to import publication metadata into their reference management software.

Create your slides in Markdown - click the *Slides* button to check out the example.

Add the publication’s **full text** or **supplementary notes** here. You can use rich formatting such as including code, math, and images.