Reproduce “Cycles in adversarial regularized learning” on OpenResearch

About this paper

Panayotis Mertikopoulos, Christos Papadimitriou, Georgios Piliouras

Mertikopoulos, Papadimitriou, and Piliouras demonstrate that continuous-time Follow the Regularized Leader (FoReL) dynamics in adversarial settings lead to perpetual cycling of strategies, rather than convergence to equilibrium. Their analysis shows that for two-player zero-sum games with interior Nash equilibria, FoReL dynamics are Poincaré recurrent, causing trajectories to return arbitrarily close to their starting points.

Key insights

• Fast regret minimization in adversarial settings does not necessarily lead to convergence to a fixed equilibrium, but rather to perpetual cycling of strategies.
• The analysis unifies various evolutionary game dynamics, such as replicator and projection dynamics, under the Follow the Regularized Leader (FoReL) framework, showing their shared characteristic of recurrent behavior.
• The inherent cycling behavior observed in these systems provides a theoretical explanation for training instabilities and non-convergence commonly seen in real-world applications like Generative Adversarial Networks (GANs).

Summary by alphaXiv.