Recursive Reasoning in Minimax Games: A Level $k$ Gradient Play Method
Authors: Zichu Liu
Lacra Pavel
Venue: NeurIPS 2022 Accept (2022)
Keywords: GAN
Game Theory
Adversarial Leraning

Abstract: Despite the success of generative adversarial networks (GANs) in generating visually appealing images, they are notoriously challenging to train. In order to stabilize the learning dynamics in minimax games, we propose a novel recursive reasoning algorithm: Level $k$ Gradient Play (Lv.$k$ GP) algorithm. Our algorithm does not require sophisticated heuristics or second-order information, as do existing algorithms based on predictive updates. We show that as k increases, Lv.$k$ GP converges asymptotically towards an accurate estimation of players' future strategy.
Moreover, we justify that Lv.$\infty$ GP naturally generalizes a line of provably convergent game dynamics which rely on predictive updates. Furthermore, we provide its local convergence property in nonconvex-nonconcave zero-sum games and global convergence in bilinear and quadratic games. By combining Lv.$k$ GP with Adam optimizer, our algorithm shows a clear advantage in terms of performance and computational overhead compared to other methods. Using a single Nvidia RTX3090 GPU and 30 times fewer parameters than BigGAN on CIFAR-10, we achieve an FID of 10.17 for unconditional image generation within 30 hours, allowing GAN training on common computational resources to reach state-of-the-art performance.

