Cycles in adversarial regularized learning
This addresses the problem of understanding cycling dynamics in adversarial settings for researchers in online optimization and machine learning, but it appears incremental as it extends known concepts to networked competition.
The paper studied the behavior of regularized learning algorithms when competing against each other in zero-sum games, showing that the system's trajectories are Poincaré recurrent, meaning they revisit neighborhoods of their starting points infinitely often.
Regularized learning is a fundamental technique in online optimization, machine learning and many other fields of computer science. A natural question that arises in these settings is how regularized learning algorithms behave when faced against each other. We study a natural formulation of this problem by coupling regularized learning dynamics in zero-sum games. We show that the system's behavior is Poincaré recurrent, implying that almost every trajectory revisits any (arbitrarily small) neighborhood of its starting point infinitely often. This cycling behavior is robust to the agents' choice of regularization mechanism (each agent could be using a different regularizer), to positive-affine transformations of the agents' utilities, and it also persists in the case of networked competition, i.e., for zero-sum polymatrix games.