Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent

James P. Bailey, Gauthier Gidel, Georgios Piliouras
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:391-407, 2020.

Abstract

Gradient descent is arguably one of the most popular online optimization methods with a wide array of applications. However, the standard implementation where agents simultaneously update their strategies yields several undesirable properties; strategies diverge away from equilibrium and regret grows over time. In this paper, we eliminate these negative properties by considering a different implementation to obtain $O\left( \nicefrac{1}{T}\right)$ time-average regret via arbitrary fixed step-size. We obtain this surprising property by having agents take turns when updating their strategies. In this setting, we show that an agent that uses gradient descent with any linear loss function obtains bounded regret – regardless of how their opponent updates their strategies. Furthermore, we show that in adversarial settings that agents’ strategies are bounded and cycle when both are using the alternating gradient descent algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-bailey20a, title = {Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent}, author = {Bailey, James P. and Gidel, Gauthier and Piliouras, Georgios}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {391--407}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/bailey20a/bailey20a.pdf}, url = {https://proceedings.mlr.press/v125/bailey20a.html}, abstract = { Gradient descent is arguably one of the most popular online optimization methods with a wide array of applications. However, the standard implementation where agents simultaneously update their strategies yields several undesirable properties; strategies diverge away from equilibrium and regret grows over time. In this paper, we eliminate these negative properties by considering a different implementation to obtain $O\left( \nicefrac{1}{T}\right)$ time-average regret via arbitrary fixed step-size. We obtain this surprising property by having agents take turns when updating their strategies. In this setting, we show that an agent that uses gradient descent with any linear loss function obtains bounded regret – regardless of how their opponent updates their strategies. Furthermore, we show that in adversarial settings that agents’ strategies are bounded and cycle when both are using the alternating gradient descent algorithm.} }
Endnote
%0 Conference Paper %T Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent %A James P. Bailey %A Gauthier Gidel %A Georgios Piliouras %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-bailey20a %I PMLR %P 391--407 %U https://proceedings.mlr.press/v125/bailey20a.html %V 125 %X Gradient descent is arguably one of the most popular online optimization methods with a wide array of applications. However, the standard implementation where agents simultaneously update their strategies yields several undesirable properties; strategies diverge away from equilibrium and regret grows over time. In this paper, we eliminate these negative properties by considering a different implementation to obtain $O\left( \nicefrac{1}{T}\right)$ time-average regret via arbitrary fixed step-size. We obtain this surprising property by having agents take turns when updating their strategies. In this setting, we show that an agent that uses gradient descent with any linear loss function obtains bounded regret – regardless of how their opponent updates their strategies. Furthermore, we show that in adversarial settings that agents’ strategies are bounded and cycle when both are using the alternating gradient descent algorithm.
APA
Bailey, J.P., Gidel, G. & Piliouras, G.. (2020). Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:391-407 Available from https://proceedings.mlr.press/v125/bailey20a.html.

Related Material