T. Lin, Z. Zhou, P. Mertikopoulos, and M. I. Jordan. In ICML '20: Proceedings of the 37th International Conference on Machine Learning, 2020.
We consider multi-agent learning via online gradient descent (OGD) in a class of games called $\lambda$-cocoercive games, a broad class of games that admits many Nash equilibria and that properly includes strongly monotone games. We characterize the finite-time last-iterate convergence rate for joint OGD learning on $\lambda$-cocoercive games; further, building on this result, we develop a fully adaptive OGD learning algorithm that does not require any knowledge of the problem parameter (e.g., the cocoercive constant $\lambda$) and show, via a novel double-stopping-time technique, that this adaptive algorithm achieves the same finite-time last-iterate convergence rate as its non-adaptive counterpart. Subsequently, we extend OGD learning to the noisy gradient feedback case and establish last-iterate convergence results – first qualitative almost sure convergence, then quantitative finite-time convergence rates – all under non-decreasing step-sizes. These results fill in several gaps in the existing multi-agent online learning literature, where three aspects – finite-time convergence rates, non-decreasing step-sizes, and fully adaptive algorithms – have not been previously explored.
arXiv link: https://arxiv.org/abs/2002.09806