Fast Rates in Time-Varying Strongly Monotone Games

Yu-Hu Yan, Peng Zhao, Zhi-Hua Zhou
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:39138-39164, 2023.

Abstract

Multi-player online games depict the interaction of multiple players with each other over time. Strongly monotone games are of particular interest since they have benign properties and also relate to many classic games that have applications in real life. Existing works mainly focus on the time-invariant case with provable guarantees established. However, the research of the more general time-varying games in changing environments is underexplored and the best-known result cannot match the guarantees in the time-invariant case. In this work, we present a new decentralized online algorithm for time-varying strongly monotone games, which greatly improves existing results and obtains fast rates, matching the best time-invariant guarantee without knowing the environmental non-stationarity. Furthermore, to achieve faster rates, we generalize the RVU property with smoothness and establish a series of problem-dependent bounds that also match the best time-invariant one. To realize all those results, we make a comprehensive use of the techniques in non-stationary and universal online learning.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-yan23f, title = {Fast Rates in Time-Varying Strongly Monotone Games}, author = {Yan, Yu-Hu and Zhao, Peng and Zhou, Zhi-Hua}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {39138--39164}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/yan23f/yan23f.pdf}, url = {https://proceedings.mlr.press/v202/yan23f.html}, abstract = {Multi-player online games depict the interaction of multiple players with each other over time. Strongly monotone games are of particular interest since they have benign properties and also relate to many classic games that have applications in real life. Existing works mainly focus on the time-invariant case with provable guarantees established. However, the research of the more general time-varying games in changing environments is underexplored and the best-known result cannot match the guarantees in the time-invariant case. In this work, we present a new decentralized online algorithm for time-varying strongly monotone games, which greatly improves existing results and obtains fast rates, matching the best time-invariant guarantee without knowing the environmental non-stationarity. Furthermore, to achieve faster rates, we generalize the RVU property with smoothness and establish a series of problem-dependent bounds that also match the best time-invariant one. To realize all those results, we make a comprehensive use of the techniques in non-stationary and universal online learning.} }
Endnote
%0 Conference Paper %T Fast Rates in Time-Varying Strongly Monotone Games %A Yu-Hu Yan %A Peng Zhao %A Zhi-Hua Zhou %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-yan23f %I PMLR %P 39138--39164 %U https://proceedings.mlr.press/v202/yan23f.html %V 202 %X Multi-player online games depict the interaction of multiple players with each other over time. Strongly monotone games are of particular interest since they have benign properties and also relate to many classic games that have applications in real life. Existing works mainly focus on the time-invariant case with provable guarantees established. However, the research of the more general time-varying games in changing environments is underexplored and the best-known result cannot match the guarantees in the time-invariant case. In this work, we present a new decentralized online algorithm for time-varying strongly monotone games, which greatly improves existing results and obtains fast rates, matching the best time-invariant guarantee without knowing the environmental non-stationarity. Furthermore, to achieve faster rates, we generalize the RVU property with smoothness and establish a series of problem-dependent bounds that also match the best time-invariant one. To realize all those results, we make a comprehensive use of the techniques in non-stationary and universal online learning.
APA
Yan, Y., Zhao, P. & Zhou, Z.. (2023). Fast Rates in Time-Varying Strongly Monotone Games. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:39138-39164 Available from https://proceedings.mlr.press/v202/yan23f.html.

Related Material