Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games

Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, Michael Jordan
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:6161-6171, 2020.

Abstract

In this paper, we consider multi-agent learning via online gradient descent in a class of games called $\lambda$-cocoercive games, a fairly broad class of games that admits many Nash equilibria and that properly includes unconstrained 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 problem parameter (e.g. cocoercive constant $\lambda$) and show, via a novel double-stopping time technique, that this adaptive algorithm achieves same finite-time last-iterate convergence rate as 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. To our knowledge, we provide the first set of results that fill in several gaps of the existing multi-agent online learning literature, where three aspects–finite-time convergence rates, non-decreasing step-sizes, and fully adaptive algorithms have been unexplored before.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-lin20h, title = {Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games}, author = {Lin, Tianyi and Zhou, Zhengyuan and Mertikopoulos, Panayotis and Jordan, Michael}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {6161--6171}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/lin20h/lin20h.pdf}, url = {https://proceedings.mlr.press/v119/lin20h.html}, abstract = {In this paper, we consider multi-agent learning via online gradient descent in a class of games called $\lambda$-cocoercive games, a fairly broad class of games that admits many Nash equilibria and that properly includes unconstrained 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 problem parameter (e.g. cocoercive constant $\lambda$) and show, via a novel double-stopping time technique, that this adaptive algorithm achieves same finite-time last-iterate convergence rate as 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. To our knowledge, we provide the first set of results that fill in several gaps of the existing multi-agent online learning literature, where three aspects–finite-time convergence rates, non-decreasing step-sizes, and fully adaptive algorithms have been unexplored before.} }
Endnote
%0 Conference Paper %T Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games %A Tianyi Lin %A Zhengyuan Zhou %A Panayotis Mertikopoulos %A Michael Jordan %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-lin20h %I PMLR %P 6161--6171 %U https://proceedings.mlr.press/v119/lin20h.html %V 119 %X In this paper, we consider multi-agent learning via online gradient descent in a class of games called $\lambda$-cocoercive games, a fairly broad class of games that admits many Nash equilibria and that properly includes unconstrained 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 problem parameter (e.g. cocoercive constant $\lambda$) and show, via a novel double-stopping time technique, that this adaptive algorithm achieves same finite-time last-iterate convergence rate as 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. To our knowledge, we provide the first set of results that fill in several gaps of the existing multi-agent online learning literature, where three aspects–finite-time convergence rates, non-decreasing step-sizes, and fully adaptive algorithms have been unexplored before.
APA
Lin, T., Zhou, Z., Mertikopoulos, P. & Jordan, M.. (2020). Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:6161-6171 Available from https://proceedings.mlr.press/v119/lin20h.html.

Related Material