Cycles in adversarial regularized learning

By Panayotis Mertikopoulos, Christos H. Papadimitriou, Georgios Piliouras. 2017

365 citations recorded by the source corpus.

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 Poincare 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.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Understanding and mitigating gradient pathologies in physics-informed neural networks (2020, background): “This result comes to no surprise, as it is well understood that gradient descent may get stuck in limit cycles or even diverge in the presence of multiple competing objectives [32, 33].”
Training GANs with Optimism (2017, background): “In fact recent theoretical results of Mertikopoulos et al. (2017) show the strong result that no variant of GD that falls in the large class of Follow-the-Regularized-Leader (FTRL) algorithms can converge to an equilibrium in terms of the last-iterate and are bound to converge to limit cycles…”
The Mechanics of n-Player Differentiable Games (2018, background): “Firstly, the potential existence of cycles (recurrent dynamics) implies there are no convergence guarantees, see example 1 and Mertikopoulos et al. (2018).”
The Unusual Effectiveness of Averaging in GAN Training (2018, background): “As a result, the time-average of the system converges fast, at a O (1 /T ) rate, to the solution of the saddle point problem (Mertikopoulos et al., 2018).”
Neural Replicator Dynamics (2019, methodology): “This yields the well-known Hedge [19] algorithm: Hedge is no-regret as long as Likewise, the continuous-time FoReL dynamics [41] are which in the case of entropy regularization yields RD as deﬁned in (1) (e.g., see [41]).”
On Convergence and Stability of GANs (2018, background): “Recent gametheoretic literature indicates that AGD can end up cycling (Mertikopoulos et al., 2017) or converging to a (potentially bad) local equilibrium, under some conditions (Hazan et al., 2017).”
Convergence of Learning Dynamics in Stackelberg Games (2019, background): “In the process of this endeavor, many negative results for algorithms and classes of games have been established that characterize the limits of what is achievable under this solution concept [6, 28, 30, 40].”
Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling (2020, background): “Perhaps the most prominent of these failures is the appearance of cycles [4, 6, 7, 20, 21] and, potentially, the transition to aperiodic orbits and chaos [3, 8, 28, 29, 31].”
Introduction to Multi-Armed Bandits (2019, neutral): “) A recent line of work (Bailey and Piliouras, 2018; Mertikopoulos et al., 2018; Bailey and Piliouras, 2018; Cheung and Piliouras, 2019) provides strong negative results, and a detailed investigation of the non-converging behavior.”
Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games (2020, background): “This was a well-known point that was only recently rigorously illustrated in Mertikopoulos et al. [2018b], where it is shown that even though follow-the-regularized-leader (another no-regret learning algorithm) converges to a Nash equilibrium in linear zero-sum games in the sense of time-averages,…”
Learning in games with continuous action sets and unknown payoff functions (2016, background): “nverge to a Nash equilibrium of the underlying game? Summary of contributions. In general, the answer to this question is a resounding “no”. Even in simple, ﬁnite games, no-regret learning may cycle (Mertikopoulos et al., 2018) and its limit set may contain highly non-rationalizable strategies that ”
On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games (2019, neutral): “A second promising line of research into theoretically sound methods of ﬁnding the Nash equilibria of zero-sum games has approached the issue from the perspective of variational inequalities (Mertikopoulos et al., 2018a; Gidel et al., 2018).”
The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization (2018, background): “Unfortunately, even when f ( x , y ) is convex-concave, it is rare that guarantees are known for the last iterate (see [17, 15, 13] for continuous time learning dynamics that may cycle).”
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2019, background): “However, there has been no shortage of research highlighting the fact that in a general setting GDA with equal stepsizes can converge to limit cycles or even diverge (Benaım & Hirsch, 1999; Hommes & Ochea, 2012; Mertikopoulos et al., 2018).”
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, background): “This work has focused on attaining improved rates [3, 4,19,21,26,29–31,41,45,48] and/or obtaining last-iterate convergence guarantees [1,2,13–15,20,22,28,35,37,38,43].”
Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile (2018, methodology): “A common theme in the above is that, to obtain a principled methodology for training GANs, it is beneficial to first establish improvements in a more restricted setting, and then test whether these gains carry over to more demanding learning environments.”
Tight last-iterate convergence rates for no-regret learning in multi-player games (2020, background): “Many other works ([HMC03, MPP17, KLP11, DFP + 10, BCM12, PP16]) establish similar non-convergence results in both discrete and continuous time for various types of monotone games, including zero-sum polymatrix games.”