On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909524953137152 |
|---|---|
| author | Cai, Yang Farina, Gabriele Grand-Clément, Julien Kroer, Christian Lee, Chung-Wei Luo, Haipeng Zheng, Weiqiang |
| author_facet | Cai, Yang Farina, Gabriele Grand-Clément, Julien Kroer, Christian Lee, Chung-Wei Luo, Haipeng Zheng, Weiqiang |
| contents | Non-ergodic convergence of learning dynamics in games is widely studied recently because of its importance in both theory and practice. Recent work (Cai et al., 2024) showed that a broad class of learning dynamics, including Optimistic Multiplicative Weights Update (OMWU), can exhibit arbitrarily slow last-iterate convergence even in simple $2 \times 2$ matrix games, despite many of these dynamics being known to converge asymptotically in the last iterate. It remains unclear, however, whether these algorithms achieve fast non-ergodic convergence under weaker criteria, such as best-iterate convergence. We show that for $2\times 2$ matrix games, OMWU achieves an $O(T^{-1/6})$ best-iterate convergence rate, in stark contrast to its slow last-iterate convergence in the same class of games. Furthermore, we establish a lower bound showing that OMWU does not achieve any polynomial random-iterate convergence rate, measured by the expected duality gaps across all iterates. This result challenges the conventional wisdom that random-iterate convergence is essentially equivalent to best-iterate convergence, with the former often used as a proxy for establishing the latter. Our analysis uncovers a new connection to dynamic regret and presents a novel two-phase approach to best-iterate convergence, which could be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_02825 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games Cai, Yang Farina, Gabriele Grand-Clément, Julien Kroer, Christian Lee, Chung-Wei Luo, Haipeng Zheng, Weiqiang Machine Learning Computer Science and Game Theory Optimization and Control Non-ergodic convergence of learning dynamics in games is widely studied recently because of its importance in both theory and practice. Recent work (Cai et al., 2024) showed that a broad class of learning dynamics, including Optimistic Multiplicative Weights Update (OMWU), can exhibit arbitrarily slow last-iterate convergence even in simple $2 \times 2$ matrix games, despite many of these dynamics being known to converge asymptotically in the last iterate. It remains unclear, however, whether these algorithms achieve fast non-ergodic convergence under weaker criteria, such as best-iterate convergence. We show that for $2\times 2$ matrix games, OMWU achieves an $O(T^{-1/6})$ best-iterate convergence rate, in stark contrast to its slow last-iterate convergence in the same class of games. Furthermore, we establish a lower bound showing that OMWU does not achieve any polynomial random-iterate convergence rate, measured by the expected duality gaps across all iterates. This result challenges the conventional wisdom that random-iterate convergence is essentially equivalent to best-iterate convergence, with the former often used as a proxy for establishing the latter. Our analysis uncovers a new connection to dynamic regret and presents a novel two-phase approach to best-iterate convergence, which could be of independent interest. |
| title | On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games |
| topic | Machine Learning Computer Science and Game Theory Optimization and Control |
| url | https://arxiv.org/abs/2503.02825 |