Discretization Drift in Two-Player Games

Mihaela C Rosca, Yan Wu, Benoit Dherin, David Barrett
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:9064-9074, 2021.

Abstract

Gradient-based methods for two-player games produce rich dynamics that can solve challenging problems, yet can be difficult to stabilize and understand. Part of this complexity originates from the discrete update steps given by simultaneous or alternating gradient descent, which causes each player to drift away from the continuous gradient flow – a phenomenon we call discretization drift. Using backward error analysis, we derive modified continuous dynamical systems that closely follow the discrete dynamics. These modified dynamics provide an insight into the notorious challenges associated with zero-sum games, including Generative Adversarial Networks. In particular, we identify distinct components of the discretization drift that can alter performance and in some cases destabilize the game. Finally, quantifying discretization drift allows us to identify regularizers that explicitly cancel harmful forms of drift or strengthen beneficial forms of drift, and thus improve performance of GAN training.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-rosca21a, title = {Discretization Drift in Two-Player Games}, author = {Rosca, Mihaela C and Wu, Yan and Dherin, Benoit and Barrett, David}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {9064--9074}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/rosca21a/rosca21a.pdf}, url = {https://proceedings.mlr.press/v139/rosca21a.html}, abstract = {Gradient-based methods for two-player games produce rich dynamics that can solve challenging problems, yet can be difficult to stabilize and understand. Part of this complexity originates from the discrete update steps given by simultaneous or alternating gradient descent, which causes each player to drift away from the continuous gradient flow – a phenomenon we call discretization drift. Using backward error analysis, we derive modified continuous dynamical systems that closely follow the discrete dynamics. These modified dynamics provide an insight into the notorious challenges associated with zero-sum games, including Generative Adversarial Networks. In particular, we identify distinct components of the discretization drift that can alter performance and in some cases destabilize the game. Finally, quantifying discretization drift allows us to identify regularizers that explicitly cancel harmful forms of drift or strengthen beneficial forms of drift, and thus improve performance of GAN training.} }
Endnote
%0 Conference Paper %T Discretization Drift in Two-Player Games %A Mihaela C Rosca %A Yan Wu %A Benoit Dherin %A David Barrett %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-rosca21a %I PMLR %P 9064--9074 %U https://proceedings.mlr.press/v139/rosca21a.html %V 139 %X Gradient-based methods for two-player games produce rich dynamics that can solve challenging problems, yet can be difficult to stabilize and understand. Part of this complexity originates from the discrete update steps given by simultaneous or alternating gradient descent, which causes each player to drift away from the continuous gradient flow – a phenomenon we call discretization drift. Using backward error analysis, we derive modified continuous dynamical systems that closely follow the discrete dynamics. These modified dynamics provide an insight into the notorious challenges associated with zero-sum games, including Generative Adversarial Networks. In particular, we identify distinct components of the discretization drift that can alter performance and in some cases destabilize the game. Finally, quantifying discretization drift allows us to identify regularizers that explicitly cancel harmful forms of drift or strengthen beneficial forms of drift, and thus improve performance of GAN training.
APA
Rosca, M.C., Wu, Y., Dherin, B. & Barrett, D.. (2021). Discretization Drift in Two-Player Games. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:9064-9074 Available from https://proceedings.mlr.press/v139/rosca21a.html.

Related Material