Recursive Reasoning in Minimax Games: A Level k Gradient Play Method
Zichu Liu
Lacra Pavel University of Toronto pavelßece www.unto.ocooommm
University of Toronto
j jieenn. liu@mail.... www.onto.cc.....
Abstract
Despite the success of generative adversarial networks (GANs) in generating visu- ally appealing images, they notoriously challenging to train. In order to stabilize the learning dynamics in minimax games, we propose novel recursive reasoning algorithm: Level & Gradient Play (Lv.k: GP) algorithm. In contrast many existing algorithms. our algorithm does not require sophisticated heuristics or curvature information. We show that as & increases. Lv.k GP converges asymptotically towards an accurate estimation of players' future strategy. Moreover, we justify that Lv.00 GP naturally generalizes a line of provably convergent game dynamics which rely on predictive updates. Furthermore, we provide its local convergence property nonconvex-nonconee
zero-sum games and global convergence bilinear and quadratic games. By combining Lv.k GP with Adam optimizer, our algorithm shows clear advantage terms of performance and computational overhead compared to other methods. Using single Nvidia RTX3090 GPU and 30 times fewer parameters than BigGAN on CIFAR-10, we achieve an FID 10. for unconditional image generation within 30 hours, allowing GAN training on common computational resources to reach state-of-the-a performance.
Introduction
In recent years, there has been a surge of powerful models that require simultaneous optimization of several objectives. This increasing interest in multi-objective optimization arises in various domains such as generative adversarial networks [21 27], adversarial attacks and robust optimization [37] [37] (7).
where several agents aim at minimizing their objectives simultancously. Games generalize this optimization framework by introducing different objectives for different learning agents, known players. The generative adversarial network is widely-used method of this type, which has demonstrated state-of-the tet-the-an art performance in variety of applications. including image generation [28 [5]] image super-resolution [32). and mmae-tt-immen translation [TO] Despite their success at generating visually appealing images, GANs are notoriously challenging to train 40 Naive application of the gradient- based algorithm GANs often leads to poor image diversity (sometimes manifesting as "mode collapse") [40], Poincare recurrence [9]] and subtle dependency on hyperparameters [18] An immense corpus of work devoted to exploring and enhancing the stability of GANs, including techniques diverse as the use of optimal transport distance [2]. critic gradient penalties (53), different neural network architectures (26 6 feature
and multi-agent reinforcement learning 33 54
matching [49] pre-trained feature space [50], and minibatch discrimination [49]. Nevertheless,
architectural modifications (e.g., StyleGANs (27) require extensive computational resources, and
many theoretically appealing methods (Follow-the-ride [55], CGD(52) require Hessian inverse
operations, which is infeasible for most GAN applications.
To stabilize the learning dynamics in GANs, many recent efforts rely sophisticated heuristics that
allow the agents to anticipate each other's next move [16
52
23 This anticipation an example of
recursive reasoning procedure in cognitive science 12 Similar to how humans think, recursive
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Extra-gradient
Level Gradieut Play
700
100
40-
200 -00
45
Figure 1: Illustration of predictive algorithms min, max, 10zy. Left: Extra-gradient algorithm.
Right: Level l gradient play algorithm (k 6). The solution, trajectory {æe, 3r ) and anticipated future state are shown with red star, black line and orange arrow, resp. The subplot in the right figure depicts how Lv.k GP predicts future states by showing its reasoning procedure with blue arrows. More steps in the reasoning process leading to better anticipations and faster convergence.
reasoning represents the belief reasoning process where each agent considers the reasoning process of other agents, based which it expects make better decisions. Importantly, it enables the use of opponents that reason about the learning agent, rather than assuming fixed opponents: the process can therefore be nested in form as believe that you believe that believe...'. Based on this intuition, we introduce a novel recursive reasoning algorithm that utilizes only gradient information to optimize GANs, Our contributions can be summarized as follows:
(i) We propose novel algorithm: level & gradient play (Lv.k GP), which is capable reasoning about players' future strategy. In game, agents Lv.k adjust their strategies in accordance with the strategies Lv.k agents. We justify that, while typical GANs optimizers, such as Learning with Opponent Learning Awareness (LOLA) and Symplectic Gradient Adjustment (SGA), approximate Lv.2 and Lv.3 GP, our algorithm permits higher levels of strategic reasoning. addition, the proposed algorithm is amenable neural network optimizers like Adam 229
(ii) We show that, smooth games, Lv.k GP converges asymptotically towards an accurate prediction of agents' next move. Under mutual opponent shaping. two Lv.00 agents will naturally have consistent view of one another the Lv.k GP converges as increases. Based on this idea, we provide closed-form solution for Lv.oc GP: the Semi-Prrximal Point Method (SPPM).
(iii) We prove the local convergence property of Lv.oc GP in nonconvex nonconcave zero-sum games and its global convergence in bilinear and quadratic games. The theoretical analysis we present indicates that strong interactions between competing agents can increase the convergence rate Lv.k GP agents in zero-sum game.
(iv) By combining Lv.k GP with Adam optimizer, our algorithm shows clear advantage in terms of performance and computational overhead compared to other methods. Using a single 3090 GPU with 30 times fewer parameters and 16 times smaller mini-batches than BigGAN [6] on CIFAR-I0. 10, achieve an FID score (24) of 10.17 for unconditional image generation within 30 hours, allowing GAN training on common computing resources to reach state-of-the-art performance.
Related Works
recent years, minimax problems have attracted considerable interest machine learning in light of their connection with GANs. Gradient descent ascent (GDA), generalization of gradient descent for minimax games, is the principal approach for training GANs in applications. GDA alternates between gradient descent step for the min-player and gradient ascent step for the max-player. The

---

convergence of GDA in games is far from as well understood as gradient descent in single-objective problems. Despite the impressive image quality generated by GANs, GDA fails to converge even in bilinear zero-sum games. Recent research on GIDA has established unified picture of its behavior in bilinear games in continuous and discrete-time [39] 46 13
First, [39] revealed that
continuous-time GDA dynamics in zero-sum games result in Poincare recurrence, where agents
return arbitrarily close to their initial state infinitely many times. Second, B [57] examined the
discrete-time GDA dynamics, showing that simultaneous update of two players results in divergence while the agents' strategies remain bounded and cycle when agents take turns to update their strategies.
The majority of existing approaches to stabilizing GDA follow one of three lines of research. The essence of the first method is that the discriminator is trained until convergence while the generator parameters are frozen. As long as the generator changes slowly enough, the discriminator still converges in the presence of small generator perturbations. The two-timescale update rule proposed by [2 24 42 aims to keep the diseriminator's optimality while updating the generator at an appropriate step size. 22 14 proved that this woo-iieescaee GDA with finite timescale separation equilibrium in differentiable games. [15] 55
converges towards the strict local Minimax//Stakellon explicitly find the local minimax equilibrium in games with secon-order optimization algorithms.
The second line of research overcomes the failure of GDA in games with predictive updates. Extra- gradient method (EG) 30 and optimistic gradient descent (OGD) [3] use the predictability of the agents' strategy to achieve better convergence property. Their variants are developed to improve the provided a unified analysis of EG and OGD, showing that they approximate the classical proximal point methods. Competitive gradient descent [52 models the agents' next move by solving a regularized bilinear approximation of the underlying game. Learning with opponent learning awareness (LOLA) and consistent opponent learning awareness (COLA) [66 (56] introduced opponent shaping to this problem by explicitly modeling the learning strategy of other agents in the game. LOLA models opponents as naive learners rather than LOLA agents, while COLA utilizes neural networks to predict opponents' next move. Lookahead minimaa 99] stabilizes GAN training by 'looking ahead' at the sequence of future states generated by inner optimizer. In the game theory literature, recent work has proposed Clairvoyant Multiplicative Weights Update (CMWU) for regret minimization in general games [47). Although CMWU is proposed to solve finite normal form games, which are different from unconstrained continuous games that Lv.k GP aims to solve, both CMWU and Lv.k GP share the same motivation of enabling the learning agent to update their strategy based on the opponent's ' future strategy. From this aspect, Lv.k GP can be viewed as specialized variant of CMUU that is specific the problem of two-player zero-sum games, but adapted for unconstrained continuous kernel games.
training performance of GANs 8
19 43
Other methods directly modify the GDA algorithm with ad-hoc modifications of game dynamics and introduction of additional regularizers. Consensus optimization (CO) 40) and gradient penalty improve convergence by directly minimizing the magnitude of players' gradients. Symplectic gradient adjustment (SGA) [33] 4 17] improves convergence by disentangling convergent potential components from rotational Hamiltonian components of the vector field.
22 (3)
3 Preliminaries
3.1 Notation
In this paper, vectors are lower-case bold letters (e.g. 0), matrices are upper-case bold letters (e.g. A). For a function f d + R, we denote its gradient by V.. For functions of two vector arguments f(z,y): : Rd. x Rd= + R we use Vaf. Vyf to denote its partial gradients. We use V. V Vyyff V / to denote its Hessian. A stationary point of f denotes the point where V.f = v,f = O. We use ||l|| to denote the Euclidean norm of vector v. We refer to the largest and smallest cigenvalues of matrix A by Amax(A) and Amin (A), respectively. Morcover, we denote the spectral radius of matrix A by ((A) = absolute value.
Pzz []. i.e., the eigenvalue with largest
3.2 Problem Definition
In order to justify the effectiveness of recursive reasoning procedure, in this paper, we consider the problem of training Generative Adversarial Networks (2I The GANs training strategy defines a two-player game between a generative neural network Go(-) and a discriminative neural network (-).). The generator takes input random noise sampled from a known distribution
3

---

Ps, e.g., 2 ~~ Ps, and outputs a sample Gø(z). A discriminator takes as imput a sample z (either sampled from the true distribution P. or from the generator) and attempts classify as real or fake. The goal of the generator is to fool the discriminator. The optimization of GAN is formulated as a two-player differentiable game where the generator Go with parameter 0, and the discriminator D& with parameters Φ, aim at minimizing their own cost function f(0, Φ) and g(0, Φ) respectively. as follows:
min f(0, Φ) and min ()), EER
(1)
BER"
where the two function f and g IRm R - R. When f f= -9 the corresponding optimization problem is called a two-player zero-sum game and it becomes minimax problem:
min max f(0, Φ). PER DER"
(Minimax)
In this work, we assume the cost functions have Lipschitz continuous gradients with respect to all model parameters (0, c):
Assumption 3.1. The gradient Vof 6), is Loo Lipschitz with respect to 9 and -Lipschit with respect & and the gradient Vog(O, Φ). Lop Lipschitz with respect and T.00 Lipschitz with respect to 0, i.e.
[ef Φ) Vef(02. Φ)11 < Leel 02l1 all $.
( Φ1) Vol(0, Φ2)1 < Losl Φ Φ2ll for all O,
V (0, Φ) Vag $)11 < Lool |0 O2 for all Φ.
Vog(O, Φ1) - Vog(O, Φ2)11 S Loo @0: - Φb for all O.
We define L == max Loo: Los. Loo, L
4 Level k Gradient Play
In this section, we propose a novel recursive reasoning algorithm, Level & Gradient Play (Lv.k GP), that allows the agents to discover self inffenntreeted strategies while taking into account other agents' reasoning processes. In Lv.k GP, l steps of recursive reasoning is applied to obtain an anticipated future state (0(h), (())),, and the current states (0,, Φe) are then updated as follows:
(0:)) = 0: Vel-VVeeS(O,.ooo Φf 1) Φ = Φ. - ( 1) .1)
Update: (0+1 (//))
Reasoning:
(Lv.k GP)
Ø1+1 = o.¹
We define the current state (0,, Φ.). to be the starting point (0. of ()),, of the reasoning process. Learning agents that adopt Lv.k GP strategy are then called Lv.k agents. Lv.1 agents act naively in response to the current state using GDA dynamics and Lv.2 agents act in response to Lv.1 agents by assuming its opponent as a naive learner. Therefore, Lv.k GP allows for higher levels of strategic reasoning. The inspiration comes from how humans collaborate: humans are great at anticipating how their actions will affect others, so they frequently find out how to collaborate with other people to reach a "win-win" solution. The key to human collaboration is their ability to understand how other humans think which helps them develop strategies that benefit their collaborators. One of our main theoretical results is the following theorem, which demonstrates that agents adopting Lv.k GP can preciscly predict other players' next move and reach consensus their future strategies:
Theorem 4.1. Suppose Assumption
3.1 holds. Let us define w: = [0,, D1 E Ru w (( E mm and Amax 2 x max[]]Vef(() I.). Vog(O,, d.))).. Assume w lie in a complete subspace of gm+ Then for Lukk GP we have:
(0 Φ
(k)
(w/ wi (k-1) S (nL) Amax
(2)
Suppose the learning rate satisfies: < (2L)-1, then the sequence (w) [ is Cauchy sequence. That is, given e > 0, there exists N such that, if > b > N then:
||!!
wf''l < 0(1²) <E
(3)
Moreover, the sequence (w! (k) J converges to a limit wi: limg-roo w!!h) w,.

---

In accordance with Theorem 4.1 if we define W1+1 = wi then Lv.o0 GP is equivalent to the following implicit algorithm where we call Pomi-Proximal Point Method:
041 - 8: - VV... ll+1)
(SPPM)
Φ Ø: -1 1/ 0.
4.1 Algorithms an Approximation of SPPM
SPPM players arrive at consensus by knowing precisely what their opponents' future strategies will be. Existing algorithms are not able to offer this kind of agreement. For instance, consensus optimization[40] forces the learning agents to cooperate regardless of their own benefits. Agents employ extra-gradient method (30, 4G and ( consider their opponents naive learners, ignoring their strategic reasoning ability. 52 takes into account the reasoning process of learning agents; however, it leads to inaccurate prediction of agents in games that have cost functions with non-zero higher order derivatives (n 2 3) [56]. In this section, we consider a subset of provably convergent variants of GDA in the Minimax settting showing that, for specific choice of hyperparameters, the mentioned algorithms either approximate SPPM or approximate the approximations of SPPM:
Table The update rules for the first player of SGA, LOLA, Lv.2 GP, LEAD, CGD, Lv.3 GP and SPPM in a probiee problem and their precision approximation of SPPM. The usage of zero or negative momentum has been suggested in recent works (20, [8 For sake of comparison, we assume no momentum factor in LEAD's update, which corresponds to 3 = 0 in Equation 10 of (23
Algorithm
Update Rule
Precision
SGA
0(41 00
LOLA [16
0.+1 - - Vol (.)
Lv.2 GP
0.11 0, V
(()))
LEAD 23
0.1 0, -oa ( 0
CGD 52
0(41 = 0, V Ve, 1V 01 (0++1 61)
O(7²)
Lv.3 GP
0,11 0, Vo, 0. V/ Vol (0,, (0), (2),(1))
O(1²)
SPPM (Lv.00 GP)
0.41 0, V0 01+1)
In Table we compare the orders of precision of different algorithms as an approximation of SPPM
in Minimax games with infinitely differentiable objective functions. In accordance with Equation (3)
of Theorem 4.1 Lv.k GP is an (1²²) approximation of SPPM. In order to analyze how well existing
algorithms approximate SPPM, consider the first-order Taylor approximation to SPPM:
00.1-0:: -: 00m=0:- [o /o (1) Vosf(O, V (: 0.)
(oo oo Φ.) -nj - Ver (1) - -d)
1t order approximation Lv.2 GP
Under-brace terms correspond to the first-order Taylor approximation of Lv.2 GP. For an appropriate choice of hyperparameters. SGA (y 77) and LOLA = 7) are identical to the first-order Taylor approximation of Lv.2 GP, where each agent models their opponent as naive learner. Hence, we list them above the Lv.2 GP. which approximates SPPM up O11²2.. CGD exactly recovers the first-order Taylor approximation of SPPM. In games with cost functions that have non-negative higher order derivatives (n 3), the remaining term SPPM's s first-order approximation an error of magnitude (17²), which means that CGD's accuracy is in the same range as that of Lv.3 GP. In bilinear and quadratic games where the objective function is at most twice differentiable, CGD
The CGD update for the max player & is Φ:+1 Φ: + Vf) Φ:) + vf (z) 1 0.). we substitute (Φ++1 Φ.)) into 0's update (and substitute (0.+1 O.) into d's update, respectively). we arrive the first-order approximation of SPPM. See A.5 for derivation details.
5

---

is equivalent to SPPM. The distinction between LEAD (a = 17) and CGD can be understood by considering their update rules. LEAD an explicit method where opponents' potential next strategies are anticipated based their most recent move (Φ,, Φ)-1). On the contrary, CGI) accounts for this anticipation in an implicit manner, (ΦL+1 - Φt), where the future states appear in current states' update rules. Therefore, the computation of CGD updates requires solving function involving additional Hessian inverse operations. A numerical justification also provided Table showing that the approximation accuracy of Lv.k GP improves as & increases.
Convergence Property
In Theorem 4.1 we have analytically proved that Lv.k GP convergences asymptotically towards
SPPM, we will use this result to study the convergence property of Lv.k GP in games based on analysis of SPPM. The local convergence of SPPM in a non convex non concave game can be analyzed via the spectral radius of the game Jacobian around stationary point:
Theorem 5.1. Consider the (Minimax) problem under Assumption 3.1 and Lv.k GP. Let (0", ,d)
be stationary point. Suppose B, - O' not in kernel of f0" T¹). Φt 8 not in kernel of J x²)) and v) < (L)-1 There exists neighhorhood L of (0", x²) such that if SPPM started
at (fo, ②o) E Edd, the iterates (0,, Φe) J120 generated by SPPM satisfy:
||0++1 0-1 + f1 - 011² p1 PVo0 110 where f =
0 + + Vof -
1 + 122 Ami (Vo. 00 00)
Moreoverfor any satisfying:
ma -I-1 ("), p') 1 00 ('))
(4)
1 17 Amin Voo. vof**)
SPPM converges asymptotically to (0", ,¹). Remark 5.1. Following the same condition as in
5.1 the iterates generated by Lx.2k GP satisfies:
110(20)
1 + 10:
(2k) (2()) 1012
p1 1 00 f 010 -L
Sa
1+ Amii Vagt f0)
where
(1+ (1+ >max V se 1²)
(1 (17 Xmin (Vool (0)
a=
for odd k, or 1- (112 Xmax Voof 60
Ve f) for even k,
1 1-(12 Amax Voo 60 ))
\maxx V f8 de f$)) )* (1)- Amin Voof" V 00 ()²²))})
b=
(n Amax Vosf 50 f)
We assume that the difference between the trajectory
{0,, @cl120 and the stationary point (0" x²) is not in the kernel of f00" x²) and (0" ; x²) for the sake of simplicity. Detailed proofs without this assump- tion are provided in Appendix ??. Following the same setting as Theorem 4.1 we have 7) < I--1, which ensures that 172 Amax o 49 f*) < 1. Therefore, as k- + oo, a a 1 and - 0 in Remark 5. and as such Lv.k GP has similar local convergence properties to SPPM. Figure 2 illustrates this property in quadratic game. Lv.k GP may behave differently than SPPM at lower values of k but as l increases, both max step size M/aaz, and distance to equilibrium for fixed number of iterations under 7maxx converges to that of SPPM. Thus, we observe that Lv.k GP is empirically similar to SPPM at higher values of k.
0.08
SPPN
3.07
30
15
20
Distance equilibrium
10
SPPN
Figure 2: Top: max step size against k Right: distance equilibrium against k. In both figures the red dashed line represents the value for SPPM.
We study the global convergence property of SPPM by analyzing its behavior in bilinear and quadratic games. Consider the following bilinear game:
min max O" M OER $ER"
(Bilinear game)

---

where M is full rank matrix. The following theorem summarizes SPPM's convergence property:
Theorem 5.2. Consider the Bilinear game and the SPPM method. Further, define ra 0
0- 1| + | -
-Ø =0 Then, for any > 0, the iterates {0t, Φz 1e22 generated by SPPM satisfy
1
Tt+1 1 11/ (M M)
(5)
It worth noting that the convergence property of Lv.k GP in bi-linear game has been studied in [2]. Furthermore, we study the convergence property of SPPM in the Quadratic game
min max 0T AO + o" Bø + 0² Co
(Quadratic game)
DER *ER"
where A R is symmetric and positive definite, B E <Rnx" is symmetric and negative definite and the interaction term C E RRnx is full rank. SPPM in quadratic games converges with the following rate:
Theorem 5.3. Consider the Quadratic game and the SPPM. Then, for any > 0, the iterates {0r, o1h generated by SPPM satisfy
|0++1 1- + || 1//12 = 1² - -1)])l))o 1 1² + Bn 1112
(6)
+ 172 Xamin (CTC)
GDA
LEAD
80
Lx22 GP
Lv.10 GP
SPPM KC
006
00B
03
0.12
0.33
0.3
0.52
3.53
2.0
6.06
20c
0.12 0.26
0.95
5.1
0.22
boaring
Figure 3: A grid of experiments for different algorithms with different values of interaction e and learning rates 1). The color in each cell indicates the distance to the equilibrium after 100 iterations. Note that the CGD update is equivalent to SPPM in quadratic games.
Theorem 5.1 5.2 and 5.3 indicate that stronger interaction Veof Φ²) improve the convergence
rate towards stationary points. By contrast, in existing modifications of GDA, the step size is In Figure 3 we showcase the effect of interaction on different algorithms in the Quadrattc game setup with dimension and the interaction matrix is defined as C = cI. Stronger interaction corresponds to higher values of e. A key difference between SPPM and Lv.k GP in the experiments is that, SPPM converges with any step size and so arbitrarily fast- while it is not the case for Lv.k GP. In order to approximate SPPM, one needs Lv.k GP to contraction and so have 7) < I.-1 This result implies an additional bound on step sizes for Lv.k GP. As long as the constraint on 7) is satisfied, stronger interaction only improves convergence for higher order Lv.k GP while all other algorithms quickly diverge as 1) and c increase.
chosen in inversely proportional to the interaction term f x²) 40 13 34
6 Experimental Results
In this section, we discuss our implementation of Lv.k GP algorithm for training GANs. Its perfor- mance is evaluated on 8- 8-Gaussians and two representative datasets CIFAR-10 10 and STL.110.
6.1 Level k Adam
We propose combine Lv.k GP with the Adam optimizer
Preliminary experiments find that Lv.k Adam to converge much faster than Lv.k GP, see A.8 for experiment results. A detailed pseudo-code for Level k Adam (Lv.k Adam) on GAN training with loss functions LG and LD is given in Algorithm T For the Adam optimizer, there are several possible choices on how to update the moments. This choice can lead to different algorithms in practice. Unlike [19] where the moments are updated on the fly, in Algorithm [T] we keep the moments fixed in the reasoning steps and update together with model parameters. In Table [ our experiment result suggests that the proposed L.vk Adam algorithm converges asymptotically as the number of reasoning steps k increases.
24
7

---

Algorithm 1: Level & Adam: proposed Adam with recursive reasoning steps
Input: Stopping time T, reasoning steps ki learning rate 110 fl, decay rates for momentum estimates 31, 82. initial weight (0o. Φo), Pa and Ps real and noise-data distributions, losses (G, Φ, 2; =) and LD ( Φb, x, 2). 1e- 8.
Parameters: Initial parameters: Oo, Φ0
Initialize first moments:mo.0 0, manu f 0 Initialize second moments:06,0 t 0, vo.0 t 0 for t= T-I do
Sample new mini-batch. x, x ~ Ps.
0 < 0r. 0,¹¹ Φ
for n= do
Compute stochastic gradient:
g (0 (f--1) x, 2): (n) VoLD(O!"-)) x.
Update estimate of first moment:
m = 3 + (1 31 Do.t ; m 0. = -i1m (1 - -31 -31) (n)
(n) (n)
Update estimate second moment:
v0. = 32 + (1 (g) )2 1 0,
= f2 + +(1 (g) (m)
Correct the bias for the moments:
o [1- 0,
(n) m (n) m (n)
0,t
(n)
(1 J
(n)
6.1
[1-
ve.
Perform Adam update: 0l()) 0:
170
m
1 0: n
(n)
m
% +
(m)
6660 +c
0.+1 + 0thh) Pt+1 - Φ: (k))
ma,t + m, M.t f- m (k).
(k)
18.1 f v0 Ust f v (k)
6.1
6.2 8-Gaussians
In our first experiment, we evaluate Lv.k Adam on generating a mixture of 8-Gaussians with standard deviations equal to 0.05 and modes uniformly distributed around the unit cir- cle. We use a two layer multi-layer perceptron with ReLU activations, latent dimension
of 64 and batch size of 128. The generated distribution is presented in Figure 4
Table The difference between two states generated by Lv.k Adam and Lv.k GP averaged over 100 steps. TTee difference is smaller than machine precision.
100 E
100
k = 2
k 4
k 6
k = 8
k: = 10
Lv.k Adam
1.04 x 10-1
1.60 10-2
2.91
10 10-3
6.08 10-4 4
1.68 10- Rs 0f
Lv.k GP
9.79 x 10-9 3.84 x 10-15
1.31
10-17
1.68 x 10-19
In addition to presenting the mode coverage of the gener- ated distribution after training, we also study the conver- gence of the reasoning steps of Lv.k Adam and Lv.k GP. Let us define the difference between the states of Lv.k and Lv.k 1 agents at time t as:
(k)
10(h) 0.h 112 + 11 11
(7)
We measure the difference averaged over the first 100 it- erations, 1 -100 r for Lv.10 Adam (n- 10- 4) and
Figure 4: Left: real distribution, Right:
100
generated distribution
Lv.10 GP (1) = 10-2). The result presented in Tablc demonstrates that both Lv.k GP and Lv.k Adam are

---

107
Uil Adkn
10
12
number of grsdient gradient computators
x10
124
beralon
Adam
LEAD
CGD
1944 6P
E6
564
1000
2000
3500
4200 5000
5003
7002 5002
20
witth OFMLP
Figure Top Left: Change FID scores over 1.2 million gradient computations for Adam, LEAD, Extra-Adam, Lv.2, Lv.4 and Lv.6 Adam on CIFAR-10 with SNGAN. Note for Lx.4 and Lv.6 Adam, we use the accelerated implementation introduced in Appendix ??. Bottom Left: Average computational cost per iteration 8- S-Gaussians experiment for MLPs with different widths. Right: Average computational cost per iteration on CIFAR-10 10 for Lv.k-Adam with different k. The values for LEAD (2.88) and Adam (14.65) are highlighted by dashed line.
verging as l increases. Moreover, the estimation precision of Lv.k GP improves rapidly and converges to within finite steps, making it accurate estimation for SPPM.
Table 3: FID and Inception scores of different algorithms and architectures on CIFAR-IO, Results
averaged over 3 runs. We re-evaluate its performance on the official implementation of FID.
Algorithm
Architecture
FID |
IS 1
Adam 29
BigGAN 66
14.73
9.22
Adam 29
StyleGAN2
58
11.07
9.18
Adam
29
SN-GAN
44
21.70 0.21
7.60 + 0.06
Unrolled GAN
SN-GAN
17.51 + 1.08
Extra-Adam 19
38
SN-GAN
15.47 + 1.82
LEAD 23
SN-GAN
44
14.45 + 0.45
LA-AIIGAN 9
SN-GAN
44
12.67 = 0.57
8.55 + 0.04
ODE-GAN(RK4) (48)
SN-GAN
11.85 + 0.21
8.61 + 0.06
Lv.6 Adam
SN-GAN
44
10.17 + 0.16
8.78 + 0.06
6.3 Image Generation Experiments
We evaluate the effectiveness of our Lv.k Adam algorithm on unconditional generation of CIFAR-1O BT. We use the Inception score (the higher the better) 49] and the Fréchet Inception distance (the lower the better) [24] as performance metrics for image synthesis. For architecture, we use the SN-GAN architecture based on 44 For baselines, we compare the performance of Lv.6 Adam that of other first-order and second-ordes optimization algorithms with the same SN-GAN architecture, and to state-of-the-art models trained with Adam. For Lv.k Adam, we use 3, = 0 and 32 = 0.9 for all experiments. We use different learning rates for the generator (Ιы- = 4e 5) and the discriminator (no 2e 4). We train Lv.k Adam with batch size 128 for 600 epochs. For testing, we use an exponential moving average of the generator's 's parameters with averaging factor 3 = 0.999.

---

Table 4: FID scores for the different loss functions with {2, 6).
Lv.2 Adam
Lv.4 Adam
Iv.6 Adam
Non-saturated loss
11.33 + 0.18
11.62 + 0.25
10.93 + 0.24
Hinge loss
10.68 + 0.20
10.33 + 0.22
10.17 + 0.16
In table 3 we present the performance of our method and basclines. The best FID score and Inception score, 10.17 + 0.16 and 8.78 + 0.06, on SN-GAN are obtained with our Lv.6 Adam. We also outperform BigGAN and StyleGAN2 terms of FID score. Notably, our model has 5.1M parameters in total, and is trained with a small batch size of 128, whereas BigGAN uses 158.3M parameters and a batch size of 2048.
The effect of k and losses: We evaluate values of k = {2, 4, 6} on non-saturated loss 21 (non- zero-sum formulation) and hinge loss [35] (zero-sum formulation). The result is presented in Table 4 Remarkably, our experiments demonstrate that few steps of recursive reasoning can result in significant performance gain comparing to existing GAN optimizers. The gradual improvements in the FID scores justify the idea that better estimation of opponents' next move improves performance. Moreover, we observe performance gains both zero-sum and non-zero-suni formulations which supplement our theoretical convergence guarantees in zero-sum games.
To test whether the proposed Lv.k Adam optimizer works on higher resolution images, we evaluate its performance on the STL-10 dataset [1I] with 3 x 48 x 48 resolutions. In our experiments, Lv.6 Adam obtained an averaged FID of 25.43 0.18 which outperforms that of the Adam optimizer, 30.25 + 0.26, using the same SN-GAN architecture.
Experiment results on STL-10:
Memory and computation cost: Compared to SGD, Lv.k Adam requires the same extra memory as the EG method (one additional set of parameters per player). The relative cost of one iteration versus SGD is factor of k and the computational cost increases linearly as increases, we illustrate this relationship in Figure 5 (right). We provide an accelerated version of Lv.k Adam in A.8 which reduces the computation cost by half for k 2. Figure S (top-lett, we compare the FID scores obtained by Lv.k Adam, Adam, and LEAD on CIFAR- 10 over the same number of gradient computations. LEAD, Lx4 Adam, and Lv6 Adam all outperform Adam in this experiment. Lv4 Adam outperforms LEAD after 2 x 10 gradient computations. Our method is also compared with different algorithms on the 8-Gaussian problem in terms of its computational cost. On the same architecture with different widths, Figure 5 (bottom-lefff illustrates the wall-clock time per computation for different algorithms. We observe that the computational cost of Lv.k Adam while being much lower than CGD, is similar to LEAD, SGA and CO which involve JVP operations. Each run CIFAR- 10 dataset takes 30 ~ 33 hours on Nvidia RTX3090 GPU. Each experiment on STL-10 10 takes 48 ~ 60 hours on a Nvidia RTX3090 GPU.
7 Conclusion and Future Work
This paper proposes a novel algorithm: Level l gradient play, capable of reasoning about players' future strategies. We achieve average FID score of 10.17 for unconditional image generation on CIFAR-10 dataset, allowing GAN training on common computing resources to reach state-of-the-art performance. Our results suggest that Lv.k GP is flexible add-on that can be easily attached to existing GAN optimizers (e.g., Adam) and provides noticeable gains in performance and stability. In future work, we will examine the effectiveness of our approach on more complicated GAN designs, such as Progressive GANs 26) and StyleGANs [27]. where optimization plays more significant role. Additionally, we intend to examine the convergence property of Lv.k GP in games with more than two players in the future.
Broader Impact Our work introduces a novel optimizer that improves the performance of GANs and may reduce the amount of hyperparameter tuning required by practitioners of generative modeling. Generative models have been used to create illegal content(a.k) k..k.a. deepfakes (5)). There is risk of negative social impact resulting from malicious of the proposed methods.
Acknowledgement This work was supported by funding from NSERC Alliance grant and Huawei Technologies Canada. ZI. would like to thank Tianshi Cao for insightful discussions on algorithm and experiment design. We are grateful to Bolin Gao and Dian Gadjov for their support.
10

---

References
[1] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference machine learning, pages 214 PMLR, 2017.
[2] Waiss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien. and Gauthier Gidel. A tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games. In International Conference on Artificial Intelligence and Statistics, pages 2863-2873. PMLR, 2020.
[3] James Bailey, Gauthier Gidel, and Georgios Piliouras. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent. In Conference on Learning Theory, pages 391-407. PMLR, 2020.
[4] David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The mechanies of n-player differentiable games. In International Conference on Machine Learning, pages 354-363. PMLR, 2018.
[5] John Brandon. Terrifying high-tech porn: Creepy 'deepfake" videos are on the rise. Fox News, 2018.
[6] Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale GAN training for high fidelity natural image synthesis. arXiv preprint arXiv: 1096, 2018.
[7] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp). pages 39-57. IEEE, 2017.
[8] Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien. Reducing noise in GAN training with variance reduced extragradient. Advances in Neural Information Processing Systems, 32, 2019.
[9] Tatjana Chavdarova, Matteo Pagliardini, Sebastian U Stich. François Fleuret, and Martin Jaggi. Taming GANs with lookahead minmaax. arXiv preprint arXiv:2006. 14567, 2020.
[10] Yunjey Choi, Minje Choi, Munyoung Kim, Jung-Wor Woo Ha, Sunghun Kim, and Jaegul Choo. StarGAN: Unified generative adversarial networks for multi-domain image-to-image translation. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 8789-8797, 2018.
[11] Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in unsuper- vised feature learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 215-223. JMLR Workshop and Conference Proceedings. 2011.
[12] Michael C Corballis. The uniqueness of human recursive thinking: the ability to think about thinking may be the critical attribute that distinguishes us from all other species. American Scientist, (5(3):240-25 2007.
[13] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. arXiv preprint 17Xiv:1111.00144 2017.
[14] Tanner Fiez and Lillian J Ratliff. Local convergence analysis of gradient descent ascent with finite timescale separation. In Proceedings of the International Conference on Learning Representation, 2021.
[15] Tanner Fiez, Benjamin Chasnov, and Lillian J Ratliff. Convergence of learning dynamics in Stackelberg games. arXiv preprint orXiv:/906.000 2019.
[16] Jakob N Foerster, Richard Y Chen, Maruan Al- Shedhiivv,, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with ppponent--carninng awareness. arXiv preprint arXiv: 17X.007799 2017.
[17] Ian Gemp and Sridhar Mahadevan. Global convergence to the equilibrium of gans using variational inequalities. arXiv preprint arXiv:1808.01533 2018.

---

[18] Ian Gemp and Brian McWilliams, The Unreasonable Effectiveness of Adam on Cycles. In NeurIPS Workshop on Bridging Game Theory and Deep Learning. 2019.
[19] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien.
A variational inequality perspective on generative adversarial networks. arXiv preprini 1802. 10551, 2018.
[20] Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Simon Lacoste-Julien, and Ioannis Mitliagkas. Negative momentum for improved game dynamics. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1802-1811. PMLR, 2019.
[21] Ian Goodfellow, Jean Pouget- Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
[22] Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of Wasserstein GANs. Advances in neural information processing systems, 30, 2017.
[23] Reyhane Askari Hemmat, Amartya Mitra, Guillaume Lajoie, and Ioannis Mitliagkas. Lead: Least-action dynamics for min-max optimization. arXiv preprint arXiv:2010. 13846, 2020.
[24] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by two time-scale update rule converge to local Nash equilibrium. Advances in neural information processing systems, 30, 2017.
[25] Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex- nonconcave minimax optimization? In International Conference on Machine Learning, pages 4880 4889. PMLR, 2020.
[26] Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen. Progressive growing of GANs for improved quality, stability, and variation. arXiv preprint arXiv: arXiv:1710.1019% 2017.
[27] Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 4401-4410, 2019.
[28] Tero Karras, Samuli Laine, Miik Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila. Analyzing and improving the image quality of StyleGAN. Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 8110-811 2020.
[29] Diederík P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 2014.
[30] Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[31] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[32] Christian Ledig, Lucas Theis, Ferenc Huszár, Jose Caballero, Andrew Cunningham, Alejandro Acosta, Andrew Aitken, Alykhan Tejani, Johannes Totz, Zehan Wang, al. Photo-realistic single image super-resolution using a generative adversarial network. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4681-4690, 2017.
[33] Alistair Letcher, David Balduzzi, Sébastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. Differentiable game mechanies. The Journal of Machine Learning Research, 20(1): (0(1):3032-001, 2019.
[34] Tengyuan Liang and James Stokes. Interaction matters: A note non-asymptotic local convergence of generative adversarial networks. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 907-915, PMLR, 2019.
12

---

[35] Jae Hyun Lim and Jong Chul Ye. Geometric gan. arXiv preprint
2017.
[36] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperatve-compelttive environments. Advances in neural information processing systems, 30, 2017.
[37] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.000 2017.
[38] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan- Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. arXiv preprint 18XXiv:8807.000 007.02629, 2018
[39] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2703-2717. SIAM, 2018.
[40] Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of GANs. Advances in neural information processing systems, 30, 2017.
[41] Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for GANs do actually converge? In International conference machine learning, pages 3481-3499 PMLR, 2018
[42] Luke Metz, Ben Poole, David Pfau, and Jascha Sohl-Dickstein. Unrolled generative adversarial networks. arXiv preprint 11.1v.1611.02163,, 2016.
[43] Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin, Peter Richtárik, and Yura Malitsky. Revisiting stochastic extragradient. In International Conference on Artificial Intelligence and Statistics, pages 4573-4582, PMLR, 2020.
[44] Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprint arXiv:1802.055: 2018
[45] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra- sttaa-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, pages 1497-1507. PMLR, 2020.
[46] Christos Papadimitriou and Georgios Piliouras. From Nash equilibria to chain recurrent sets: An algorithmic solution concept for game theory. Entropy, 20(10):782, 2018.
[47] Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Optimal no-regret learning in gen- eral games: Bounded regret with unbounded step-sizes via clairvoyant mwu. arXiv preprint 21X1:2111.11437, 2021.
[48] Chongli Qin, Yan Wu, Jost Tobias Springenberg, Andy Brock, Jeff Donahue. Timothy Lillicrap, and Pushmeet Kohli. Training generative adversarial networks by solving ordinary differential equations. Advances in Neural Information Processing Systems, 33:5599-5609 2020.
[49] Tim Salimans, Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training GANs. Advances in neural information processing systems, 29, 2016.
[50] Axel Sauer, Kashyap Chitta, Jens Müller, and Andreas Geiger. Projected GANs converge faster. Advances in Neural Information Processing Systems, 34, 2021.
[51] Axel Sauer, Katja Schwarz, and Andreas Geiger. StyleGAN-XI: Scaling StyleGAN to Large Diverse Datasets. arXiv preprint arXiv:2202.00277. 2022.
[52] Florian Schäfer and Anima Anandkumar. Competitive gradient descent, Advances Neural Information Processing Systems, 32, 2019.
13

---

[53] Hoang Thanh-Tung, Truyen Tran, and Svetha Venkatesh. Improving generalization and stability of generative adversarial networks. arXiv preprint FrXiv:1902.0398/ 2019.
[54] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun- young Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft using multi-agent reinforcement learning. Nature, 575(7782):350-333 354, 2019.
[55] Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A follow-the-ridge approach. arXiv preprint a.00v:1910.07512. 2019.
[56] Timon Willi, Johannes Treutlein, Alistair Letcher, and Jakob Foerster. COLA: Consistent Learning with Opponent-Leamning Awareness. arXiv preprint arXiv:2203. 040988 2022.
[57] Guodong Zhang, Yuanhao Wang, Laurent Lessard, and Roger Grosse. Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization. arXiv preprint arXiv:2102.09468, 2021.
[58] Shengyu Zhao, Zhijian Liu, Ji Lin, Jun-Yan Zhu, and Song Han. Differentiable augmentation for data-efficient gan training. Advances in Neural Information Processing Systems, 33:7559-7570, 2020.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 3 and 4
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? (Yes] See Section and 4
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix 1-4
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We will provide main experimental results.
the code needed to reproduce
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Appendix 5-8
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] See Section all of our experiment results are averaged over multiple runs with different initializations.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 6
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] We cite CIFAR-10
and STL-10 in section 6, and describe libraries that we use in appendix 5-7.
(b) Did you mention the license of the assets? [Yes] In appendix 7.
(c) Did you include any assets either in the supplemental material or URL? [No]
We did not publish any new asset.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? (Yss] We did not curate any new datasets. Existing dataset are discussed in appendix 7
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [Yes] In appendix 7.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "gvgbL-T75Vz", "reviewer": "Reviewer_Rboc", "summary": "This work introduces a novel algorithm, closely related to existing \"lookahead approaches\", for solving minmax games. \nIn \"level k gradient play\" each agent first arrives at a prediction of the opponent's move through k steps of recursive reasoning  *the counter move to the counter move to ... gradient descent*. They then make a step of gradient descent in the direction of the gradient computed using their own present position and their opponent's position according to the recursive reasoning. The authors show convergence results for the (theoretical) infinite recursion version with $k = \\infty$. Finally, the authors show numerical experiments on GANs, demonstrating improved IS and FID scores. ", "questions": "1. I find the way in which the algorithms are studied through the lens of SPPM to be confusing. First (up to including section 4), different algorithms are compared regarding how good they are at approximating SPPM. To this point, only vague, anthropomorphic language is provided to justify why approximating SPPM should be desirable. For instance in line 159: \"SPPM players arrive at a consensus by knowing precisely what their opponents’ future strategies will be. Existing algorithms are not able to offer this kind of agreement.\"\nIn Section 5, justification is given why SPPMs could be interesting by providing convergence results of SPPM. It is also claimed (line 189), that this convergence result is going to be used to study the convergence properties of Lv.k GP. However, this is then declared \"beyond the scope of this work\" and it is claimed that the convergence property can be \"inferred ... via SPPM\", without providing rigorous definitions. \nIn my opinion, this work could be strengthened considerably if instead of the SPPM characterization a simple local convergence result of Lv.k GP would be given. At first glance, it seems that it should be possible (strictly convex problem, small enough step size), that local convergence can be essentially reduced to the quadratic problem, where Lv.k GP should not be so hard to characterize? I would be curious to hear the opinion of the authors as to what is the roadblock here. Even if an analysis of Lv.k GP is not possible, it seems that by combining the theorems already in the paper it should be possible to provide an analysis for Lv.inf GP. \n\n2. The authors advertise their methods as not requiring second-order gradient information, compared to other methods that ...\n\"demand second-order gradient information (e.g., Jacobian-vector product and Hessian inverse), making well-performing models unavailable for standard computational budgets [50, 6]\"\nThis claim is false or at least misleading, as the proposed methods compute gradients at multiple points at each iteration and thus also use second-order information. Furthermore, using performant mixed-mode automatic differentiation frameworks such as JAX, computing Jacobian-vector products need not be significantly more expensive than gradient computation (for Hessian-inverses the story is a bit more complicated). Thus, the above strikes me as mischaracterizing competing methods.\n\n3. Related to the above, none of the experimental data shown give an idea of the cost-vs-quality trade-off of the proposed method. Can you run, say, Adam and Lv.6 Adam side by side and plot the IS and FID as a function of the number of gradient computations?\n\n4. Just out of curiosity: Did you try what happens if you run the experiment shown in Table 2 on the larger, image datasets? \n\n5. You write in line 164 that \"In games with at least thrice differentiable objective function\". Since the bilinear objective is infinitely differentiable you probably meant something else. Similar in 176.\n\n6. Is there a reason why LOLA and CGD were not included in Figure 2?", "limitations": "The authors discuss the additional computational cost of Lv.k in the very end of section 6. However, I was surprised that they did not provide further investigation of this concern by comparing, for instance, and adam model with k times as many epochs to an Lv.k Adam.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n\n- The algorithm seems natural and well-motivated to me. \n- The algorithm appears to provide substantial improvements in GAN training\n\n### Weaknesses:\n\n- The emphasis on SPPM is confusing and makes it hard to understand how the proposed algorithm relates to other methods in the literature.\n- Overall, there is a lot of hand-wavey language in the paper that hints at the advantages of the proposed method or results of the paper, that are never made concrete. \n\nOverall, my present view of the paper is that the results are suitable to be published in NeurIPS. However, the paper needs to undergo a major reorganization/rewrite to clearly convey its key points. I am not sure such a revision is within the scope of a single conference review cycle which is why I tend towards rejection and encouraging the authors to resubmit to a future cycle. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "gRaihGAxiKi", "reviewer": "Reviewer_iDC6", "summary": "This paper studied optimization of minimax games and proposed a recursive optimization algorithm called Level k gradient play (Lv.k GP). As an update based on predictive updates, Lv.k GP does not require second-order information, which is computationally more efficient than existing algorithms.\n\nTheorem 4.1 showed that as k increases, the level k reasoning of parameter vectors is approaching a limit point. And Lv.$\\infty$ GP is equivalent to an ideal algorithm Semi-Proximal Point Method (SPPM).\n\nTable 1 then summarized different algorithms and viewed them as approximations of SPPM, and Lv.k GP approximation accuracy improves as k increases.\n\nTheorem 5.1 showed local convergence of SPPM toward stationary points, and Theorems 5.2 and 5.3 showed that for a specific bilinear game and quadratic game, the SPPM converges in terms of squared norm of parameter distances.\n\nExperiments on training GANs using 8-Gaussians, CIFAR-10 and STL-10 are conducted to show that Lv.k GP and Lv.k Adam can be used to help existing GAN optimizers (e.g., Adam) provides noticeable gains in performance and stability.", "questions": "1. It is claimed that the Lv.k GP methods do not require second order information. Thus I suppose the implication is that Lv.k is faster than second order methods and their first order approximations (e.g., rank-1 approximation)? Is there any evidence to support this?\n\n2. How does the computational time increase as k increases (seems this relation should be linear to me)? It would be better to have the computational time recorded.\n\n3. Theorems 5.1-5.3 studied the convergence properties of the ideal algorithm SPPM. However, the algorithms actually used here are Lv.k GPs. A more direct study should be to get convergence properties of Lv.k GP, where as $k \\to \\infty$, Theorems 5.1-5.3 could be recovered.", "limitations": "The authors discussed the potential negative impact of using GANs to generate images, which is reasonable to me.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Minimax game optimization is an important problem which has lots of applications such as GANs, while being difficult to resolve and optimize. The research is well motivated.\n\n2. The proposed Lv.k GP algorithm seems novel to me, and the authors provided its approximation to SPPM and showed the convergence properties of SPPM.\n\n3. Experimental results are supporting the proposed methods\n\nWeakness:\n\n1. The proposed algorithms are Lv.k GPs, while the convergence properties are studied for SPPM method, which creates a gap.\n\n2. It is not clear that whether the claim of Lv.k GP is faster than (first order approximations) of second order methods is true or not.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RX_SnXscxF", "reviewer": "Reviewer_zfPL", "summary": "This paper proposes a Level K Gradient Play algorithm to stabilize the learning dynamics in minimax games (GANs).  By combining the proposed Lv. K algorithm with Adam optimizer, this  paper could achieve similar results with SOTA GAN model with 30 times fewer parameters. ", "questions": "As stated in the **Weaknesses** section.", "limitations": "As stated in the **Weaknesses** section.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n\nThis paper proposes the Level K Gradient Play Algorithm for stabilizing the training of GANs. The proposed method has a theoretical guarantee, with the assumption that the gradient of the loss function is Lipschitz continuous. Moreover, the paper proves and analyses the convergence properties of the Lv. K algorithm.\n\n**Weaknesses**:\n1. **On the definition of SPPM** (line 157). The author claims that \"SPPM players arrive at a consensus by knowing precisely what their opponents’ future strategies will be\" in line 159. However,  the stationary point $\\omega^*_{t} = [\\theta_t^*, \\phi_t^*]$ obtained with the reasoning step in Line 139 should not equal to the future strategies $\\omega_{t+1} = [\\theta_{t+1}, \\phi_{t+1}]$. In another word, the term $\\phi_{t+1}$ used to updating $\\theta_{t+1}$ does not equal to the term $\\phi_{t+1}$ updated by $\\theta_{t+1}$. The author should consider changing the notation here (Line 156). Or it may result in a misunderstanding that the Level.$\\infty$ GP algorithm could use the opponents' future strategy to update its current gradient.\n\n2. **Efficiency of the Level K algorithm.** As a level K algorithm would have to compute the gradient for **K** times for $\\theta$ and $\\phi$, this algorithm would take more time for a single step than a regular algorithm. I would recommend the author compare the method with baseline models regarding time efficiency (similar to Appendix. Figure~6 but with X axis as time).\n\n3. **Difference with Other GAN optimizers**. The proposed methods could be seen as \"given current generator, we use K step updates to find a better discriminator and use that discriminator to update the generator, and vice versa.\" However, some theory shows that, if we use a good (e.g., optimal) discriminator in the beginning, then we could obtain no gradient for the generator (Wasserstein-GAN). The $\\omega^*$ in this paper could be seen as the optimal $\\phi$ and $\\theta$ with the other kept fixed. Then what is the theoretical foundation between this paper and W-GAN that makes both methods work?\n\n4. **Limited Experiment**. This paper only conduct experiment on a small \"8-Gaussians\" experiment and CIFAR-10. As the author claims an improvement against BigGAN, which is good at high-resolution images, would the algorithm in this paper also be applicable to BigGAN or other big models?\n\n5. The proposed method is to stabilize the training of GAN. However, the author also claims that this algorithm uses 30 times fewer parameters. What's the correlation between stabilizing gradients and small models? Are there any theoretical results on this issue?", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PcVAZgCLvNQ", "reviewer": "Reviewer_kcBL", "summary": "This work propose Level k Gradient Play, a new dynamical system for non-convex non-concave min-max optimization. The key feature of the dynamics is that each player tries to anticipate what the opponent will do in the following round and adapt to it instead of the opponent's current iterate. Under mild assumptions, the Level $\\infty$ dynamics are well defined and enjoy local convergence for quadratic games and global convergence for bi-linear ones. In terms of practical algorithms, Level k algorithms are shown to converge to a Level $\\infty$ solution as $k \\to \\infty$ for sufficiently small learning rates based on a contraction property. This means that they can heuristically be used as replacements for Level $\\infty$. Level k Adam variants are shown to have good empirical performance. ", "questions": "If the authors comment on the differences/similarities between this work and [1] I would increase my score. More specifically, can Level k Gradient Play or a variant thereof be considered as a special case of Clairvoyant FTRL? ", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Regarding strengths, the presentation of the algorithm intuition and the key technical results is very clear. The proposed algorithm and analysis are to the best of my knowledge both novel when compared to other approaches in the non-convex non-concave optimization literature. While the theoretical guarantees are not particularly strong (many approaches can solve bilinear problems or have local convergence guarantees), the empirical results are promising.\n\nThe only weakness I detect is that this work is similar to [1], which is not referenced. Just like in this work, the agents try to predict the strategies of the opponents in the next turn and adapt to them. This is once again computationally feasible for small learning rates via a contraction argument. Once again the dynamics globally converge for bi-linear games and higher learning rates lead to faster convergence but may be computationally intractable just like this work.  \n\nWhile the overall technique may be similar to [1], the individual arguments are sufficiently different and the analysis of Section 4.1, Theorem 5.1 and 5.3 and the experimental analysis are unique to this work. Overall I propose to accept this work (Accept, 7).\n\nI have read the response of the authors which addressed my concern. I have thus increased my score to (Strong Accept, 8).\n \n[1] Optimal No-Regret Learning in General Games: Bounded Regret with Unbounded Step-Sizes via Clairvoyant MWU, Georgios Piliouras, Ryann Sim, Stratis Skoulakis, arXiv:2111.14737, 2021\n   ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept