Awesome

impossibility-global-convergence

Accompanying code for the paper: On the Impossibility of Global Convergence in Differentiable Games. Implements a number of multi-loss optimization methods that are shown to enter limit cycles instead of converging in a two-parameter zero-sum game, despite being weakly-coercive, analytic and nondegenerate. This includes (simultaneous) GD, AGD, EG, OMD, CO, SGA, LA, LOLA, SOS, and CGD.

This undesirable phenomenom is shown to apply more generally to any 'reasonable' algorithm in the paper, ruling out the possibility of global convergence guarantees in multi-loss optimization.

The notebook runs in ~2 minutes (without GPU accelerator). Use this link to open directly: https://colab.research.google.com/github/aletcher/impossibility-global-convergence/blob/master/impossibility_global_convergence.ipynb

Please find the bibtex citation for each algorithm in the bibtex.md file.