English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider online learning in multi-player smooth monotone games. Existingalgorithms have limitations such as (1) being only applicable to stronglymonotone games; (2) lacking the no-regret guarantee; (3) having only asymptoticor slow $O(\frac{1}{\sqrt{T}})$ last-iterate convergence rate to a Nashequilibrium. While the $O(\frac{1}{\sqrt{T}})$ rate is tight for a large classof algorithms including the well-studied extragradient algorithm and optimisticgradient algorithm, it is not optimal for all gradient-based algorithms.  We propose the accelerated optimistic gradient (AOG) algorithm, the firstdoubly optimal no-regret learning algorithm for smooth monotone games. Namely,our algorithm achieves both (i) the optimal $O(\sqrt{T})$ regret in theadversarial setting under smooth and convex loss functions and (ii) the optimal$O(\frac{1}{T})$ last-iterate convergence rate to a Nash equilibrium inmulti-player smooth monotone games. As a byproduct of the acceleratedlast-iterate convergence rate, we further show that each player suffers only an$O(\log T)$ individual worst-case dynamic regret, providing an exponentialimprovement over the previous state-of-the-art $O(\sqrt{T})$ bound.

Doubly Optimal No-Regret Learning in Monotone Games