Characterizing Lookahead Dynamics of Smooth Games
Authors: Junsoo Ha
Gunhee Kim
Venue:  (2021)
Keywords: Lookahead optimizer
game dynamics
smooth game

Abstract: As multi-agent systems proliferate in machine learning research, games have attracted much attention as a framework to understand optimization of multiple interacting objectives. However, a key challenge in game optimization is that, in general, there is no guarantee for usual gradient-based methods to converge to a local solution of the game. The latest work by Chavdarova et al. (2020) report that Lookahead optimizer (Zhang et al. (2019)) significantly improves the performance of Generative Adversarial Networks (GANs) and reduces the rotational force of bilinear games. While promising, their observations were purely empirical, and Lookahead optimization of smooth games still lacks theoretical understanding. In this paper, we fill this gap by theoretically characterizing Lookahead dynamics of smooth games. We provide an intuitive geometric explanation on how and when Lookahead can improve game dynamics in terms of stability and convergence. Furthermore, we present sufficient conditions under which Lookahead optimization of bilinear games provably stabilizes or accelerates convergence to a Nash equilibrium of the game. Finally, we show that Lookahead optimizer preserves locally asymptotically stable equilibria of base dynamics and can either stabilize or accelerate the local convergence to a given equilibrium with proper assumptions. We verify each of our theoretical predictions by conducting numerical experiments on two-player zero-sum (non-linear) games.

Under review as a conference paper at ICLR 2021
CHARACTERIZING LOOKAHEAD DYNAMICS OF SMOOTH GAMES
Anonymous authors Paper under double-blind review
ABSTRACT
As multi-agent systems proliferate in machine learning research, games have at- tracted much attention as a framework to understand optimization multiple in- teracting objectives. However, key challenge in game optimization is that, in general, there is no guarantee for usual gradient-based methods to converge to a local solution of the game. The latest work by Chavdarova al. (2020) report that Lookahead optimizer (Zhang et al. 2019) significantly improves the performance of Generative Adversarial Networks (GANs) and reduces the rotational force of bilinear games. While promising, their observations were purely empirical, and Lookahead optimization of smooth games still lacks theoretical understanding. In this paper, we fill this gap by theoretically characterizing Lookahead dynamics of smooth games. We provide an intuitive geometric explanation on how and when Lookahead can improve game dynamics in terms of stability and convergence. Furthermore, we present sufficient conditions under which Lookahead optimiza- tion of bilinear games provably stabilizes or accelerates convergence to Nash equilibrium of the game. Finally, we show that Lookahead optimizer preserves locally asymptotically stable equilibria of base dynamics, and can either stabilize or accelerate the local convergence to given equilibrium with proper assump- tions. We verify our theoretical predictions by conducting numerical experiments on two wwo-player zero-sum (non-linear) games.
INTRODUCTION
Recently, plethora of learning problems have been formulated as games between multiple inter- acting agents, including Generative Adversarial Networks (GANs) (Goodfellow al. [2014] Brock
et al. 2019; Karras et al. 2019), adversarial training (Goodfellow al. 2015: Madry et al. 2018)
self-play (Silver et al. 2018 [ansal et al., 2018), inverse reinforcement learning (RL) (Fu et al.)
2018) and multi-agent RL (Lanctot et al.] 20177; Vinyals al. 2019). However, the optimization of interdependent objectives is a non-trivial problem, in terms of both computational complexity (Daskalakis et al. 2006 Chen et al. 2009) and convergence to equilibrium (Goodfellow) 2017 Mertikopoulos et al.]
et al. 2018 Hsieh et al.) 2020). In particular, gradient- optimization methods often fail converge and oscillate around (local) Nash equilibrium of the game even in a very simple setting (Mescheder et al. 2018 Daskalakis et al.) 2018 Mertikopoulos al. 2019; Gidel al. 2019b a). To tackle such non-convergent game dynamics, huge effort has been devoted to developing efficient optimization methods with nice convergence guarantees in
smooth games (Mescheder al. 2017 2018 Daskalakis et al. 2018 Balduzzi et 2018 Gidel
et al. 2019b Schäfer & Anandkumar 2019 Yazici et al. 2019 Loizou et al. 2020).
Meanwhile, Chavdarova et al. (2020) have recently reported that the Lookahead optimizer (Zhang et al. 2019) significantly improves the empirical performance of GANs and reduces the rotational
force bilinear game dynamics. Specifically, they demonstrate that class-unconditional GANs trained by Lookahead optimizer can outperform class-conditional BigGAN (Brock et al.) 2019)
trained by Adam (Kingma Ba 2015) even with a model of 1/30 parameters and negligible com- putation overheads. They also show that Lookahead optimization of stochastic bilinear game tends to be more robust against large gradient variances than other popular first-order methods, and con- verges to Nash equilibrium of the game where other methods fail.

---

Under review as a conference paper at ICLR 2021
Despite its great promise, the study of Chavdarova al. (2020) relied purely empirical obser- vations, and the dynamics Lookahead game optimization still lacks theoretical understanding. Specifically, many open questions, such as the convergence properties of Lookahead dynamics and the impact of its hyperparameters on the convergence, remain unexplained. In this work, we fill this gap by theoretically characterizing the Lookahead dynamics of smooth games. Our contributions are summarized as follows:
We provide an intuitive geometric explanation on how and when Lookahead can improve the game dynamics in terms of stability and convergence to equilibrium.
We analyze the convergence of Lookahead dynamics in bilinear games and present suffi- cient conditions under which the base dynamics can be either stabilized or accelerated.
We characterize the limit points of Lookahead dynamics in terms of their stability and local convergence rates. Specifically, we show that Lookahead (i) preserves locally asymptoti- cally stable equilibria of base dynamics and (ii) can either stabilize or accelerate the local convergence to a given equilibrium by carefully choosing its hyperparameters.
Each of our theoretical predictions is verified with numerical experiments on two-player zero-sum (non-linear) smooth games.
PRELIMINARIES
We briefly review the objective of smooth game optimization, first-order game dynamics, and Lookahead optimizer. Finally, we discuss previous work on game optimization. We summarize the notations throughout this paper in Table A.I
2.1 SMOOTH GAMES
Following Balduzzi et al. 2018 a smooth game between players i = 1, can be defined set of smooth scalar functions ( with fr Id + R such that d' = Σ d. Each f; represents the cost of player i's strategy x; E R44: with respect to other players' strategies x- The goal of this game optimization is finding (local) Nash equilibrium of the game (Nash) 1951). which is strategy profile where no player has an unilateral incentive to change its own strategy.
Definition (Nash equilibrium). Let (fr) be a smooth game with strategy spaces {Rd J:= such that d Ei= dy Then x* E RRd a local Nash equilibrium of the game if, for each i = .,....".. there is neighborhood U; of x such that xx(x,,x,,) 2 f((x") holds for any E U, Such x² is said to be global Nash equilibrium of the game when U, Rd: for each i I.....m
A straightforward computational approach to find (local) Nash equilibrium of smooth game is to carefully design gradient- based strategy update rule for each player. Such update rules that define iterative plays between players are referred to as a dynamics of the game.
Definition (Dynamics of game). A dynamics of a smooth game {ft indicates a differentiable operator F pd + Id that describes players' iterative strategy updates as (t-1)) =xx(t)
One might expect that a simple myopic game dynamics, such as gradient descent, would suffice to find (local) Nash equilibrium of game in traditional minimization problems. However, in general, gradient descent optimization of smooth games often fail to converge and oscillate around an equilibrium of the game (Daskalakis al. [0188] Gidel et al. 2019b Letcher al. 2001)). Such non-convergent behavior of game dynamics is mainly due to (non-cooperative) interaction between multiple cost functions, and considered as key challenge in the game optimization (Mescheder
et al.
2017 7 2018 Mazumdar et al., 2019: Hsich et al. 2020).
2.2
FIRST-ORDER METHODS FOR SMOOTH GAME OPTIMIZATION
We introduce well-known first-order methods for smooth game optimization. To ease the notation, use V.f(-) to denote the concatenated partial derivatives (Vx. fi()..... Vx, f.)) of smooth game [f where f-)) is partial derivative of a player i's cost function with respective to its own strategy.
2

---

Under review as a conference paper at ICLR 2021
Gradient Descent (GD) minimizes the cost function of each player using the gradient descent. Its simultaneous dynamics F of a smooth game {f:] with a learning rate 17 > 0 is given by
(1+1) F' FDDs.m (xl*) oct ( ,)(x((('))
(I)
On the other hand, its alternating dynamies F A. is described by
(1+1)_ FEDAN (x(1) def Fi o ..... Fx(x()), where
(2)
F (..., Ij
v/
(3)
Proximal Point (PP) Martinet 1970) computes an update by solving proximal problem at cach
iteration. Its simultaneous dynamics F FrPs.. of a smooth game {f: (f,)== with learning rate 1) > 0s
(++1) FP
-)Vx((((*+))
(4)
Note that this update rule is implicit sense that x (++1) appears on both sides of the equation; hence it requires solving the proximal subproblem for ((++1) per iteration.
Extra Gradient (EG) (Korpelevich 1976) computes an update by using an extrapolated gradient.
Its simultaneous dynamics F FEGSH of smooth game {fi with learnnng rate n > 0 is
(++1) FEsS (x(1)= V/ [Vxx((((+)))
where
(5)
(++ x(1) V)(((())
(6)
2.3 LOOKAHEAD OPTIMIZER
Lookahead (Zhang et al. 2019) is recently proposed optimizer that wraps around a base optimizer and takes a backward synchronization step for each k forward steps. Given dynamics FA induced by base optimization method A, the Lookahead dynamics GLA-A with a synchronization period k E N and rate E (0, 1),1)s is
(1+1) = GLA-d(x(0) del (1 (1- a)xx)x + (x
2.4 RELATED WORK
The convergence analysis of first-order smooth game dynamics dates several decades back and have been established in the context of saddle-point problems (Rockafellar 1976) Korpelevich, 1976. Tseng 1995), which is special case of zero-sum games. For example, Rockafellar (1976) showed the linear convergence of PP in the bilinear and
(SCSC) saddle- point problems. Tseng 1995) and Facchinei Pang 2003) proved the linear convergence of EG in the same problem, and Nemirovski (2004) did in the convex-concave problem over compact sets.
As many learning problems are formulated as games in recent years (Goodfellow et al. 2014 Madry et al. 2018 Silver et al., [2018] Fu et al. 2018 Vinyals et al.) 2019), game optimization has regained considcrable attentions from the research community. Optimistic gradient descent (OGD) (Popov) efficient approximation of EG, was recently rediscovered in the
1980 which be seen context of GAN training (Daskalakis et al. 2018). Recent work of Liang & Stokes (2019) and Gidel
ct (2119)) proved linear convergence of OGD in bilinear and SCSC games. Mokktarr
(2020) established an unifying theoretical framework for analyzing PP, EG and OGD dynamics. Zhang &
Yu (202)) presented exact and optimal conditions for PP, EG and OGD dynamics to converge in
bilinear games. While there has been growing interest for incorporating second recond-order information
into game dynamics (Mescheder al.
2017
Balduzzi et al.) 2018 Mazumdar al.) 2019 Schhfee
& Anandkumar, 2019; Loizou et al. 2020 to remedy non-convergent behaviors, the first-order
optimization still dominates in practice (Brock et al. 2019 Donahue & Simonyan 2019) due to
computational and memory cost of second-order methods.
Lately, Chavdarova et al. (2020) reported that recently developed Lookahead optimizer (Zhang et al.) 2019 significantly improves the empirical performance of GANs and reduces the rotational force of bilinear game dynamics. However, this study relied on purely empirical observation and lacked the- oretical understanding for Lookahead optimization of smooth games. Although Wang et al. (2020) proved that Lookahead optimizer globally converges to a stationary point in minimization problems, its convergence in smooth games still remain an open question.
3

---

Under review as a conference paper at ICLR 2021
B 2
Forward
Forward
Backward
Forward
4
4
B x
4+
C
A (1,0)
5
C=
+ a
A (1,0)
C
ax
A (1.0)
-8
Backward
2_
Backward
A
x
(a) Eigenvalues of AD
(b) Eigenvalues of GD
(c) Figenvalues PP/EGsim
The spectral contraction effect of Lookahead dynamics in Equation 8 A the eigen- values of each base dynamics, and - + aλt are the eigenvalues of the associated Lookahead dynamics. k forward steps of Lookahead procedure first rotate the eigenvalues t of the dynam- ics' Jacobian matrix. Then, a synchronization backward step pulls them into a circle with a radius smaller than their maximal modulus. This results in reduced spectral radius of the Jacobian matrix, which improves stability and convergence to an equilibrium.
Figure 1:
3 SPECTRAL CONTRACTION EFFECT OF LOOKAHEAD IN BILINEAR GAMES
In this section, we show that Lookahead can either stabilize or accelerate the convergence of its base dynamics by reducing the spectral radius of its underlying Jacobian matrix. We highlight such spectral contraction effect by analyzing the convergence of Lookahead dynamics in a simple bilinear game (Section) 3.1). and extend the results to general bilinear games (Section 3.2
3.1 LOOKAHEAD DYNAMICS OF A SIMPLE BILINEAR GAME
We begin with simple exemplar bilinear game that has unique Nash equilibrium (0,0):
min max 21 T22- ER 2262
This game has been extensively studied as a representative toy example game optimization by Gidel et al. (2019a) due its oscillating dynamics. The following proposition demonstrates stabi- lization effect of Lookahead on Equation
Simultaneous GD dynamics F with a learning rate vj > diverges from the Nash equilibrium of Equation 8 However, its Lookahead dynamics GIA- with synchronization period k E N and a rate E (0, 1) globally converges to the Nash equilibrium if R[(1 + and a is small enough.
Proposition
iin) in)*)
[ that Lookahead optimizer can stabilize divergent dynamics of Equation 8 How- ever, such stabilization effect of Lookahead raises a natural question: would there be any advantage for using Lookahead when its base dynamics is already stable? Proposition analyzes well- known convergent PP dynamics of Equation g and presents an affirmative answer. Specifically, shows that Lookahead dynamics (i) preserves the convergence of its base dynamies, and (ii) can further accelerate the convergence with proper hyperparameter choices.
Proposition Simultaneous PP Lookahead dynamics GLA-PE... with a learning rate nj E (0. 1), synchronization period k. E N and rate E (0, 1) globally converges to the Nash equilibrium of Equation Furthermore, the rate of convergence improved upon its base dynamics F FP if R((1 + in) (1+ 12 and is large enough.
We provide geometric interpretation of the Lookahead procedure in Figure 1 Intuitively, Lookahead optimizer either stabilizes or accelerates its base dynamics by pulling the eigenvalues of the dynam- ics' Jacobian matrix into a circle with a small radius. Specifically, k forward steps of Lookahead procedure first rotate the eigenvalues, and a synchronization backward step pulls them into a circle with radius smaller than their maximal modulus. This results in reduction of the spectral radius of the dynamics' Jacobian matrix, which is known to crucial for stability (Slotine & Li 199I). Such spectral contraction effect of Lookahead dynamics is captured by the following lemma.
4

---

Under review as a conference paper at ICLR 2021
Lemma 3 (Spectral contraction effect of Lookahead). Let k N, E (0. 1) and define a function
mm + maxm by f(X) - (1 - a + ax. Define 0(A) del Arg(A* - 1) and Φ(2) def
arcsin ) Then, the following statements hold: Mxx
For x(X) 1, p(f( < X 1, AA E Amax (X).
For p(X) > L, p(f( < 1 R R(*a) L
20oa(=-((A))
AA A21 (X).
14--11
For p(X) 1, (X)( < <x(x* if R((2) p(x) .a21-
ond o(A))) 2x(x)*
14 -111
AY E Amax (X), YY, X(X).
In short, Lemma 3 suggests that Lookahead can reduce the spectral radius of a matrix by choosing a proper a and a k such that the entire uudus--suporrtis eigenvalues (e.g., 121(X), Amax are ro- tated to left enough. However, such k may not exist, for example, especially when such eigenvalues are not tightly clustered together. To help understanding when Lookahead can actually reduce the spectral radius, we present Lemma 4 as a sufficient condition for a set of eigenvalues to admit the existence that rotates them to the left half-plane.
Lemma 4 (Left-rotatable eigenvalues). Let X,J mm be such that X - nJ for some n and let S C X(X). Assume that each element of S has its conjugate pair in S. Then we have R(A*) < for each X E S if
(S)) 20mar(8)) and every element of S has non-zero imaginary part. Existence of such k N is guaranteed for small enough vj when 3max <. 3 (S)
3r
Note that the Jacobian matrix of most well-known gradient- based dynamics can be written in the form of nJ. where rj > a learning rate and J the underlying Jacobian matrix of the game. Intuitively, Lemma 4 suggests that for a small enough learning rate, any subser of the eigenvalues of a dynamics with imaginary conditioning less than 3 admits the existence k that rotates them left enough. For such k: Lookahead can reduce the spectral radius of the dynamics by choosing proper a, as stated in Lemma] This joint usage of Lemma plays a central role for the proofs of main results in Section 3.2 and Section 4 To summarize, Lemma 3 together highlight when Lookahead can actually improve the game dynamics and show that the imaginary conditioning of the radius- supporting eigenvalues is erucial for determining whether the dynamics is improvable.
3.2 LOOKAHEAD DYNAMICS OF GENERAL BILINNAR GAMES
In this section, we extend the analysis of Lookahead dynamics to general bilinear game
min max x Ax2 by'x by X2
E N2E
for some A E Rx and bj E RR,,b2 E R" such that there exists x E R E R" with A T x = b2 and Ax; = bj. The existence of x", x allows to rewrite the game
min max (x1 x
v (x2 x;),
(10)
XIER XER
where U,E, V is the SVD of A with rAnk(A). Therefore, we can analyze the dynamics of Equation 9 by inspecting a rather simpler problem
min max NI XaER
x Σ,
(11)
as they equivalent up to some rotations and translations. This reduction is a well-known tech- nique and has been used by Gidel et al. (2019bla) and Zhang & Yu (2020) for simplifying the analysis of Equation 9
Now we present sufficient conditions for Lookahead hyperparameters under which convergence of each first-order base dynamics, namely GDAU GD PP and EGsim is either stabilized or accelerated. The following first two theorems show that Lookahead can provably stabilize non- convergent GD dynamics of general bilinear games.
5

---

Under review as a conference paper at ICLR 2021
Theorem 5 (Convergence of GLA-GDA)) Lookahead dynamics GLA-GDas with learning rate ni
synchronization period k E N and a rate a E (0, converges to a Nash equilibrium 0, max
of Equation Saaationn
arccos - mod 2m # 0 for any o, E (A).
Theorem (Convergence of am. Lookahead dynamics GLA-GDao with a learning rate >> 0. a synchronization period & IN and a rate (0, 1) converges to Nash equilibrium of Equation
if le
3x
and is small enough.
Farctan min arcian 1/mmax
Roughly, Theorem 5 suggests that almost any configurations of Lookahead can make GDAlt conver- gent to a Nash equilibrium of the bilinear games. On the other hand, the existence of & that satisfies the condition of Theorem is guaranteed for small enough rj if dmms < 3 holds. This highlights min
limitation of the convergence guarantee for Sim that holds only for well-conditioned games.
The next two theorems show that Lookahead preserves the convergence of PP and EGisi in the bilinear games, and can further accelerate their convergence under proper hyperparameter choices.
Theorem (Acceleration of GLA-PPsm... Lookahead dynamics GLA-PP with a learning rate ni >> O, a synchronization period k. E N and rate a E (0,1) converges to Nash equilibrium of Furthermore, the rate of convergence is accelerated upon its base dynamics F Frrs.. if
Equation 9
) and a is large enough.
Saretan min" Farctan min
Theorem 8 (Acceleration of GLA.FGgu.). Lookahead dynamics GIA-EGs.. with learning rate n synchronization period l N and rate E (0, converges to Nash equilibrium of Equation Furthermore, the rate of convergence accelerated upon its base dynamics F FEGS if
00 mmax
1 E
(0:2mmax)
2ermax ) Paretan
and a is large enough.
min 10
arrtan
min
Note that the existence of k that satisfies the acceleration conditions of Theorem is always guaranteed for a small enough 7). This contrasts Theorem 7 with Theorem 6 to well-conditioned games, and suggests that they can be applied for a wide range of bilinear games, including the ell-conditi ones.
g
which only applies
THE LIMIT POINTS OF LOOKAHEAD DYNAMICS
In this section, we characterize the limit points Lookahead dynamics and reveal the connections between their stability and the hyperparameters of Lookahead. We start by defining few stability concepts which are standard in the dynamical system theory (Slotine & Li 1991).
Definition (1 yapunov stability). Let F be smooth vector field on R." Then x E TR. is Lyapunov
stable in F if for any > O, there exists > O such that for any y E TRn |x -xyll < 5 implies [FF (((x))FF(())) (y)l < ffror all E N.
Definition 4 (Asymptotic stability). A Lyapunov stable equilibrium x E R of a smooth vector field F is said to be asymptotically stable if there exists 5 0 such that ||x x" < 8 implies Such x" is said to be locally asymptotically stable if 8 < oc.
lim | 10000
We show that any Lyapunov stable equilibrium (SE) a dynamics a locally asymptotically stable equilibrium (LASE) of a Lookahead dynamics. Furthermore, we show that Lookahead can either stabilize or accelerate the local convergence to an equilibrium when the radius-supportig eigenval- ues of the equilibrium satisfy certain assumptions
their imaginary parts.
Theorem (SE C LASELA-A)- Xetx" E R be Lyapunov stable equilibrium of dynamics F. Then, x" is LASE of its Lookahead dynamics G with a synchronization period k E N and rate (0, 1) X + for each X; >(VxF(x*))
T be an equilibrium of a dynamics F with 1. Assume that every element of \>1((V x" is LASE of its Lookahead dynamics G with synchronization period k E 1 and a rate a E (0.1) and a is small enough.
Theorem 10 (One-point local stabilization). Let x* E ER
F(xF((x*)
has non zero imaginary part. Then,
if k
3m
28 Mmin (V,F( 29marl (g (V.F

---

Under review as a conference paper at ICLR 2021
Theorem 11 (One-poine local acceleration). Letx" F()F((x*) < 1. Assume that every element of Amac (xz(xx") has non-zero imaginary part. Then, the local convergence rate to x" in a Lookahead dynamics G with synchronization period k E N
IR" be an equilibrium of dynamics F with
and a rate E (0, 1) is accelerated upon F if large enough.
3m 20 min! Amax F(x")) 20max Dmaax V F(x*)))
and
Intuitively, Theorem shows that Lookahead preserves stability of its base dynamies, and Theorem
10 11 suggest that Lookahead can either stabilize or accelerate the local convergence to an equi-
librium. Note that the stabilization and acceleration can be guaranteed when A²1 (>1 xx'(xx)) and
Amax (VxF(x*)) contain real eigenvalues and have imaginary conditioning less than 3: otherwise,
that satisfies the conditions of Theorem I0 may not exist (see Appendix E.10 E.11
An additional, but important consequence of Theorem 10 is that the inclusion relationship implied by Theorem is strict in general. In the context of Nash equilibrium (NE) computation, such stabilization effect of Lookahead can be helpful when unstable NE are stabilized (e.g., bilinear games). However, the stabilization effect also carries a possibility for introducing non-Nash LASE, which is bad for the NE computation (Mazumdar et al. 2019). Hence, the overall impact of Theorem 10 on the computation NE depends on the global structure of the game and base dynamics.
Note that Theorem 10 require aadius-supporting cigenvalues to have non-zero imaginary parts and therefore does not apply to fully-cooperative (FC) games (i.e., minimization problems), which exhibit real eigenvalues only. To give understanding of Lookahead dynamics in FC games, present Proposition 13 together which imply that the iterates Lookahead dynamics almost surely avoids unstable equilibria of its base dynamics in FC games (e.g., avoids local maxima).
Proposition 12 (Avoids unstable points). Let F be L-Lipschitz smooth dynamics for some L > and let G be its Lookahead dynamics with a synchronization period k E N and a rate a (O. T+TE) Then the diitta--n iterates of G almost surely avoids its equilibrium x* with p(V,G(x*) 1 (VVx(()) + 1 holds for any equilibrium Xo of G.
Proposition 13 (Preserves unstable points in FC games). Let x" E R. be an equilibrium of dynamics F with (V, F(x))) eigenvalues. Then, p( ((r))()) period l E N and a rate E (0, 1).
))² > 1, and assume that F(F"x") is a symmetric matrix with positive
1 holds for Lookahead dynamics G with a synchronization
EXPERIMENTS
10a
LA-GD
Distance to (0,0)
LA-GD
Distance to NE
10a
LA-GDjr
10a
LA-GD
10F
GDAI
LA-GDia
10
GD
LA-GD
10-1
LA-GD5in
LA-GD
10-3
GDam
GDsm
10
EG
LA-EG3
LA-EG
LA-EGjm
400
600 Iterations
800
1000
1200 1400
EGsm
500
Iterations
1000
1500
2000
2500
EGsm
(a) Convergence the NE of the bilinear game.
(b) Convergence (0, in the nonlinear game.
Figure 2: Optimization progress of multiple first-order methods with hyperparameters chosen by (+) and against our theorems (-) in the bilinear and nonlinear games.
Bilinear game. We test our theoretical predictions in Section 3.2 (Therrem
8 on bilinear game
min max x Ax X ER R
(12)
with A I, + E,, where each element of E,, E M,xn is sampled from (0,0 1). We report our results using n 10 and 0.05, which gives sample of A with Faax 1.195 and Jmin 0.852, hence Amux 1.401 < 3. For fixed 1) = 0.1, we use Theorem 51g to derive range of k min

---

Under review as a conference paper at ICLR 2021
LA-GDAr
LA-GDAr LA-GOGm LA-EG
LA-GD5im
LA
2
-2
-2
-2
-2
(a) Trajectories of cach Lookahead dynamics with Ae and a predicted by Theorem aOl
(b) Trajectories of cach Lookahead dynamics with k and a chosen against Theorem TO T0aad
I
Figure 3: Visualized trajectories of each dynamics an equilibrium (0,0) of the nonlinear game.
and an approximate scale of that guarantee stabilization and acceleration of convergence to Nash equilibrium (NE) of Equation [2] We provide the derivations of theoretically recommended values and actual configurations used for the experiment in Appendix D Figure (a) shows that the hyperparameters predicted by our theorems, denoted by LA--GDAwsim and LA-EGsim* actually stabilize and accelerates the convergence against our thcorems and denote as LA-GD AluSim and LA-EGsim smaller than the lower bound predicted by theorems and use large for unstable base dynamics and small a for stable base dynamics. The result in Figure (a) suggests that Lookahead can fail to stabilize, even worse, slow down the convergence when hyperparameters configured badly.
NE. We also test the hyperparameters that are chosen
Specifically, we choose a
Nonlinear game. We verify our theoretical predictions Section (Theorem 10 and on the non-linear game proposed by Hsieh et al. (2020):
min max #1 D2 + E0(x2). at mrER Z2ER
(13)
where (bxr) def _ - 1 a. with 0. This game has an unstable critical point (0, 0) surrounded by attractive internally chain-transitive (ICT) set, which may contain arbitrarily long trajectories. [Hiic et al. (2020) demonstrate that most first-order methods fail to converge in this game due to the instability of the equilibrium and the existence of the ICT set. For fixed 0.01 and 0.05, use Theorem and [T to derive range of I and an approximate scale of a that guarantee local sta- bilization and acceleration the equilibrium of Equation [3] We provide the detailed derivations of the theoretically recommended values and the configurations in Appendix D Figure (b) and Fig- ure 3 (a) shows that the hyperparameters predicted by our theorems, denoted by
AluSim and LA- LA-EGSim + actually stabilize and accelerates the convergence to the equilibrium. In contrast, hy- perparameters chosen against our theorems, denoted by LA-GD AIASii and LA-EGsim Figure 2 (b) and Figure 3 (b), neither success to stabilize nor accelerate the convergence to the equilibrium.
6 CONCLUSION
In this work, we derived the theoretic results for convergence guarantee and acceleration of Looka- head dynamies in smooth games for the first time. Specifically, derived sufficient conditions for hyperparameters of Lookahead optimizer under which the convergence of bilinear games is either stabilized or accelerated. Furthermore, asymptotically stable equilibria of smooth games. Finally, we showed that Lookahead can either stabilize or accelerate the local convergence to a given equilibrium under proper assumptions.
proved that the Lookahead optimizer preserves locally
Our results point to several future research directions. Lemma 4 suggests that the imaginary con- ditioning of the rapposssu eigenvalues is crucial for the performance gain in Lookahead. Therefore, developing convergence of its Lookahead dynamics. Another interesting application of our theoretic results would be designing an adaptive mechanism for the Lookahead hyperparameters by applying our theorems on local bilinear approximation (Schäfer & Anandkumari 2019) of the game for each step.
optimizer that exhibits small imaginary conditioning could improve the
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Waiss Azizian, Damien Scieur, Ioannis Mitliagkas, S. Lacoste-Julien, and Gauthier Gidel. Acceler- ating smooth games by manipulating spectral shapes. In AISTATS, 2020.
D. Balduzzi, Sébastien Racanière, Martens, Jakob N. Foerster, K. Tuyls, and Graepel. The Mechanics of n-Player Differentiable Games. In ICML, 2018.
Trapit Bansal, Jakub W. Pachocki, S. Sidor, Ilya Sutskever, and Igor Mordatch. Emergent Complex- ity via Multi-Agent Competition. In ICLR, 2018.
D.P. Bertsekas. Nonlinear Programming. Athena Scientific, 1999.
A. Brock, J. Donahue, and K. Simonyan. Large Scale GAN Training for High Fidelity Natural Image Synthesis. In ICLR, 2019.
Tatjana Chavdarova, Mattco Pagliardini, M. Jaggi, and Franois Fleuret. Taming GANs with Looka- head. ArXiv, 0oss2006.115661 2020.
C. Chen. Linear System Theory and Design. Oxford University Press, 1995.
X. Chen, X. Deng, and S. Teng. Settling the Complexity of Computing Two-player Nash Equilibria. J. ACM, 56: 14:11445 2009.
C. Daskalakis and loannis Panageas. The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization. In NeurlPS, 2018.
C. Daskalakis, P. Goldberg, and C. Papadimitriou. The Complexity of Computing Nash Equilib- rium, Electron. Colloquium Comput. Complex., 2006.
C. Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with Optimism. In ICLR, 2018
Donahue and K. Simonyan. Large Scale Adversarial Representation Learning. NeurIPS, 2019.
F. Facchinei and J. Pang. Finite-Dimensionl Variational Inequalities and Complementarity Prob- lems. Springer, 2003.
Justin Fu, Katie Luo, and S. Levine. Learning Robust Rewards with Adversarial Inverse Reinforce- ment Learning. In ICLR, 2018.
Gauthier Gidel, Hugo Berard, Pascal Vincent, and S. Lacoste- A Variational Inequality Per- spective on Generative Adversarial Nets. In ICLR, 2019a.
Gauthier Gidel, Reyhane Askari Hemmat, M. Pezeshki, Gabriel Huang, Rémi Le Priol, S. Lacoste- Julien, and Ioannis Mitliagkas. Negative Momentum for Improved Game Dynamics. AISTAT, 2019b.
Ian J. Goodfellow. NIPS 2016 Tutorial: Generative Adversarial Networks. ArXiv, abs/ 700.000660 2017.
Ian J. Goodfellow, Jean Pouget-Abadie, M. Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative Adversarial Nets. In NIPS, 2014.
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adversarial Examples. CoRR, abs/1412.6552. 2015.
Ishaan Gulrajani, F. Ahmed, Martín Arjovsky, Vincent Dumoulin, and Aaron C. Courville. Improved training of wasserstein gans. ArXiv, abs/1704.00028. 2017.
Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. The Limits of Min-Max Optimization Algorithms: Convergence to Spurious Non-critical Sets. ArXiv,
2020.
Tero Karras, S. Laine, and Timo Aila. A Style-Based Generator Architecture for Generative Adver- sarial Networks. In CVPR, 2019.

---

Under review as a conference paper at ICLR 2021
Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In ICLR, 2015.
G. M. Korpelevich. The Extragradient Method for Finding Saddle Points and Other Problems. Ekonomika Matematicheskie Metody, 12:747-756, 1976.
Mare Lanctot, V. Zambaldi, A. Gruslys, A. Lazaridou, K. Tuyls, Julien Pérolat, D. Silver, and T. Graepel. A Unified Game-Theoretic Approach Multiagent Reinforcement Learning, In NeurlPS, 2017.
J. Lee, Ioannis Panageas, G. Piliouras, Max Simchowitz, Michael I. Jordan, and B. Recht. First-order methods almost always avoid saddle points. NeurIPS, 2019.
Alistair Letcher, D. Balduzzi, Sébastien Racanière, J. Martens, Jakob N. Foerster, K. Tuyls, and T. Graepel. Differentiable Game Mechanics. JMLR, 20:1-40, 2019.
Tengyuan Liang and J. Stokes. Interaction Matters: A Note Non-asymptotic Local Convergence of Generative Adversarial Networks. AISTATS, 2019.
N. Loizou, Hugo Berard, Alexia Jolicoeer--arriieauu Pascal Vincent, S. Lacoste-Julien, and loannis Mitliagkas. Stochastic Hamiltonian Gradient Methods for Smooth Games. In ICML, 2020.
A. Madry, Aleksandar Makelov, L. Schmidt, D. Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. In ICLR, 2018.
B. Martinet. Brève Communication. Régularisation d' d'inéquations Variationnelles par Approxima- tions Successives. ESAIM: Mathematical Modelling and Numerical Analysis Modélisation Muthématique et Analyse Numérique, 4(R3):154-155 1970.
Eric V. Mazumdar, Michael I. Jordan, and S. Sastry. On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games. ArXiv, abs/1901 0bs//101..0083, 2019.
Mertikopoulos, C. Papadimitriou, and G. Piliouras. Cycles in Adversarial Regularized Learning. In SODA, 2018.
Mentikopoulos, Houssam Zenati, Bruno Lecouat, Chuan-Sheng Foo, V. Chandrasekhar, and G. Piliouras. Mirror descent in saddle-point problems: Going the extra (gradient) mile. ArXiv, hss/1807.02629 2019.
Lars M. Mescheder, Sebastian Nowozin, and Andreas Geiger. The Numerics of GANs. In NIPS, 2017.
Lars M. Mescheder, Andreas Geiger, and Sebastian Nowozin. Which Training Methods for GANs do actually Converge? In ICML, 2018
Aryan Mokhtari, A. Ozdaglar, and Sarath Pattathil. A Unified Analysis of Extra-gradient and Op- timistic Gradient Methods for Saddle Point Problems: Proximal Point Approach. In AISTATS. 2020.
Cristinel Mortici and Hary M Srivastava. Estimates for the Arctangent Function Related to Shafer's Inequality. Collog. Math, 136(2):263-215 2014.
Nash. Non-Cooperative Games. Annals of Mathematics, 54:286, 1951.
A. Nemirovski. Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems. SIAM J. Optim., 15:229 221, 2004.
L. Popov. modification of the arrow-hurwiez method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28:845-848, 1980.
R. T. Rockafellar. Monotone Operators and the Proximal Point Algorithm. Siam Journal Control and Optimization, 14:877-898, 1976.
Tim Salimans, Ian J. Goodfellow, W. Zaremba, Vicki Cheung, A. Radford, and Xi Chen. Improved techniques for training gans. ArXiv, abs/1 (ts/1606.03498. 2016.
10

---

Under review as a conference paper at ICLR 2021
Florian Schäfer and Anima Anandkumar. Competitive Gradient Descent. In NeurIPS, 2019.
D. Silver, T. Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, A. Guez, Marc Lanctot, L. Sifre, D. Kumaran, T. Graepel, T. Lillicrap, K. Simonyan, and Demis Hassabis. A General Re- inforcement Learning Algorithm That Masters Chess, Shogi, and Go Through Self-play. Science, 362: 1100 144, 2018.
J. Slotine and W. Li. Applied Nonlinear Control. Pearson, 1991.
P. Tseng. On Linear Convergence of Iterative Methods for the Variational Inequality Problem. Journal of Computational and Applied Mathematics, 60:237-252, 1995.
Oriol Vinyals, Babuschkin, W. Czarnecki, Michaël Mathieu, A. Dudzik, Chung, D. Choi, R. Powell, Timo Ewalds, P. Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Dani- helka, Aja Huang, L. Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg, A. S. Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, D. Budden, Yury Sulsky. James Molloy, L. Paine, Caglar Gulcehre, Ziyu Wang, T. Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, O. Smith, T. Schaul, Lillicrap, Kavukcuoglu, Demis Hassabis, Chris Apps. and D. Silver. Grandmaster Level in StarCraft II using Multi-agent Reinforcement Learn- ing. Nature, pp. 1-5, 2019.
Jianyu Wang. Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Lookahead Converges to Sta- tionary Points of Smooth Non-convex Functions. In ICASSP, 2020.
Yasin Yazici, C. S. Foo, S. Winkler, Kim-Hui Yap, G. Piliouras, and V. Chandrasekhar, The Unusual Effectiveness of Averaging in GAN Training. In ICLR, 2019.
Guojun Zhang and Y. Yu. Convergence of Gradient Methods on Bilinear Zero-Sum Games. In ICLR, 2020.
M. Zhang, Lucas, Geoffrey Hinton, and Jimmy Ba. Lookahead Optimizer: k Steps Forward, Step Back. In NeurlPS, 2019.
11

---

Under review as a conference paper at ICLR 2021
A
NOTATION
Table A.I: List of mathematical notations used in the paper.
Symbol
Definition
IH-I1
T,2 norm
i-th clement of a vector x = (#1,.... En)
X;
i-th vector of concatenated vectors (x1....,Kn)
x
(X1...., X;-1, X.+1,..., X..)
Derivative of function evaluated x
S.
The zero-centered circle of radius r > 0 0 C
R(z)
Real part of E C
((z)
Imaginary part of E C
Arg(z)
The angle between E C and real axis of the complex plane The set of singular values of A E R
(A)
(A)
The spectral radius of A | The set of eigenvalues of A RR The set of eigenvalues of A with modulus larger than or equal to a E IR The set of eigenvalues of A with the largest modulus
((A)
Aza(A A)
Amax
R(S)
[R(c)]ee E S} for S _
min
min R()
R (S)
max R(S)
(S))
(S(c)le S) for SCC
(20(S)
(S, E ((8) 2 0}
min (S)
min (S)
max (S)
max (z)(S)
(()
c for S CC
(S)
(0,10 E ((S), 20
0 min (S)
min (S)
max (S)
max (S)
B USEFUL FACTS
B. STANDARD RESULTS ON CONVERGENCE
Lemma 14 (Bertsekas (1999)). Let F R m + R be continuously differentiable, and let E R be such that F(x') = x". Assume that p(V, F(x)) 1. Then, there an open neighborhood Ux- of x" such that for any x E Ur., F xx'll, ((x)) for
Lemma 15 Giieel et al. (2019))). Let M Rm and (t) be a sequence of iterates such that, u (++1) Mu M) then have three cases of interest for the spectral radius p(M):
If P(M) < 1 and M is diagonalizable/ then ( O(((M)
|0t 112)
If P(M) 1, then there exists u (0) such that || [(p(MM) (,())
IfAA 1, VA, A(M), and M is diagonalizable, then (12 @(Ilu(")),))
B.2 CHARACTERISTIC EQUATIONS OF FIRST-ORDER DYNAMICS IN BILINEAR GAMES
Latest work of Zhang& & Yu (020) provides the exact and optimal conditions for popular first-order methods converge in zero-sum bilinear games, if possible. Besides from the exact conditions and the choice of optimal hyperparameters, they also derive the characteristic equation of each first- order dynamics in the zero-sum bilinear games, Since our proofs of theorems in Section 3.2 heavily
AAtuallyy M does have be diagonalizable; Theorem 5.4 and Theorem 5.D4 Chen 1995
12

---

Under review as a conference paper at ICLR 2021
rely on these characteristic equations, restate somewhat simplified version of the equations for using our notations.
Equation
GDAIl: (A; (A,- 1)2 + 1/ - =0
(14)
GDsim (A; - 1)2 + +1000 =0
(15)
Pi (1/A; - 1)² + +
(16)
EGAI: 1 + (1/" (A + (v/0² + , = 0.
(17)
EGsim (A, 2npp== r
(18)
We denote the singular values of matrix A in Equation by o. The eigenvalues of each dynamics'
Jacobian matrix denoted by d Note that Zhang & Yu 2020) also derive characteristic equations of memory-auggeent first-order methods, such as OGD (Popov 1980) and the momentum method, which we do not cover in this paper.
C OMITTED RESULTS
Proposition 16. Alternating GD dynamics F F.D. with a learning rate E (0, 2) fails to converge
and oscillates around the Nash equilibrium of the game in Equation 8 However its Lookahead dynamics GLA-GDa, with synchronization period k E N and rate a E (0, 1) globally converges to
k
the Nash equilibrium if (1 (1- 3 1-
#1
Proof. One easily check from Equation 2 that the dynamics FGD can be written
[ [] 1
(
F FaD (1 (1) x
(19)
17
1 - 17
22
Defining M def
1
-1
the Lookahead dynamics GLA.-GDA be written
11 1 - 1/2
GLA (9) 20)) ) ((1 a) +
(20)
follows that the eigenvalues of V.GLAGG can be written as a at with A del
+
i/4-1² E X(M) for any 7 (0,2) However, 1 - a is interpolation between two distinct points on S1 since | and X + 1, implying
a + a 1. Therefore, we conclude from Lemma 14 that the iterates of GLA-GDa converge to the Nash equilibrium (0,0) of the game
with convergence rate O(]1 + I assuming the amortization of its computation over k forward steps. The proof for oscillation of F. follows from Lemma 15 and can be found in Gidel et al. (2019a).
Proposition 17. Simultaneous EG Lookahead dynamics GLA-EGen. with a learning rate n E (0, synchronization period N and a rate E (0, 1) globally converges the Nash equilibrium of Equation S Furthermore, the rate of convergence is improved upon its base dynamics F FEGua if
R((1 2 +n < 112 of a/a and a is large enough.
Proof. Using simple algebra on Equation 5 the dynamics F Fuis can be written
F EGGsi
(1 22
(t)
(0)
[
[
172
(21)
1-
Defining M del 1+n "
-17
its Lookahead dynamics GLAEGGn with a synchronization
1- 1
period l E N and rate
(0, can be written as
(t) x
GLA-GOo (
(0) ((1 a) +a)
(22)
I
13

---

Under review as a conference paper at ICLR 2021
follows that the eigenvalues of V,GLA EGsm are + ati with b def 1- in E A(M). However, - a at is an interpolation between two distinct points on/inside S since |* l for any 77 E (0, 1). It follows that [1 - + a < 1, from which we conclude from Lemma 14 that the iterates of G FGs.. converge the Nash equilibrium (0, 0) of the game with convergence rate O(11 at= ) assuming the amortization of its computation over k forward steps.
Now show that the convergence is accelerated upon its base dynamics FEGSO. if RR(( 17 + in) (1 17² )²* and is large enough. Figure 1 (c) intuitively shows that the line segment between (1,0) and X contains line segment inside 1| when such that R( | Therefore, for a large enough the interpolation - a + a lies inside SIa+ This implies that the convergence rate O(J1 - a + a ((/k) of GLA-EGss.. is accelerated upon the rate ((>+1') of its base dynamics.
Proposition 18 (Equilibrium of Lookahead dynamics), Let F be dynamics and G be its associ- ated Lookahead dynamics with a synchronization period k E N. Then any equilibrium of F is an equilibrium of G and any equilibrium of G is periodic point of F.
Proof. Let k E N and (0. 1) be the synchronization period and synchronization rate of G.
respectively. It is trivial to see that G(x*) = ((1 a)id + a= (x*) = aaxx + axx = x" F(x") x". Conversely, F
easily check that G(x²) a)xx oF aF*(x*) = implies
D EXPERIMENTAL DETAILS
We report the actual hyperparameters used for the experiments of Section 5 in T.bldD22 and D.3 Furthermore, we also provide the detailed derivations the theoretically recommended range of synchronization period & E N.
Table D.2: Hyperparameters used for the experiment on the bilinear game
Configuration
k (Theorem
(Theorem
CK
LA-GDAR Al
N
25
(0, 1)
0.1
LA-GDA Alt
N
5
10,
0.9
LA-GDsim
(18.47,39.65)
25
small enough
0.1
LA-GDsim
(18.47, 1.4479990 39.62)
5
small enough
0.9
LA-EGsim
(16.9, 34.93)
25
large enough
0.9
LA-EGsim
(16.9, 34.93)
5
large enough
0.1
Table D.3: Hyperparameters used for the experiment on the nonlinear game
Configuration
(Theorem
k
(Theorem 10 11
a
LA-GDAR
(31.16, 93.49)
35
small enough
0.1
LA-GDAI
(31.16, 93.49)
small enough
0.9
LA-GD
(31.6, 94.81)
35
small enough
0.1
LA-GD LA-GDsim
(31.6, 94.81)
small enough
0.9
LA-EGE LA-EGsim
(121.76, 365.00)
175
large enough
0.9
LA-EGsim
1121.76, 365.30)
large enough
0.1
D.1 DERIVATION OF THEORETICALIS RECOMMENDED RANGE OF & IN EQUATION
12
We plug in (A) = (1.195, 1.163, 1.094, 1.094, 1.018, 0.999, 0.969, 0.888, 0.879, 0.852) with maxx 1.195 and amin 0.852 Theorem 58 Then have
14

---

Under review as a conference paper at ICLR 2021
0.1 2
LA-GDAiE {k E (arcoos(
mod π + 0, Va,).
LA-GDsimi (2arctnn Zaretan 6.12
3r
(18.47, 39.62),
LA-EGsami 2 h 0.09* 2 aarttan 0.13)
3x
(16.9, 34.93).
which give ranges for k as in T.b
D.2 DERIVATION OF THEORETICALLI RECOMMENDED RANGE OF k IN EQUATION
13
LA-GDAH
From Equation 2 the Jacobian of dynamics FLA of Equation 13
can be derived as
Vx GD.
= " 17² ne(1 3x2)
7
x
(23)
12
and it trivial to see that has an equilibrium at (), By plugging e 0.01 and v = 0.05, we
obtain
-0.05
V.F CD (0,0)
(24)
0.05
0.998
0.99 + 0.05i. Note that |^+| 1.0003 1 and F.DaD.. 00 has the with eigenvalues X def
imaginary conditioning of 1, which implies that the origin an unstable equilibrium of GD that can be locally stabilized by Lookahead dynamics. By plugging in the eigenvalues and minnn (VxF FaD,, (0, 0)) - maxx mnax(Ve /V (0, 0)) arctan 0.05
0.0504 to Theorem 10 we obtain
0.99
the theoretically recommended range
(31.16, 981.16,33.49)
LA-GD Sim
From Equation 1 the Jacobian of dynamics FLA-GDaIn of Equation
13 can be derived
as
V VxF GDsm (21, x2)
=
[7 1+ ne(1
3x22)
x2
(25)
and it trivial to see that has an equilibrium (0, By plugging 0.01 and r) = 0.05, we obtain
-0.05
FGD... (0,0)
(26)
0.05
1.005
with eigenvalues A def 1.0025 + 0.0499i. Note that |^_| 1.0037 > and F.Daa (0.0)
has the imaginary conditioning of 1, which implies that the origin is an unstable equilibrium of GD that be locally stabilized by a Lookahead dynamics. By plugging in the eigenvalues
and O ( V ED (0, 0)) = 0max V GD&.. (0, 0)) arctan I 0025
0.0499 0.0497 to Theorem 10 we
obtain the theoretically recommended range of l: as (31.6, 94.81).
LA-EG
From Equation the dynamics FLA BGs of Equation 13 can be derived as
1/22
F FEGsm (21, =
where
(27)
22
Ø2 + 77 [1 + e --3))
21
11 17222
Z2
=
02 + 1)(21 E(
x"))
(28)
By computing the derivatives with J1 = 0, 12
and = 0.01, 77 = 0.05, we obtain
[0.9975
-0.05
V V FrG.n (0,0)
FGsm
0.05
0.9005
(29)
with eigenvalues X 0.949 + 0.0122i. Note that | 0.949 and F.F (0, 0) has the imaginary conditioning of 1, which implies that the origin an stable equilibrium of EGsam whose local convergence be accelerated by a Lookahead dynamics. By plugging in the eigenvalues and m (V,FFF (0, 0)) = mm (V FV,Fr Fr.... (0, ()) = arctan 0.0122 the theoretically recommended range of (121. .7, 365.30)
0.999 0.0129 to Theorem we obtain
15

---

Under review as a conference paper at ICLR 2021
E PROOFS
E.1 PROOF OF PROPOSITION
Proof. One can easily check from Equation
that the dynamics F FGDS can be written as
(
(1) 2 F FDD (1
(1)
7
(30)
I
1 -1) " its Lookahead dynamics GLA-GDam can be written as
Defining M
(0) = ((1 - -a) + GLA (x :
(31)
It follows that the eigenvalues of VxGLA-GDem can be written as - a + ad4 with A 1 in XMM.. Assuming RR in) the line segment between (1, and X contains line segment inside S1 as in Figure [ (b). Therefore, for a small enough a, the interpolation a ax4 1. We thus conclude from Lemma 15 that the iterates of GLA--Gsaa converge to the Nash equilibrium (0,0) of the game. The proof for divergence of F FGDa follows from Lemma 13 and can be found Gidel et 2019a).
a lies
inside S1, implying
E.2 PROOF OF PROPOSITION
Proof. Using simple algebra on Equation the dynamics FpPsn can be written as
F FpPm (2 10 x0 I 1
7
(32)
1
-1]
Defining M
its Lookahead dynamics GLA-PPSI with synchronization period E and rate a E (0, 1) can be written as
I+. "
GLA.PP (c(2 (0)) = ((1 ((0-a]]e MM
(33)
follows that the eigenvalues of VLGPPP are 1 1 a atR with 2 daf # E A(M). We know
that 1 + aaii is interpolation between two distinct points on/inside S since | < 1 for any п E (0, 1). It follows that |1 a + ati 1, from which we conclude from Lemma 14 that the iterates of GLA-PPsIn converge to the Nash equilibrium 0) of the game with convergence rate O(11-a + a (//k), assuming the amortization of its computation over & forward steps.
Now we show that the convergence is accelerated upon the base dynamics Fres.. if RR(1 + in) < (1 + r/ and a is large enough. Figure (c) intuitively shows that the line segment between (1, and X contains line segment inside A=يي" when is such that R( | Therefore, the interpolation 1 - + at4 lies inside S|A+1" for a large enough a. This implies that the convergence rate 10 //k) of GLA PPa.. is accelerated upon the rate O of its base dynamics. D
E.3 PROOF LEMMA
Proof. We prove each of the cases in their order.
Case p(X) = 1. Assume that Amax & of for any Amax E Amax (X). Then we can immediately conclude p(f(X)) < since - + adt x(S(X)) an interpolation between two distinct points (1,0) and X on/inside S₁ for any X E A(X).
16

---

Under review as a conference paper at ICLR 2021
1.
D
B = x
a
as
p00
8:
S
(1.0)
9
(1,0)
(a) p(X)
(b) p()) <1
Figure Visualized eigenvalues of (1 +
Case p(X) 1. Assume that R(* for any À E (X). Then for each À A=1, A can be visualized as point Figure (a), where the existence of point D is guaranteed by R(AA < 1. easy to from the figure that
||A||| alA* 1| cos(( 0(A)) ||AD||
(34)
sufficient to place - a + a inside St. Furthermore, for any À E X(X) such that [^] < 1, 1 a & lies inside since 1 +a is interpolation between two distinct points on/inside
Sj. Therefore we conclude p(f((() < 1.
Case p(X) 1. Assume that R(**) < p(X) for any À Amax (X). Then for any A(X), A can be visualized as point B Figure 4 (b) since the existence of point D guaranteed by
R((*) < p(X)2* and sin((();) = sin(0(X,) px)))))))p(() follows from the law of sines. Therefore we can intuitively from the figure that
BC (1 a) 11 2p(X)* cos( +(A.) BD
(35)
sufficient to place - a + oAf inside Sp(xye, concluding the proof.
E.4 PROOF OF LEMMA
Proof. Let us denote Omin OSin(S), 0max (Sax(S) for brevity and let k E N be such that
E 26 min 20
x
3r Then we have min E 2
STB min
S (g
1 3m and k0max E 20 20 2
n0max
3r
S
20
(I 3rT which implies R()))) < O for any A E S such that (AA)) >> 0. Since every element of S has its conjugate pair in S by the assumption, we conclude BR(A)) < O for any X, S.
(2)
Now we show that the existence of k E such that l E
T
3x is guaranteed for a small
20
20max
enough 17 when 3S) 3. Using simple algebra, we can see that 6max < f66min) for 3min (S)
R defined by f(x)
3mæ equivalent 20
3x
1, implying nonempty
*+2r
20max
N
3T 29max Smax 3 min
Therefore it suffices to show that 0mux f (6mmi) holds for small enough
min
> 0 when
< 3.
(8)
Let us define function H. IR- + R given by
(()) def
1
20 max" +
))
(1 [1+ 11 113amax (S) /1 2 sec Omin
+ sec 6 + + +b).
(36)
Rmin (S)
17

---

Under review as a conference paper at ICLR 2021
del where min arctan
14 (S)) max
n min (8)
del
arctan
y 33max T- o (S) and del (1+:2 0 min tan 0max +
340
We show that the inequality
G max ()
(37)
min (S)
(m)
implies max < m0 and conclude the proof by showing that there exists small enough 1) such that satisfies Equation 37 when 3max (S)
3min' (ST 3.
Note that the incqualities m min and max I max directly follow from the definitions of miin and max + Furthermore, using the Shafer-type double inequalities (Mortici & Srivastava 2014 for arctan(-), , we obtain
tan Omin
3
6 min
(38)
1 1 2 2 + tan? m
(1 + Rux (1 2 sec 0min -)
3 tan max"
m
tan maax"
(39)
1 2/1221 1 + lan" 0
180
3
mux tan max
(40)
(1 + M) (1 + 2sec max
180(1 RpSmin))
from which follows that
0 0max
0max*
mmxx (S)
+ 1p (S)
1 + 2 sec Omin
+ b)
(41)
miin
Omin
Fiiin (S)
17 Remin(S)
1 soc 0
However, assuming inequality [37] we derive
S 3max (S) 1 + Rax (S)
1 2 sec 0
3m
f(0 +)
b
(42)
mmin (S) + Bmmii (5)
+ sec maxx"
π
20max
Omax" +
Furthermore, since f((x) (x+2x)² know that is both concave and monotonically increasing. Hence follows that
3x
[00ma
[(Omin)
(43)
θ min
from which we obtain 0max (0 by combining Equation
43
Finally, we prove that Equation 37 holds for small enough
when 3mas (S)
Smin (S) 3. Assume
Senax
3min (S) 3 and let 3
(m)x(()
0. By the continuity of H[- at = 0 and the fact that
3 min (S)
(()) = 1, there exists > 0 such that |
3 < e holds for any E (0,8). Therefore we have
Him) Smax (5) 3 Him) for any E (0, 6), concluding the proof.
mmin
E.5 PROOF OF THEOREM 5
Proof. From Equation 2 the dynamics FGG of Equation
I1 can be derived as
FOD.. (x (1)
x =
I
E, n
(44)
E
I
I, - XZ its Lookahead dynamics GIA-GDA with a synchronization pe- riod k E N and rate
Defining M def E,
L
-,
(0, 1) can be written as
x000
GLAGDD (x(0) xx)(0))= ((1-a))) a)
(45)
(1)
18

---

Under review as a conference paper at ICLR 2021
Together with Equation 14
that eigenvalues of V.GLA-GDA can be written as 1-a+adi;;
with Asi 1 5 + ino; / :P 2
4 E X(M) for any of 0, dmaax In the meanwhile,
2
simple calculation gives us AAiil = 1, which implies p(M) = 1. Now assume & E is such that arccoos(1 " mod * for any o;, Then follows that X * for any Y1i E A(M),, from which obtain p GVAGLA)) < from Lemma 3 It follows from Lemma 15 that the iterates converge to the origin, and we conclude the proof by observing that the transtormations X1 + U [ +x and X2 + [x;: 0n-rI +X2 of (0,0) R" x Rº gives (x,,x)) IR x R" which is a Nash equilibrium of Equation
E.6 PROOF OF THEOREM 6
Proof. From Equation the dynamics F'GDa. of Equation
can be derived as
I m m
E,
F DDDm (x) x2
(46)
O Er 0, and M nJ. Then its Lookahead dynamics GLA-GDsm.. with
Σ,
Let us define J synchronization period & N and a rate a E (0, 1) can be written as
GLA-CDSn (x) (t) (0)) = ((1 - a)I aM
(47)
Together with Equation 15 we can see that the eigenvalues of V GLA-GGD. can be written as - a ino X(M). In the meanwhile, one can easily see that [|æi] > 1, implying Then since tan mmm (XM)) =
aAi with A=i def
P(M) 1. Now assume that E arctan min aaretan mjx
3
min and tan max (A(M)) max we have h 20
It follows from Lemma 4 that BY B( < O for any A+i E A(M), and the existence of & is guaranteed for small enough when Smaa (A(M) Amas < 3. Then it follows from Lemma that p(V,GIA
20max(A(M1) (A(M))
mii Therefore, by Lemma [5] the iterates converge to the origin, and we conclude the proof by observing that the transformations X1 + [[x 0m-r] xf and X₂ H
min (A(
holds for small enough
V [xg; _ + x2 of (0,0) e E" x IR' gives (x), R R", which is Nash equilibrium of Equation
E.7 PROOF OF THEOREM 7
Proof. From Equation 4 the dynamics FPPs.. Equation can be derived as
F PpPom (x)
(t)
I E
x
(48)
i
0, ΣS
Σ,
Let us define J a synchronization period & E N and a rate a E (0, 1) can be written as
0, and M nJ)
Then its Lookahead dynamics GLA- with
GLA-PPaI (x)
(1) ((1 a) )M
(49)
Together with Equation
16 we can see that the eigenvalues of V. V1..AAEGGL.. can be written as 1 del Itine, E A(M). the meanwhile, we can easily see that | < Toaaa?
a + a with Ati holds for any 77 > O. Therefore, - a + att, is an interpolation between two distinct points (1, and A², on/inside S,. implying D(V,Gi..Pe the iterates converges to the origin. However, the transformations
1. Hence it follows from Lemma 15 that
U [xxx; 0mm:0m=r
x and
19

---

Under review as a conference paper at ICLR 2021
X2
Ky; Og
of (0, 0) E R' x R' gives (x1,x)) E IR x RR, which is Nash equilibrium + x
of Equation 9
Now show that GLA-PPam
accelerate the convergence upon its base dynamics Fi Assume Note that M shares the same eigenvalues with the Jacobian of
k E
3r
Zaretan no min"
arctan min
F FDDa
Therefore have tan 0 min (Amax
M M)) tan max (Amax (M-!)) m0min which implies
k E
3x m0 (Amax J] 24mmax (Amax (M)
Then it follows from Lemma 4 that R((AF) 0 for
any Xii E Amax (M ") and the existence of & E N is guaranteed for a small enough 7). Then we have R(AA.) < for any À2 E X(M) since the reciprocal of a complex number preserves the sign of the real part. Hence follows from Lemma 3 that p VLV.GLA < <P(M)& holds for a large enough a. We conclude the proof by noting that the convergence rate ([I(V,LA-PPPa. ) of GLA-PPsi provided by Lemma [5| is faster than the rate (p(()))) of FpPa.. assuming amortization of computations over i forward steps.
E.8 PROOF OF THEOREM 8
Proof. From Equation 5 the dynamics FEGSS of Equation 11 can be derived as
F FEGSA (x) x
1 [
n
-n I, - 7
(50)
Mrrr
and M rJJ. Then its Lookahead dynamics GLA-EG with synchronization period ls E N and a rate a E (0, 1) can be written as
Let us define J def
Σ >>
GLA-EGSS (x) (0)
((1 a) oM*)
(51)
we can see that the eigenvalues of V GLA-EGG can be written a aAt. with Ats 1 no, inj XMM) In the meanwhile, we easily see that [Ati] < 1 for any n E (0, d'ax implying (M) 1. Therefore, 1 1-a+a is an interpolation between two distinct
Together with Equation 18
points (1, 0) and _ on/inside S1. implying P(VAGLA < Hence follows from Lemma 15 that the iterates converges to the origin. However, the transformations + U [xx:: 0m-rl + x and
X2 r X2; Oz + x on (0, 0) E R" R" gives (xj, x5) E IR. R", which is a Nash equilibrium of Equation g
Now we show that EGsn. GLA. can accelerate the convergence upon its base dynamics F FEGS.. Assume
k:
and 17 (0, Zermax -
Note that |A, 2n12
1 24p
Parctan I
min
Zaretan
mii min
min
holds for each A+i E A(M). This implies Amax (M) {1- min + min) for any 17 E 20
hence 1s E Oemin(Amaa (Mj)+ 28max (Amax (M)) It follows from Lemma that RR(AL) < 0 holds for any A+i X(M), and the existence of k is guaranteed for small enough 7). Then by Lemma we have P(V.GIA.EG
< p(M)* for a large enough a. We conclude the proof by noting that the
}&) of GLA-EGs.. provided by Lemma 15 is faster than the rate convergence rate assuming amortization of computations over forward steps.
(pp(M)t) of EG
E.9 PROOF OF THEOREM 9
Proof. From Equation 7 the Jacobian of G' evaluated at x can written
vxG(x*)= = vx ((1 - a)id + aF (x*) = +v
(52)
= (1 - a
(53)
i=1
20

---

Under review as a conference paper at ICLR 2021
where the chain rule is used in third equality with slight abuse of notation F def id. We use the fact that is an equilibrium of dynamics F for the last equality. It is easy to see from Equation 53 that eigenvalues of VxG(x*) can be written as a + a. for each X E F(*xF(
However, A is either on/inside S₁ since Ae S 1 for each due the Lyapunov stability xf in F. a. is an interpolation between two points (1, 0) E S1 and X either on/inside S1; hence [1 a + a _ 1. By assumption that X * (1, for each X; E XVV, the
Therefore,
inequality is strict, i.e. |1 + ad < 1, implying the local asymptotic stability of x in G by
Proposition 14
E. PROOF OF THEOREM 10
Proof. From Equation 7 the Jacobian of G evaluated at x* can written as
VxG(x")= = v. ((1 - a:)id + aaF (x') = (1 a) a VV,
(54)
(1 - o:Il II (x))
a
(55)
where the chain rule is used in third equality with a slight abuse of notation F0 def id. We use the fact that x" is an equilibrium of dynamics F for the last equality. It is easy to see from Equation 55 that the eigenvalues of (xG(x*) can be written as - a + a. for each X E F(x)F((x))
Now assume that every element of Az1
Fx*(x*)) has non-zero imaginary part, and let le
3x 29 (Aaiin (((x") W) 20max (A
Let 17 0, J E R be such that Fx*)xx)
nJJ.
Then by Lemma R (R(A)) 0 holds for any A As V FxF(") (x))) and the existence of such i E N
is guaranteed for small enough 7 when (Am
< 3. Then it follows from the second
case of Theorem that ((V. < 1 holds for a small enough a. By Proposition 14 this implies local asymptotic stability of x* in G, concluding the proof.
E.11 PROOF OF THEOREM
Proof. From Equation 7 the Jacobian of G' evaluated at x can written
VxG(x") = v ((1 a:iid + aF* (x*) = (1 a) (V=x(xx)))
(56)
k
= (1 - a:)l + a II
(x (1- a)
(57)
where the chain rule is used in third equality with slight abuse of notation F def id. We use the fact that x" is an equilibrium of dynamics for the last equality. It is easy to see from Equation 57 that the eigenvalues of (x"(x") can be written - a + a. for each X; ((V,F((')))
Now assume that every element of Amnax
has non-zero imaginary part, and let l: E Letn > O,J E | be such that VxF((*) = I-nJ. 29 20 (V. (x)))) (V.F
3T
Then by Lemma R(x+)) < O holds for any de E Amax F(x")) )) and the existence of such k: E N
guaranteed for small enough when 3max (Amax F (x)))
3. Then it follows from the third
Emin(Amxx V. (x (D)
case of Theorem that p(VxG(x*)) ((V,F(x*)) (x*))* ) holds for small enough We conclude the proof by noting that this implies the upper bound Opp( (xx(x)))) on the rate of local convergence
provided by Proposition 14 is faster than (x)))
E. PROOF OF PROPOSITION 12
Proof. We directly follow the proofs of Lemma 2.1 and Lemma 3.1 in Daskalakis & Panageas (2018) and show that E (0, + guarantees locally diffeomorphic Lookahead dynamics, i.e locally invertible at any given points.
21

---

Under review as a conference paper at ICLR 2021
Note from Equation that the Jacobian of G evaluated at written
VxG(x)= Vx ((1 arjid + aF*) (x) (1 a)) +
(58)
(1 a + II VIF(F=-
(59)
where we have used the chain rule in the last equality with slight abuse of notation 7 id.
Now assume that a E (0. 1+L$) and consider the following inequalities
R
R VI (x))
V.F(FE -
III
V
& L.,
(60)
==1
where the first and second inequalities hold for any operator norms and the last inequality is due L-Lipschitzness of F. Then it follows from the assumption that
(.F(F" LA 1-a
(61)
Therefore, we conclude that G' locally diffeomorphic, since pilL vxF(Fi-(xx))) plies 0 & Xx).)(x)).
< I-a im-
Now let us define the set of unstable equilibria of G as U det fx' G(x*) = p
Then it directly follows from the locally diffeomorphic G and the arguments of Lee et al. (2019):
Daskalakis & Panageas (2018) that the set (z(00) lim (a()(")) E U} is of measure zero, which 1-00
concludes the proof. We refer the readers Appendix A Daskalakis al. (2018) for the detailed derivation of measure-zero arguments.
E.13 PROOF OF PROPOSITION
K
Proof. From Equation]
7 the Jacobian of G' evaluated at x can written as
vxG(x") v ((1 adiid + +aF*) (x*) = (1 - a) vVF""(x)
(62)
k
= (1 - al II (.F((F'
a) a)I+
(63)
where the chain rule is used in third equality with a slight abuse of notation 0 def id. We use the fact that x* is equilibrium of dynamics F for the last equality. It is casy to see from Equation that the eigenvalues of VxG((x)) can be written as 1 a-+ + aλt for each A E A(VxF((x))), However, by the assumption, there exists À A(V,F(x*)) )) such that [X] > 1. Since is positive real number,
we have - a I > 1, concluding the proof.
F ADDITIONAL EXPERIMENTS
F. EIGENVALUES GAN DYNAMICS
Theorem 10 assumes the radius-supporting eigenvalues, namely A (V.F) and Amax (V))), to have zen- imaginary parts and imaginary conditioning less than 3; otherwise, the existence of l that satisfies the sufficient conditions of Theorem 10 may not exist. We verify whether such assumptions are realistic practical settings. Specifically, we train GANs on MNIST dataset with two different loss functions, non-saturating (Goodfellow et al. 2014) and WGAN-GE (Gulrajani ct al. 2017). and visualize the top 20 eigenvalues of V.FGD... for each loss function in Figure
Figure suggests most of the radius-supporting eigenvalues of V GDs. well-performing point (Inception Score (IS) (Salimans et al., (016)) 2 9) are distributed along the imaginary axis, and have non-zero imaginary part with imaginary conditioning less than 3. This suggests that assumptions on the eigenvalues is not unrealistic and Theorem 10 can be applied for a practical non- non-linear
game like GANs.
22

---

Under review as a conference paper at ICLR 2021
0.015
Mic 24014)
0.00
slagy 34600
int
0.01
0.005
0.000
0.00
-0.01
-0.10
0.015
63
0.5
0.7
0.8
0.9
0.990
0.955
3.000
1.405
1.000
(a) Non-saturating GAN (IS=8.69)
(h) WGAN-GP (IS=9.09)
Figure 5: Visualized top 20 cigenvalues of F GDam before (blue) and after (orange) training GANs with two different loss functions on MNIST.
F.2 ILL-CONDITIONED BILINEAR GAMES AND MOMENTUM METHODS
GDje LA-GDA
Distance to NE
LA-GD
Distance to
EGsin LA-EGEm LA-Ggmm
LAEGGn MN
LiVEGsm.
1000
Iterations
Iterations
Lookahead dynamics without momentum.
Lonkahead dynamics with momentum.
Figure 6: Optimization progress of first-order methods in an ill-conditioned bilinear game. (a) Comparison between convergence of Lookahead dynamics chosen by (+) and (-) against Theorem
and g (b) Comparison between convergence of Lookahead dynamics with positive (PM) and
negative (NM) momentums.
We test the convergence and acceleration of Lookahead dynamics in an ill-conditioned bilinear game, and Lookahead can accelerate momentum- based dynamics in such game. Specifically, we test convergence of each dynamics in the game given by Equation 12 with n 20 and 1, which gives a sample with max = 8.81 and o min 0.11. Note that this game has a significantly larger conditioning number Tmax 76.4 than the bilinear game of conditioning 1.401 used in min
Section
We fix 0.05 throughout the experiments, and use Theorem g to derive theoretically recom- 3300 a 0.9 for LA-EGsim dynamics. We use k 50, = 0.1 to represent hyperparameters of LA-EGsim chosen against (-) the theorem. For LA-GD Alt we use 300, a = 0.1. We use the momentum factor 3 0.1 for negative (NM) and = 0.1 for positive (PM) momentum methods.
mended (+) hyperparameters
Figure (a) shows that Theorem indeed hold even for an conditioned game, Furthermore, Figure 6 (b) suggests that Lookahead significantly accelerate the convergence of momentum
methods that provably perform well on bilinear games, including the gradient descent with negative
momentum Giiel et al. 2019bb and extragradient with momentum Azizian et al. 2020).
23


Reviews:
[{"review_id": "qlznTnGKFbz", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper investigates „lookahead dynamics of smooth games“. By this the authors mean discrete-time dynamical systems generating from a given algorithm by adding a relaxation step in the updates. The main aim of the paper is to solve smooth games. Under sufficient convexity assumptions Nash equilibria for such games can be identified as solutions to a Variational Inequality with a monotone and operator. This is in particular the case for convex-concave min-max problems. The main conclusion of this paper is that a combination of relaxation and lookahead effects stabilizes the learning dynamics and can lead to acceleration over the base algorithm.\n\nEvaluation: This is a very strong paper with an extremely large number of interesting results. In my opinion it makes an extremely good contribution to the flourishing literature  on game dynamics. I only have some small technical remarks which can easily be fixed. \n\n\nSpecific Remarks: \n\n .  Interchange the order of eqs. (5) and (6).\n. Define $F^{k}$ in eq. (7) \n. Check for consistency of notation: Sometimes $M_{m\\times m}$ is used for the matrix space, then $\\mathbb{R}^{m\\times m}$. If the former is used, explain which field of numbers is used. \n. Define $\\rho$ in Theorem 3\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NBxkw86SJFg", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the theoretical aspect of lookahead dynamics of smooth games, inspired by the recently introduced Lookahead optimizer, in the spirit of studying the game dynamics of multiple agents. \n\nThe overall writing of the paper is not clear enough and should be organized better. For instance, in Sections 3.2 and 4, there are several consecutive theorems which should be better organized to enhance readability. The *Proof.* environments should also be omitted. Not being an expert in this area, I cannot judge the novelty of this work. The usage of the English language should also be improved to avoid grammatical mistakes. \n\n\nPros: \n- Possibly novel theoretical study of the game dynamics driven by the recently proposed lookahead optimizer.\n\n\nCons: \n- The main text is not self-contained; see below:  \n    - Lots of non-standard notation are not defined before being used. And the main text does not contain any pointers to the supplemental material for the list of mathematical notation. The notation $ \\mathbb{M}_{m \\times m} $ is never defined. How is it different from $ \\mathbb{R}^{m \\times m} $? Or does it stand for a matrix group like $ \\mathrm{GL}_m(\\mathbb{R}) $? I also think the principal argument $ \\mathrm{Arg} $ should be used instead of vaguely defining $ \\mathrm{arg} $ which is multi-valued in complex analysis.\n    - Some of the propositions and theorems in the paper are not mathematically precise or rigorous enough. E.g., proper choice of $ k $, small enough $\\alpha $, etc. Without making the statements precise, I found some theoretical results in the paper vacuous and hard to interpret.\n\n- The numerical experiments are not sufficient. Results of GAN optimization are expected as in other papers in this line of work, in order to demonstrate the full effectiveness of the proposed scheme. \n\n- The figures, especially Figures 2 and 3, seem to be of quality not up to publication standard and unclear.\n\n\nDespite my unfamiliarity with this line of work, I think this paper needs to be improved before acceptance, and I suggest rejection for the current state of this paper. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "MG0jEnAqxr-", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nThis paper provides a spectral analysis of Lookahead dynamics. This paper’s main results state that lookahead dynamics can improve a given method’s convergence rate if the Jacobian’s operator has eigenvalues with non-zero imaginary parts and an imaginary conditioning (ration between the largest and the smallest imaginary part) smaller than 3.\n\nOverall I think that the idea of this paper is exciting and is motivated by recent empirical observation. However, the theoretical results of this paper are relatively weak because of some restrictive assumptions. \n\n### Pros \nThe motivations of this paper are clean and propose a promising line of analysis. \n\n### Cons \nThe theory is only developed in a very restrictive setting (Bilinear with condition number smaller than 3 and general games with non-real eigenvalues and imaginary condition number smaller than 3) where the optimization problem is easy to solve. (a small condition number corresponds to an easy optimization problem.)\nThe experiments are relatively weak since they are only on well-conditioned bilinear games, a 2D non-linear problem, and do not explore the necessity of the assumptions of the theorems of the paper.\n\n## Questions/comment: \n\n- It seems to me that the condition that the Jacobian has non-real eigenvalue and $\\frac{\\mathcal I_\\max}{\\mathcal I_\\min} < 3$ is an artifact from your technique proof because lookahead does converge in the context of minimization (only real eigenvalues). \nThough in the minimization case, it seems quite direct to see that look ahead slows down the dynamics $ 1 - \\alpha + \\alpha \\lambda > \\lambda \\, \\forall 1>\\lambda >0$ the interesting property of lookahead highlighted by this work is that it can positively affect the impact eigenvalues with a large imaginary part on the convergence. \nSince in games, it has been shown that eigenvalues with a large imaginary part may slow down the convergence of games [Mescheder 2017], lookahead seems to be a promising direction to improve the convergence rate of the gradient method. Specifically, in the context of games with large or infinite imaginary condition number.\n\n- Overall, I think that this paper would benefit from a more precise analysis of the convergence rates.  Then answer the following question: can we find some problems where lookahead provides a significant improvement in terms of convergence rate (against standard methods such as Extragradient or Gradient). \nThe concept of acceleration usually refers to a significant improvement of the convergence rate (see for instance [Azizian et al. 2020] for a discussion on acceleration on games.) In the case of Theorem 3 it would mean $\\rho(f(X)) << \\rho(X)^k$.\n\n\n- Also, I am not sure about the relevance of the “local stabilization properties”, usually one may want to diverge from certain points where $\\rho(\\nabla_x F(x)) >1$ e.g., local maxima. \nWhat can you say regarding the fact that Lookahead does not converge to “bad” stationary points (for instance, in multi-objective minimization one want to avoid a local maximum for each player’s loss)?\n\n- Regarding your experiment, you could try to test if the conditions in your theorem are necessary:\nCan I find hyperparameters to make lookahead converging even when there are real eigenvalues or a condition number larger than 3? \nCan lookahead provide improvement with respect to optimization methods that provably perform well on bilinear minimax such as extragradient with momentum or specific method for bilinear [Azizian et al. 2020]?\n\n\nAzizian, Waïss, et al. \"Accelerating smooth games by manipulating spectral shapes.\" AISTATS (2020).\n\n\nMescheder, Lars, Sebastian Nowozin, and Andreas Geiger. \"The numerics of gans.\" Advances in Neural Information Processing Systems. 2017.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "BOd88iaqXkW", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nMotivated by the empirical success of lookahead in GAN training, the paper studies theoretically the convergence behavior of the algorithm in smooth games. In particular, the authors focus on bilinear games and local convergence around equilibrium points and derive sufficient conditions under which lookahead improves upon its base dynamics (by either stabilizing a non-convergent algorithm or accelerating a convergent one). \n\n### Pros\n\nThe lookahead optimizer studied in this paper is relatively new and worths more theoretical investigation.  In this spirit, this work consists in, as far as I am aware, the first attempt to understand theoretically the performance of lookahead in game optimization. The results concerning the potential stabilization and acceleration achieved by the lookahead mechanics provide us some insight into the reasons for its empirical success.\n\n### Cons\n\n#### On the significance of the results\n1. The sufficient conditions provided by the authors appear to be too restricted and cannot paint a global picture of what would happen in practice (even in the bilinear case). \nIn more than half of the theorems, we require the (imaginary) condition number to be smaller than 3. Is this realistic? What happens if this is not verified? Is it even reasonable to suppose that every eigenvalue of the matrix $J$ has non-zero imaginary part given that we would be at the other opposite if we consider a minimization problem (every eigenvalue would be real)? \nThe work would be much more complete if the authors could also discuss what may happen if these sufficient conditions are not verified.\n2. The implication of Theorem 12 is unclear. The fact that the dynamics avoids unstable equilibrium points of the dynamics itself seems to be of little interest for the problem that we are solving (and is a quite standard result). In effect, we are more interested in the characterization of the set of stable equilibrium points which may contain undesired solutions. This is clearly illustrated by the nonlinear game experiment in which the algorithm converges to a spurious attractor of the problem (to be explained in more detail below).\n\n#### On the presentation of the results\nThe presentation of the results needs to be improved. In its current form, the authors provide plenty of theorems that could be difficult to decipher for the readers. \n1. For example, it seems that both Theorems 3 and 4 are mainly used for deriving the rest of the theorems. This can be explicitly stated and I even feel it would be better to call them lemmas instead of theorems since it is not immediately clear what these two results imply. \n2. The authors could comment on the existence of $k$ for Theorems 5~11. While this is easy to derive it would be helpful to clearly state this somewhere (such as a sentence saying that such $k$ will always exist in all the theorems.)\n3. For both Theorems 10 and 11, corollaries for different base dynamics under different assumptions on the Jacobian of the vector field can be provided. Again, this may be straightforward but can help to understand the results.\n\n### Detailed comments\n\n#### Bilinear game reduction\n\nFor the paragraphs at the bottom of page 5. The authors describe why we only need to be interested in a bilinear game of the form (11). I understand this is due to the fact that modulo some transformation (9) and (11) have in fact the same trajectory. However, given the presentation of the paper, we may feel that to solve (9) we first solve (11) but this does not really make sense because the real goal is not to solve the problem (otherwise for (11) we know the solution is the all-zero vectors) but to understand how the algorithms perform in this problem. I feel that this point is much better explained in, for example, Zhang & Yu (2020).\n\n#### Diagonalizability\n\nI fail to understand the authors' arguments about the diagonalizability of the matrices in the proofs of Theorems 5\\~8.  Nonetheless, I feel this can be easily proved by using the fact that all real symmetric and skew-symmetric matrices are diagonalizable and we do not even need the extra assumptions on $k$ of Theorems 6~8.\n\n#### Nonlinear game experiment\n\nIn my opinion, the nonlinear game example considered in the experiments is not very appropriate. Actually, it depends on the problem that we are looking at. For (13), the origin is not a saddle point and not even a min-max solution (while it is a max-min solution). If our goal is to find the zeros of the vector field, we indeed want a convergence to the point. However, the whole paper is motivated by the computation of a (local) nash equilibrium, then we would like to avoid this point. Notice how this example is presented in (Hsieh et al. 2020): we want to escape from the origin and not converge to it. \nWhile the above points are not in conflict with what the authors want to demonstrate, this should be made clear to the readers to avoid confusion.\n\n#### A very minor point\nEquation (25) and the following analysis are actually for the proximal method, not EG.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors study the behavior of the Lookahead dynamics of Zhang et al. (2019) in bilinear zero-sum games. These dynamics work as follows: given a base algorithm for solving the game (such as gradient descent-ascent or extra-gradient), the Lookahead dynamics perform $k$ iterations of the base algorithm followed by an exponential moving average step with weight $\alpha$. The authors then provide a range of sufficient conditions for the eigenvalues of the matrix defining the game under which the Lookahead dynamics become more stable and converge faster than the base method.

This paper received four reviews and generated a very lively discussion between the authors and reviewers. Reviewer 4 was enthusiastic about the paper; the other three initially recommended rejection. During the discussion phase, the authors revised their paper extensively, and Reviewer 3 increased their score to an "accept" recommendation as a result. In the end, the reviewers were evenly split, and I also struggled a lot to reach a recommendation decision.

On the plus side, the paper treats an interesting problem: prior empirical evidence suggests that the Lookahead dynamics can improve the training of some adversarial machine learning models, so a theoretical study is very welcome and of clear value. On the other hand, the setting treated by the paper (bilinear min-max games) is somewhat restrictive, and the authors' theoretical conclusions do not always admit as clear an interpretation as one would like.

The issues that ended up playing the most important role in my recommendation were as follows:
1. The Lookahead dynamics with period $k$ involve $k$ gradient evaluations, so their rate of convergence should be compared at a $k:1$ ratio to GD and EG (with an additional $2:1$ ratio between GD and EG to put things on an even scale). To a certain degree, this $k:1$ ratio is present in the last part of Lemma 3; however, the exact acceleration achieved by the "shrinkage" of the spectral radius is not clear. This can also be seen in the semi-log plots provided by the authors, where the corresponding slopes of GD/EGD methods should be multiplied by $k$ when compared to the respective LA variants. In this regard, a comparison with the values of $k$ provided in Appendix D reveal that the performance of the Lookahead variants in terms of gradient queries is very similar (if not worse) to the non-LA variants. This is a cause of concern because, if LA does not accelerate convergence in simple bilinear games, it is not credible to expect faster convergence in more complicated problems. During the AC/reviewer discussion of this point, Reviewer 3 pointed out that this might be due to a suboptimal tuning of $\alpha$ (i.e., that it was not chosen "small enough"), and went out to note that this echoes the arguments of other reviewers that the characterization of acceleration may be problematic and not significant (even if it takes place).
2. Another major concern has to do with the stabilization provided by the Lookahead dynamics: using a benchmark game proposed in a recent paper by Hsieh et al. (2020), the authors showed that the Lookahead dynamics converge to a point which is unstable under GDA/EG (and hence avoided). This is fully consistent with the authors' theoretical analysis, but it also highlights an important problem with the Lookahead optimizer: if $k$ and $\alpha$ are tuned to suitable values for stabilization, the algorithm converges to a non-desirable critical point (a max-min instead of a min-max solution). This is a major cause of concern because it shows that the algorithm may, in general, converge to highly suboptimal states.

The above create an inconsistency in the main story of the paper. In fact, it seems to me that the authors' results form more of a "cautionary tale in hiding": even in very simple bilinear problems, the lookahead step may not provide acceleration and, even worse, it could converge to highly undesirable critical points. I find this "negative" contribution quite valuable from a theoretical standpoint, and I believe that a thoroughly revised paper along these lines would be of interest in the top venues of the community (though a more theoretical outlet like COLT might be more appropriate). However, this would require a drastic rewrite of the paper, to the extent that it should be treated as a new submission.

In view of all this, I am recommending a rejection at this stage. I insist however that this should not be seen as a critique for the mathematical analysis of the authors (which was appreciated by the reviewers), but as a recommendation to reframe the paper's narrative to bring it in line with the algorithm's observed behavior. I strongly encourage the authors to resubmit at the next top-tier opportunity.
Decision: Reject