On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach
Authors: Yuanhao Wang*
Guodong Zhang*
Jimmy Ba
Venue:  (2020)
Keywords: minimax optimization
smooth differentiable games
local convergence
generative adversarial networks
optimization

Abstract: Many tasks in modern machine learning can be formulated as finding equilibria in sequential games. In particular, two-player zero-sum sequential games, also known as minimax optimization, have received growing interest. It is tempting to apply gradient descent to solve minimax optimization given its popularity and success in supervised learning. However, it has been noted that naive application of gradient descent fails to find some local minimax and can converge to non-local-minimax points. In this paper, we propose Follow-the-Ridge (FR), a novel algorithm that provably converges to and only converges to local minimax. We show theoretically that the algorithm addresses the notorious rotational behaviour of gradient dynamics, and is compatible with preconditioning and positive momentum. Empirically, FR solves toy minimax problems and improves the convergence of GAN training compared to the recent minimax optimization algorithms. 

Published as a conference paper at ICLR 2020
ON SOLVING MINIMAX OPTIMIZATION LOCALLY: A FOLLOW-THE-RON RIDGE APPROACH
Yuanhao Wang"l, Guodong Zhang* 2.3 Jiimy B
mss Tsinghua University, *University of Toronto, Veccoo Institute yuanhao- 60mails...... tsinghua edu.en, (gdzhang, joa) (cs toronto.
ABSTRACT
Many tasks in modern machine learning can be formulated as finding equilibria in sequential games. In particular, two-player zero-sum sequential games, also known as minimax optimization, have received growing interest. It is tempting to apply gradient descent to solve minimax optimization given its popularity and success in supervised learning. However, it has been noted that naive application gradient descent fails to find some local minimax and can converge to non- points. In this paper, we propose Follow-the-Ride Ridge (FR), novel algorithm that provably converges to and only converges to local minimax. We show theoretically that the algorithm addresses the notorious rotational behaviour of gradient dynamics, and is compatible with preconditioning and positive momentum. Empirically, FR solves toy minimax problems and improves the convergence of GAN training compared to the recent minimax optimization algorithms'.
INTRODUCTION
We consider differentiable sequential games with two play- leader who commit action, and follower who responds after observing the leader's s action. Particu- larly, focus on the zero-sum case of this problem which is also known as minimax optimization, i.e.,
00
80
min max y(
xER" yEkm
-100
Unlike simultaneous games, many practical machine learn ing algorithms, including generative adversarial networks (GANs) (Goodfellow al., 2014; Arjovsky et al., 2017), adversarial training (Madry et al., 2018) and primal-dual reinforcement learning (Du et al., 2017; Dai al., 2018), explicitly specify the order of moves between players and the order of which player acts first crucial for the prob- lem. Therefore, the classical notion of local Nash equi- librium from simultancous games may not be proper definition of local optima for sequential games since mini- max is in general not equal to maximin. Instead, we consider the notion of local minimax (Jin et al., 2019) which takes into account the sequential structure of minimax optimization.
Ridge
Grad the ieader
Gradient follower
Correction term
Figure 1: For a function f(x, y) -3x² f to the ridge every iteration and moves along the ridge once it hits the ridge. Without the FR correction term, gradient dynamics can drift away from the ridge.
algorithm moves closer
The vanilla algorithm for solving sequential minimax optimization is gradient descent-ascent (GDA), where both players take gradient update simultaneously. However, GDA is known suffer from two drawbacks. First, has undesirable convergence properties: it fails to converge to some local minimax and can converge fixed points that not local minimax (Jin al., 2019; Daskalakis and Panageas, 2018). Second, GDA exhibits strong rotation around fixed points, which requires using very small learning rates (Mescheder et al., 2017: Balduzzi al., 2018) converge.
In this paper, we propose Follow-the-Ridge (FR), an algorithm for minimax optimization that addresses both issues. Specifically, we elucidate the cause of undesirable convergence of GDA the
"These two authors contributed equally.
Our code is made public https: / thub. aod-hhaggaaae Saaaan/Folll /Fol www- -ihgeeiddge

---

Published as a conference paper at ICLR 2020
leader whose gradient step takes the system away from the ridge. By adding correction term the follower, we explicitly cancel out negative effects of the leader's update. Intuitively, the combination of the leader's 's update and the correction term is parallel to the ridge in the landscape (sce Fig. 1), hence the name Dollow-the-Ridee Overall, our contributions are the following:
We propose novel algorithm for minimax optimization which has exact local convergence to local minimax points. Previously, this property was only known to be satisfied when the leader moves infinitely slower than the follower in gradient descent-ascent (Jin et al., 2019).
We show theoretically and empirically that FR addresses the notorious rotational behaviour of gradient dynamics around fixed points (Balduzzi et al., 2018) and thus allows a much larger learning rate compared to GDA.
We prove that our algorithm compatible with standard acceleration techniques such as preconditioning and positive momentum, which can speed up convergence significantly.
We further show that algorithm also applies to general-sum Stackelberg games (Fiez et al., 2019; Zeuthen, 1935) with similar theoretical guarantees.
Finally, we demonstrate empirically our algorithm improves the convergence performance in both toy minimax problems and GAN training compared to existing methods.
PRELIMINARIES
2.1 MINIMAX OPTIMIZATION
We consider sequential games with two players where one player is deemed the leader and the other the follower. We denote leader's action by R", and the follower's action by y Rm. The leader aims at minimizing the cost function f(x, while the follower aims at maximizing y(x The only assumption
make the cost function is the following.
Assumption 1. f is twice differentiable everywhere, and thrice differentiable at critical points. yy is invertible (i.e., non-singular).
The global solution to the sequential game miny maxy yx is an action pair y"),, such that y" is the global optimal response to x" for the follower, and that x" is the global optimal action for the leader assuming the follower always play the global optimal response. We call this global solution the global minimax. However, finding this global minimax often intractable; therefore, follow Jin et al. (2019) and take local minimax as the local surrogate.
Definition (local minimax). (x",y") is a local minimax for fx,,y) if( y is a local maximum of fxx", )) (2) x" is local minimum of ((x)= := r(x), where r(x) is the implicit function defined by V (x. y) = in neighborhood of x" with =xx")"".
In the definition above, the implicit function r(-) R RD is local best response for the follower, and is ridge in the landscape of f f y). Local minimaxity captures an equilibrium in two-player sequential game if both players are only allowed change their strategies locally. For notational convenience, we define
Hxx Hyx
Hxy
Vf(x,y) [Vx V v²f(x,y=
=
Hyy
In principle, local minimax can be characterized in terms of the following first-order and second-order conditions, which were established Jin et al. (2019).
Proposition 1 (First-order Condition). Any local minimax (x", .y") satisfies V ff(x", . y"" ) 0.
Proposition 2 (Second-order Necessary Condition). Any local minimax (x", ,²) satisfies Hyy O
and H Hxy H Hyx yx > O.
Proposition 3 (Second-order Sufficient Condition). Any stationary point (x*,y) satisfying Hyy - 0 and H H H Hyx 0 is a local minimax.
The concept global/local minimax is different from Nash equilibrium and local Nash, which are the equilibrium concepts typically studied for simultaneous games (see Nash al. (1950); Ratliff et al. (2016) for more details). In particular, we note that the concept of Nash equilibrium or local Nash does not reflect the order between the min-player and the max-player and may not exist even
2

---

Published as a conference paper at ICLR 2020
for simple functions (Jin al., 2019). In general, the of local minimax is superset of local Nash. Under some mild assumptions, local minimax points are guaranteed to exist (Jin et al., 2019). However, the set of stable fixed points of GDA, roughly speaking the set of points that GDA locally converges to, a different superset of local Nash (Jin et al., 2019). The relation between the three sets of points is illustrated in Fig. 2.
2.2 STABILITY OF DISCRETE DYNAMICAL SYSTEMS
Gradient-based methods can reliably find local stable fixed points - local minima in single-objective optimization. Here, we generalize the concept of stability games by taking game dynamics as discrete dynamical system. An itera- tion of the form 2++1 ur(zz) can be viewed as a discrete dynamical system, where in our case w Rn++ -> R=+m
GDA Stable Limit Points
Local
Local Minimax
Nash
Figure 2: Relation between local Nash, lo- cal minimax and GDA stable fixed points.
(z)) = z, then z is called a fixed point. We study the stability of fixed points as a proxy to local convergence of game dynamics.
Definition 2. Let J denote the Jacobian of at fixed point z. If it has spectral radius p(J) S 1, then we call z a stable fixed point. If p(J) < 1, then we call z strictly stable fixed point.
is known that strict stability implies local convergence (e.g., see Galor (2007)). In other words, if strictly stable fixed point, there exists neighborhood U of z such that when initialized in U, the iteration steps always converge to z.
UNDESIRABLE BEHAVIOURS OF GDA
In this section, we discuss the undesirable behaviours of GDA in more detail. Recall that the update rule of GDA is given by
X++1 X1 Vx,, Y++1 + yr +
(I)
where we assume the same learning rate for both the leader and the follower for simplicity?. As illustrated in Fig. 2, the of stable fixed points of GDA can include points that are not local minimax and, perhaps even worse, some local minimax are not necessarily stable fixed points of GDA. Here, we first give an example that stable fixed point of GDA not a local minimax. Consider min, maxy (a. y) 3x + y² 4xy; the only stationary point of this problem is (0, 0) and the Jacobian of GDA at this point is
6
4
J - -4
-2
is easy to see that the cigenvalues of are 61 = 62 = - 2n.. Therefore, by Definition 2, (0,0) is strictly stable fixed point of GDA. However, can show that Hyy 2 > 0 which doesn't satisfy the sccond-order necessary condition local minimax.
Similarly, one can easily find examples in which local minimax is not in the set of stable fixed points of GDA, e.g., min max,eR fæ, y) -3x² y² + 4xy (see Fig. 1). In this example, the two Jacobian eigenvalues both greater than 1 no matter how small the learning rate is. In other words, GDA fails to converge to (0, 0) for almost all initializations (Daskalakis and Panageas, 201 8).
As will discuss in the next section, the main culprit of the undesirable behaviours of GDA is the leader whose gradient update -17 V pushes the whole system away from the ridge or attracts the system non-local-minee minimax points. By contrast, the follower's step V f can pull the system closer to the ridge (see Fig. 1) or push it away from bad fixed points. To guarantee convergence to local minimax (or avoid bad fixed points), we have use a very small learning rate for the leader (Jin et al., 2019; Fiez et al., 2019) so that the V term dominates. In the next section, we offer an alternative approach which explicitly cancels out undesirable effects of -1 Vz/, thereby allowing us to use larger learning rates for the leader.
In general, the learning rates of two players can be different. Since arguments apply general setting long as the ratio T/x bx/Ty fly is positive constant, so we assume the same learning rate for convenience.
3

---

Published as a conference paper at ICLR 2020
4 FOLLOW THE RIDGE
Despite its popularity, GDA has the tendency to drift away from the ridge or the implicit function, and can, therefore, fail to converge with any constant learning rate. To address these problems. propose a novel algorithm for minimax optimization, which we term Follow-the Ridge (FR). The algorithm modifies gradient descent-ascent by applying an asymmetric preconditioner. The update rule is described in Algorithm. 1.
Algorithm 1 Follow-the-Rine Ridge (FR). Differences from gradient descent-ascent are shown in blue.
Require: Learning rate 7/x and fy; number of iterations T.
1: for 1, 1,... T do
2: X++1 f Th V 3x),
D gradient descent
3: Y1+1 f- Yt + Fyy Vy Vx, + T/x Hy Vx Xx),
b modified gradient ascent
The main intuition behind FR is the following. Suppose that y; is local maximum of f'x;; .). Let r(x) be the implicit function defined by Vyf(x.y) 0 around Yr). i..., ridge in the landscape of f(x, y). By definition, local minimax has lie on ridge: hence, it is intuitive to follow the ridge during learning. However, if Xt) is on the ridge, then fyf(x,, vr) = O, and one step of gradient descent- ascent will take (xe, Yt) to (x: Tix Vx).yt). which off the ridge. In other words, gradient descent-ascent tends to drift away from the ridge. The correction term we introduce is
Vxr(x) (- V (xx,xx)))) = 1h would bring yt to Yt + Vxr(x)(X(+1 stay along the ridge. When (x,, Yt) is not on ridge yet, we expect the - Vx term and the The Hy / term to move parallel to the ridge, while the f/y VyJ term brings (x.,y) closer to the ridge (see Fig. 1). Our main theoretical result is the following theorem, which suggests that FR locally converges and only converges to local minimax.
x,) R r(xx+1), thereby encouraging both players to
Theorem (Exact local convergence), With suitable learning rate, all strictly stable fixed points of FR are local minimax, and all local minimax points are stable fixed points of FR.
The proof mainly based on the following observation. The Jacobian of FR dynamics at a fixed point (x",y") is (c 17y/1 /)x)))
Hxx -cHyx
Hxy -cHyy
J - Tx
Hy Hyx I
where the Hessians are evaluated at (x", y"). J is similar to
M I
Hxx
Hxy H vy
Hxy
Hy yx I - yx I = Txx
yx
-cHyy
Therefore, the eigenvalues of J are those of I + ny Hyy and those of I 7> HHxx As shown in second-order necessary condition 2, (x",y" being a local minimax implics Hyy * and Hxx Hxy Hyy Hyx > O: one can then show that the spectral radius of the Jacobian satisfies p(J) S 1; hence (x" .y" is a stable fixed point by Definition 2. On the other hand, when p(J) by the sufficient condition in Proposition 3, (x", .y" must be local minimax.
HXy H H Hyx).
Remark (All eigenvalues are real). We notice that all eigenvalues of J, the Jacobian of FR, are real since both Hyy and Hxx Hyy are symmetric matrices. As noted by Mescheder al. (2017); Gidel et al. (2019); Balduzzi et al. (2018), the rotational behaviour (instability) of GDA is caused by eigenvalues with large imaginary part. Therefore, FR addresses the strong rotation problem around fixed points as all eeggereeee
eigenvalues are real.
4.1 ACCELERATING CONVERGENCE WITH PRECONDITIONING AND MOMENTUM
We now discuss several extension of FR that preserves the theoretical guarantees.
Preconditioning: To speed up the convergence, it is often desirable to apply preconditioner on the gradients that compensates for the curvature. For FR, the preconditioned variant given by
Xx+1
Y1+1
y:
X;
- H
I
Hyx
1
I
P2
7x V
(2)
4

---

Published as a conference paper at ICLR 2020
We can show that with any constant positive definite preconditioners P1 and P2, the local convergence behavior of Algorithm remains exact. We note that preconditioning is crucial for successfully training GANs (see Fig. 9) and RMSprop/Adam has been exclusively used in GAN training.
Another important technique in optimization momentum, which speeds up conver gence significantly both in theory and in practice (Polyak, 1964; Sutskever et al., 2013). We show that momentum can be incorporated into FR (here, we include momentum outside the correction term which is equivalent to applying momentum the gradient directly for simplicity. We give detailed discussion in Appendix D.4), which gives the following update rule:
Momentum:
X++1 Y++1
xx Y+
[
V Vx
Xc x(-1
Hy,
Hyx
+
Yr 1y--y-1 yr-
(3)
Because all of the Jacobian eigenvalues are real, we can show that momentum speeds up local convergence in similar way speeds up single objective minimization.
Theorem 2. For local minimax (x", yy"), let a min (Amin(-H) (Hyy): Amin (Hxx Hxy Hy Hyx)) )
= p (xx="(x","")) y))),, & == B/ox Then FR converges asymptotically to (x", ,y" with rate Mxx 2);; FR with a momentum parameter of = - e 1)= converges asymptotically with rate 12(16
Experiments the speedup of momentum are provided in Appendix E.2. This is in contrast to gradient descent-ascent, whose complex Jacobian eigenvalues prevent the use of positive momentum. Instead, negative momentum may be more preferable (Gidel et al., 2019), which does not achieve the same level of acceleration.
4.2 GENERAL STACKELBERG GAMES
Algorithm 2 Follow-the the theddeggeeeeeee (FR) for general-sum Stackelberg games.
Require: Learning rate 77x and fly number of iterations T.
1: for ..... T do
2: Xe+1 f- Xt 1xx (xt,
& total derivative D&S = Vx V (yy)) "Vy)) 3: Y1+1 t Bl Vx, vi) + T/x (V Vy (x),))
Here, we further extend FR to general sequential games, also known as Stackelberg games. The leader commits to an action x, while the follower plays y in response. The leader aims to minimize its cost fxx,y) while the follower aims minimizing g(x, y). For Stackelberg games, the notion of equilibrium is captured by Stackelberg equilibrium, which is essentially the solution to the following optimization problem:
min ((x,))ly E arg min
XER"
yER"
can be seen that minimax optimization is the special case when g= =-f
Similarly, one define local Stackelberg cquilibrium as generalization of local minimax in general-sum games (Fiez et al., 2019). Stackelberg game has wide applications in machine learn- ing. To name few, both multi-agent reinforcement learning (Littman, 1994) and hyperparameter optimization (Maclaurin et al., 2015) can be formulated as finding Stackelberg equilibria.
For general-sum games, naive gradient dynamics. i.e., both players taking gradient updates with their own cost functions, is no longer a reasonable algorithm, as local Stackelberg equilibria in general may not be stationary points. Instead, the leader should try the total derivative of f(x, r(x)). where r(x) is local best response for the follower. Thus the counterpart of gradient descent-ascent in general-sum games actually gradient dynamics with best-response gradient (Fiez al., 2019):
X1+1 < X, - Vxx - Vayg (Vyg)) V (xx,y)),
(4)
Y++1 y: - ((),,,))
'B rate a, mean that one iteration shortens the distance toward the fixed point by factor of (1 a):
hence the larger the better.

---

Published as a conference paper at ICLR 2020
FR can be adapted to general-sume games by adding the same correction term to the follower. The combined update rule is given in Algorithm 2. Similarly, we show that FR for Stackelberg games locally converges exactly to local Stackelberg equilibria (see Appendix C.2 for rigorous proof.)
5 RELATED WORK
As a special case of Stackelberg games (Ratliff et al., 2016) in the zero-sum setting, minimax optimization concerns the problem of solving minxex maxyey f(x, The problem has received wide attention due to its extensive applications in modern machine learning, in settings such as generative adversarial networks (GANs), adversarial training. The vast majority of this line of research focus on convex-concave setting (Kinderlehrer and Stampacchia, 1980; Nemirovski and Yudin, 1978; Nemirovski, 2004; Mokhtari et al., 2019b;a). Beyond the sanvex-concaee setting, Rafique et al. (2018); Lu et al. (2019); Lin al. (2019); Nouiched et al. (2019) consider nonconvex- concave problems, i..,, where f is nonconvex in x but concave in y. In general, there is no hope to find global optimum efficiently in nonconvex-coneawe setting.
More recently, ticularly, there are several lines of work analyzing the dynamics of gradient descent-ascent (GDA) in minconvex-nonconcant been shown to have undersirable convergence properties (Adolphs et al., 2019; Daskalakis and Panageas, 2018; Mazumdar et al., 2019; Jin et al., 2019) and exhibit strong rotation around fixed points (Mescheder al., 2017; Balduzzi al., 2018). To overcome this rotation behaviour of GDA, various modifications have been proposed, including averaging (Yazıeı et al., 2019), negative momentum (Gidel et al., 2019), extragradient (EG) (Korpelevich, 1976; Mertikopoulos et al., 2019), optimistic mirror descent (OGDA) (Daskalakis et al., 2018), consensus optimization (CO) (Mescheder et al., 2017) and symplectic gradient (SGA) (Balduzzi et al., 2018; Gemp and Mahadevan, 2018). However, note that all these algorithms discard the underlying sequential structure of minimax optimization and adopt a simultaneous game formulation. In this work, we hold that GAN train- ing is better viewed as sequential game rather than simultaneous game. The former is more consistent with the divergence minimization interpretation of GANs; there is also some empirical evidence showing that well-performing GAN generators are closer to saddle-point instead of local minimum (Berard et al., 2019), which suggests that local Nash, the typical solution concept for simultaneous games, may not be the most appropriate one for GANs.
problem has gained more attention due to its generality. Par-
setting (such as GAN training). Though simple and intuitive, GDA has
To the best of our knowledge, the only two methods that can (and only) converge to local minimax are two time-scale GDA (Jin et al., 2019) and gradient dynamics with best response gradient (Fiez et al., 2019). In two time-scale GDA, the leader moves infinitely slower than the follower, which may cause slow convergence due to infinitely small learning rates. The dynamics in Fiez et al. (2019) proposed for general-sum games. However, their main result for general-sum games require stronger assumptions and even that case, the dynamics can converge to non-local -tcaa-Stackellerrggggg points in general-sum games. In contrast, in general-sum games, FR will not converge to Son-local-Sttacelleee points. Besides, Adolphs et al. (2019); Mazumdar et al. (2019) attempt to solve the undesirable convergence issue of GDA by exploiting curvature information, but they focus simultaneous game on finding local Nash and it is unclear how to extend their algorithm to sequential games.
For GAN training, there is a rich literature different strategies to make the GAN- -ANgamme well- defined, e.g. by adding instance noise (Salimans et al., 2016), by using different objectives (Nowozin al., 2016; Guirajani al., 2017; Arjovsky al., 2017: Mao et al., 2017) by tweaking the architectures (Radford et al., 2015; Brock et al., 2019). While these strategies try to make the overall optimization problem easily, our work deals with specific optimization problem and convergence issues arise in theory and in practice; hence our algorithm is orthogonal to these work.
EXPERIMENTS
In this section, we investigate whether the theoretical guarantees of FR carry over to practical problems. Particularly, our experiments have three main aims: (1) to test FR converges and only converges to local minimax, (2) to test the effectiveness of FR training GANs with saturating loss, (3) to test whether FR addresses the notorious rotation problem in GAN training.

---

Published as a conference paper at ICLR 2020
10
6
0
G2A
GDM
-5
OGDA
-5-
0GM
OGDA
EG
CO
CO
88
-10
(a) GDA diverges
(b) GDA converges to bad fixed
(c) Limiting cycle
point that is non local minimax
Figure Trajectory of FR and other algorithms in low dimensional toy problems. Left: for gr. 0) is local minimax. Middle: for 92. (0, 0) NOT local minimax. Right: for ga, (0, 0) a local minimax. The contours are for the function value. The red triangle marks the initial position.
6.1 Low DIMENSIONAL. TOY EXAMPLES
To verify our claim on exact local convergence, we first compare FR with gradient descent-ascent (GDA), optimistic mirror descent (OGDA) (Daskalakis et al., 2018), extragradient (EG) (Korpelevich. 1976), symplectic gradient adjustment (SGA) (Balduzzi et al., 2018) and consensus optimization (CO) (Mescheder et al., 2017) on three simple low dimensional problems:
91 (z, y) = -x2² y²² + 4ry
92(x, y) = 3x² + v1² 4zy
ga(x, v) (4x² (y 3z 0.05x") - - -0.0((=*+0))
Here 91 and G2 are two-dimensional quadratic problems, which are arguably the simplest nontrivial problems. Ø3 is sixth-order polynomial scaled by exponential, which has a relatively complicated landscape compared to 91 and g2-
It can be seen that when running in gi, where (0, 0) is a local (and in fact global) minimax, only FR, SGA and CO converge to it; all other method diverges (the trajectories of OGDA and EG almost overlap). The main reason behind the divergence of GDA is that gradient of leader pushes the system away from the local minimax when it a local maximum for the leader. In 92, where (0, 0) is not local minimax, all algorithms except for FR converges this undesired stationary point'. In this case, the leader is still to blame for the undesirable convergence of GDA (and other variants) since gets trapped by the gradient pointing to the origin. g3. FR can converge to (0, 0), which is local minimax, while all other methods apparently enter limit cycles around (0, 0). The experiments suggest that even on extremely simple instances, existing algorithms can either fail to converge to desirable fixed point or converge to bad fixed points, whereas FR always exhibits desirable behaviors.
6.2 GENERATIVE ADVERSARIAL NETWORKS
One particularly promising application of minimax optimization algorithms is training generative adversarial networks (GANs). To recover the divergence minimization objective (e.g.. Jensen- Shannon divergence in standard GANs), we have to model the adversarial game sequential game. According to the formulation, the generator the leader who commits to an action first, while the discriminator is the follower that helps the generator to learn the target data distribution.
6.2.1 MIXTURE OF GAUSSIANS
We first evaluate different algorithms (GDA, EG, CO and FR) on mixture of Gaussian problems with the original saturating loss. To satisfy the non-singular Hessian assumption, we add L2 regularization (0.0002) to the discriminator. For both generator and discriminator, 64 hidden units each layer where tanh activations used. By default, RMSprop (Tieleman and Hinton, 2012) is used in all experiments while the learning rate is tuned for GDA. As FR involves the computation of Hessian inverses which is computational prohibitive, we instead use conjugate
use 2-hidden-layers MLP with
Note that it local minimum for the follower.
7

---

Published as a conference paper at ICLR 2020
Gradiont descert-ascent
Extra gradient
Consensus optimization
Follow the ridge
Govigee Dergy
100
gereratar
gererator
Figure 4: Comparison between FR and other algorithms on GANs with saturating loss. First Row: Generator distribution. Only consensus optimization (CO) and FR capture all three modes. Second Row: Discriminator prediction. The discriminator trained by converges a flat line, indicating being fooled by the generator. Third Row: Gradient norm as a function of iteration. Only in the case of FR, the gradient norm vanishes.
Generator Dersity
Discriminator Prediction (SDA)
Generator Dersity (FR)
Discr minator Pred ction (FR)
04
03
0.0
0.16
01
0.46
Figure 5: Comparison between FR and GDA 2D mixture of Gaussians. Left: GDA; Right: FR.
gradient (Martens, 2010; Nocedal and Wright, 2006) to solve the linear system the inner loop. To be specific, instead of solving Hyy Hyx vxJ directly, we solve Hy Hyx Vx/ to ensure that the problem is well-posed since H is always positive semidefinite. For all experimental details, we refer readers to Appendix D.2.
As shown in Fig. 4, GDA suffers from the "missing mode" problem and both discriminator and generator fail to con- verge confirmed by the gradient norm plot. EG fails to resolve the convergence issue of GDA and performs similarly GDA. With tuned gradient penalties, consen- sus optimization (CO) can successfully recover all three modes and obtain much smaller gradient norm. However, we notice that the gradient norm of CO decreases slowly and that both the generator and discriminator have not converged after 50,000 iterations. In contrast, the generator trained with FR successfully learns the true distribution with three modes and the discriminator is totally fooled by the generator. As expected, both players reach much lower gradient norm with FR, indicating fast convergence. Moreover, we find that even if initialized with GDA-trained networks (the top of Fig. 4), FR can still find all the modes at the end of training.
6.30
8.00
apha
Figure 6: Path-norm and path-angle of FR along the linear path.
To check whether FR fixes the strong rotation problem around fixed points, we follow Berard et al. (2019) plot the gradient parameters z and the final parameters z". they proposed to monitor the angle between the vector field and the linear path from z". Specifically, they looked at the quantity path-angle, defined
and path-angle (see Fig. 6). By interpolating between the initial
(()) = (z" z, vo) 1
where v. = v(az + (1 a)2²).
2
2/||v.11
They showed that high "bump" around rotation behaviour. We choose a = [0.6, 1.2] and plot the gradient norm and path-angle along the linear path for the updates of FR. In particular, only observe sign-switch around the fixed point
in the path-angle plot typically indicates strong
8

---

Published as a conference paper at ICLR 2020
z" without obvious bump, suggesting that FR doesn't exhibit rotational behaviour around the fixed point. To further check FR converges to local minimax, we check the second order condition of local minimax by computing the cigenvalues of Hxx Hxy Hy Hyx and Hyy As expected, all cigenvalues of Hxx- Hxy Hy are non-negative while all eigenvalues of Hyy are non-positive.
We also run FR on 2-D mixture of Gaussian with the same architectures (see Fig. 5) and compare it to vanilla GDA. Though GDA captures all the modes, we note that both the generator and the discriminator don't converge which can be seen from the gradient norm plot in Fig. 12. con-
GDA
discriminator generator
gradient nomn
100
20-1-
30
10"4
trast, the discriminator trained by FR is totally fooled by the generator and gradients vanish. We stress here that the sample quality in GAN models not a good metric of checking convergence as we shown in the above example.
1000020000 1200000000500000 iteration
1000020000 12000400000000000 (ter
Figure 7: Gradient norms of GDA and FR.
6.2.2 PRELIMINARY RESULTS ON MNIST
In a more realistic setting, we test our algorithm on image generation task. Particularly, we use the standard MNIST dataset (LeCun et al., 1998) but only take subset of the dataset with class 0 and for quick experimenting. To stabilize the training of GANs, we employ spectral normalization (Miyato al., 2018) to enforce Lipschitz continuity on the discriminator. To ensure the invertibility of the discriminator's Hessian, we add the same amount of L2 regularization to the discriminator as in mixture of Gaussian experiments. In terms of network architectures,
2-hidden-layers MLP with 512 hidden units in each layer for both the discriminator and the generator. For the discriminator, use Sigmoid activation the output layer. We use RMSProp as our base optimizer in the experiments with batch size 2,000. We run both GDA and FR for 100,000 iterations.
10
0
0
O
discriminator
O
1
0
0
Gradient norm
10"
0
/ / 0
1 / 0 /1/
O
10
0
0
0
/
10-1
0
0 1 0
O
Graden eett
O 1 0
0 1
10
/ 0
10-4
/ 1
0
10-7
discriminator
0
0
0
0
00
generator
25000 50000
75000 100000
25000
50000 75000 100000
Figure 8: Comparison between FR and GDA on MNIST dataset. Left: GDA; Right: FR.
In Fig. 8, we show the generated samples of GDA and FR along with the gradient norm plots. Our main observation is that FR improves convergence the gradient norms of both discriminator and generator decrease much faster than GDA; however the convergence is not well reflected by the quality of generated samples. We notice that gradients don't vanish zero the end of training. We conjecture that for high-dimensional data distribution like images, the network we used is not flexible enough to learn the distribution perfectly.
7 CONCLUSION
In this paper, we studied local convergence of learning dynamics in minimax optimization. To address undesirable behaviours of gradient descent-ascent, we proposed novel algorithm that locally converges to and only converges to local minimax by taking into account the sequential structure of minimax optimization. Meanwhile, we proved that our algorithm addresses the notorious rotational behaviour of vanilla pradient-descent-ascen around fixed points. We further showed theoretically that our algorithm is compatible with standard acceleration techniques, including preconditioning and positive momentum. Our algorithm be easily extended to general-sum Stackelberg games with similar theoretical guarantees. Empirically, we validated the effectiveness of our algorithm in both low-dimensional toy problems and GAN training.

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGEMENT
We thank Kefan Dong, Roger Grosse and Shengyang Sun for helpful comments on this project.
REFERENCES
Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmann. Local saddle point optimization: A curvature exploitation approach. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 486-495, 2019.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. arXiv:1701.07875. 2017.
Wasserstein gan.
arXiv preprint
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The mechanics of n-player differentiable games. In International Conference Machine Learning, pages 363-372, 2018.
Hugo Berard, Gauthier Gidel, Amjad Almahairi, Pascal Vincent, and Simon Lacoste-Julien. A closer look the optimization landscapes of generative adversarial networks. arXiv preprini
1rXiv:1906.048453 2019.
Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale GAN training for high fidelity natural image synthesis. In International Conference on Learning Representations, 2019. URL
https:://ppenreteeee wttp://wwwweeeeeteoeiiieeee--eee forrmmidd-1 xsqj09FF.
net
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sbeed: Convergent reinforcement learning with nonlinear function approximation. International Conference Machine Learning, pages 1142, 2018.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems, pages 9236-9246,
2018.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In International Conference on Learning Representations (ICLR 2018), 2018.
Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, pages 1049- 1058, 2017.
Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Convergence of learning dynamics in stackel- berg games. arXiv preprint
2019.
Oded Galor. Discrete dynamical systems. Springer Science & Business Media, 2007.
Ian Gemp and Sridhar Mahadevan. Global convergence to the equilibrium of gans using variational inequalities. arXiv preprint arXiv: 01531, 2018
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 on Artificial Intelligence and Statistics, pages 1802-1811, 2019.
Ian Goodfellow, Jean Pouget-Abadic, Mehdi Mirza, Bing Xu, David Warde-Farley. Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural informa- tion processing systems, pages 2672-2680, 2014.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Improved training of wasserstein gans. In Advances in neural information processing systems, pages 5767-5777, 2017.
Roger A. Horn and Charles R. Johnson. Matrix analysis. Cambridge University Press, 2nd edition, 2013.
10

---

Published as a conference paper at ICLR 2020
Chi Jin, Praneeth Netrapalli, and Michael I Jordan. What is local optimality in nonconvex-nonconeee minimax optimization? arXiv preprint arXiv:1902.006// 2019.
David Kinderlehrer and Guido Stampacchia. An introduction to variational inequalities and their applications, volume 31. Siam, 1980.
GM Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):227822222222 1998.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. arXiv preprint arXiv:1906.0053 2019.
Michael L Littman. Markov games as framework for multi-agent reinforcement learning. In
Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
Songtao Lu, Joannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive approxi- mation for one-sided non-convex min-max problems: algorithms and applications. arXiv preprint arXiv: /902.0994.. 2019.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-basse hyperparameter optimization through reversible learning. International Conference on Machine Learning, pages 21 2113-2122, 2015.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant adversarial attacks. In International Conference on Learn- ing Representations, 2018. URL https: / opwnreview.eeeeeee n forum ? diddrriIiieee........
Xudong Mao, Qing Li, Haoran Xie, Raymond YK Lau, Zhen Wang. and Stephen Paul Smolley, Least squares generative adversarial networks. In Proceedings of the IEEE International Conference on Computer Vision, pages 2794-28022 2017.
James Martens. Deep learning via hessian-free optimization. In International Conference on Machine Learning, pages 735-742, 2010.
Eric V Mazumdar, Michael I Jordan, and S Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. arXiv preprint arXiv:1901.000 00088, 2019.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra(- gradient) mile. In International Conference on Learning Representations, 2019, URL https: //openreview net/ forum? id= jCKK...
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of gans. In Advances in Neural Information Processing Systems, pages 1825 1825-1835, 2017.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. International Conference on Learning Representations, 2018.
URL hwtps:ttp//... wwwp//wweeeeeeeee/////ptp net forum? i 11=B1QQRe QRgziT-
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. Proximal point approximations achieving convergence rate of (11/k) for smooth convex-concave saddle point problems: Optimistic gradient and extra- extra-gradee gradient methods. arXiv preprint arXiv: 2019a.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. arXiv preprint arXiv:1901.085// 2019b.
John Nash et al. Equilibrium points in n n-person games. Proceedings of the national academy of sciences, 36(1):48 49, 1950.
11

---

Published as a conference paper at ICLR 2020
Arkadi Nemirovski.
with rate of convergence (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-25) 25,, 2004.
Arkadi S Nemirovski and David Berkovich Yudin. Cesari convergence of the gradient method of approximating saddle points of convex-concave functions. In Doklady Akademii Nauk, volume 239. pages 1056-1059, Russian Academy of Sciences, 1978.
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.
Maher Nouiehed, Maziar Sanjabi, Jason D Lee, and Meisam Razaviyayn. Solving class of non- convex min-max games using iterative first order methods. arXiv preprint arXiv: 192.000992 2019.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. In Advances in neural information processing systems, pages 271-279, 2016.
Peter Olver. Nonlinear systems. httt:://wwwwsseeee ma tha umn edd//=olver//nnmmmll pdf, 2015.
B.T. Polyak. Some methods of speeding up the convergence of iteration methods. Ussr Computa- tional Mathematics and Mathematical Physics, 4(5):1-17, 1964. URL pttttps:/accadmmtt
mi crosoft. com/ httmm/appr/1998855 (atper//9987201010
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint
2015.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization:
Provable algorithms and applications machine learning. arXiv preprint arXiv:1810.02060, 2018.
Lillian J. Ratliff, Samuel A. Burden, and S. Shankar Sastry. On the characterization of local nash equilibria in continuous games. IEEE Transactions Automatic Control, 6188):231 2016.
URL https::p///. /aaaaaaaaacccc//c. www. crosoft. wwtm:pappee/33333955555555
Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. In Advances in neural information processing systems, pages 2234-2242, 2016.
Ilya Sutskever, James Martens, George E. Dahl, and Geoffrey E. Hinton. On the importance of initialization and momentum in deep learning. In Proceedings of The 30th International Conference Machine Learning, pages 1139-1147, 2013. URL https: aca.emia c. micsosft. com/ patpp//ppeae11///
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
Yasin Yazıeı, Chuan-Sheng Foo, Stefan Winkler, Kim-Hui Yap, Georgios Piliouras, and Vijay Chan- drasekhar. The unusual effectiveness averaging in GAN training. In International Conference on Learning Representations, 2019. URL https::/ ntt.:/wweetffoteeeeeee idd SRqFQ.
F. Zeuthen. Heinrich von stackelberg: Marktformen und gleichgewicht. julius springer. 1934 (138 s.). pris r. 9,60. Nationalokonomisk Tidsskrift, 3, 1935. URL https://academie /aacdemmic. microsoft. com / htmmm/pppp/22022245000
12

---

Published as a conference paper at ICLR 2020
A PROOF OF THEOREM
Proof. First of all, note that FR's 's update rule can be rewritten as
Xx+1
Xx
I H Hyx
a]
[
Vx [
1xx
(5)
Y++1
Yt
I
where c := The and that
is always invertible. Therefore, the fixed points FR
H Hy H yx
cI
are exactly those that satisfy y)
0. ie.. the first-order necessary condition of local minimax.
Now, consider fixed point (x", yy), The Jacobian of FR's 's update rule at (x",y") is given by
Hxx Hyy H yx I -cHyx yx
Hxy
J T
-cHyy yy
Observe that is similar to
I
I
J
Hyx
H
Hyx
vy
yy
I
I
Hxx cHyx
Hxy -cHyy
I Hyy Hyx
=I
1/x
Hyy
Hyx
I
H
Hyx
vy
Hxx
Hxy H
yx
Hxy
-
1/x
-cHyy
which is block diagonal. Therefore, the eigenvalues of are exactly those of + ny Hyy and those of I- 11x (Hxx Hxy Hyy Hyx), which are all real because both matrices are symmetric.
Moreover, suppose that
2
7 max (p(Hxx Hxy Hyy H cp(-Hyy))
where p(-) stands for spectral radius. In this case
-I -I < I Hyyyyyn Hyy: -I Thx (Hxx - Hxy H Hyx)
Therefore whether p(J) < depends on whether Hyy or Hxx - Hxy Hyx has negative eigen- values. If (x*,y") ) is a local minimax, by the necessary condition, Hyy & 0, Hxy Hyx > 0. It follows that the eigenvalues of J all fall in (-1, (x",y") )²*( is thus a stable fixed point of FR.
On the other hand, when (x", y²) is strictly stable fixed point, pJJ 1. It follows that both Hyy and Hxx Hxy Hyy Hyx must be positive definite. By the sufficient conditions of local minimax, (x", y") is local minimax.
B PROOF OF THEOREM 2
Consider a general discrete dynamical system Ze+1 +- g(:)). Let z" be fixed point of g()). Let J(z) denote the Jacobian of g(-) Similar results can be found in many texts; see, for instance. Theorem 2.12 (Olver, 2015).
Proposition 4 (Local convergence rate from Jacobian eigenvalue). If p(]((z))) - A then there exists neighborhood U of x such that for any E U,
1|z x" S C 00
1|z0 z z²|12,
where C' is some constant.
Proof. By Lemma 5.6.10 (Horn and Johnson, 2013), since p(J(z")) - A, there exists a matrix
norm || || induced by vector norm || such that [x](z)) }|| < 1 32 4
Now consider the Taylor
expansion of g(z) at the fixed point zz:
g(2) g(z") J(z(( (z x²) + R(z z²),
13

---

Published as a conference paper at ICLR 2020
where the remainder term satisfies
R(z z²)
lim
2 z=1 = 0.
Therefore, choose 5 such that whenever ||z-z") < 6, || 2¹)l = 1 z2 this case,
ll - g(2")) _ [J(z") (z =1 + R( z²)ll
- [J(z") |lll 4 z² + 4 |z ='
1 (1
||2 - z"1
2
In other words, when Zo U {z) 1z z" d),
b 201l < 1 -
||z0 x-
By the equivalence of finite dimensional norms, there exists constants cı, > 0 such that
Vz, e c1|1z|12 S ||||| s 02/12112-
Therefore
||z - z 20112 5 C2 A
120
=2-12-
2
In other words, the rate of convergence is given by the gap between p(J) and 1. We now prove Theorem using this view.
proof of Theorem' In the following proof we use || to denote the standard spectral norm. is not hard to see that Xmaz Hyy) S pl f(x", )) = 3 and [Hxy xy
I B. Also,
g2
Aman H xx H xy H < H + Hxy |
S 3
(1++))
Therefore choose learning to be T/x Fly
2x3 In this case, the eigenvalues of the Using Proposition 4, we can show that
Jacobian of FR without momentum all fall in [0, 1
2x
FR locally converges with rate of O(x ((x-)).
Now, let consider FR with momentum:
X++1
V Vyf
X1 x,-1
Y++1
Y
H H yx
I
+7
Yt yt-1
(6)
This is dynamical system on the augmented space of (x,, Vr, X, 1. Yt-1). Let
I
H
Hxy
Ji Tx
Hyx
I
- Hyx
-Hyy
be the Jacobian of the original FR at fixed point (x", y"), (x", y y*) is
Then the Jacobian of Polyak's momentum
J2 >I Jr
- 0
The spectrum of Jg given by solutions to
det (AI J2) = det ((12 - + 7 -11) = 0.
In other words, an eigenvalue of Jı corresponds to two eigenvalues of J. given by the roots of
x - +) 0. For our case, let us choose 1
122 Then for any r E [0, - 2
2
1
7)² 7) 47 5
+ +
47 00
2x
Therefore the two roots of X2 + ( must imaginary, and their magnitude are exactly
V.. Since V < 1 - <
2//x²' we now know that p(J2) S 1- 2/26" Using Proposition
that FR with momentum locally converge with of ((K-1))
14

---

Published as a conference paper at ICLR 2020
C PROOFS FOR SECTION 4
C.1 PRECONDITIONING
Recall that the preconditioned variant of FR is given by
X
Xx
I
1/x Pi Vx/ I
y++1
yr
H yx
H
We now prove that preconditioning does not effect the local convergence properties.
Proposition 5. If A is symmetric real matrix, B is symmetric and positive definite, then the eigenvalues of AB are all real, and AB and have the same number of positive, negative and zero eigenvalues.
Proof. AB is similar and thus has the same eigenvalues B AB which symmetric and has real eigenvalues. Since B3 AB is congruent to A, they have the same number of positive, negative and zero eigenvalues (see Horn and Johnson (2013, Theorem 4.5.8)).
Proposition 6. Assume that P1 and P2 are positive definite. The Jacobian of (7) has only real eigenvalues at fixed points. With a suitable learning rate, all strictly stable fixed points of (7) are local minimax, and all local minimax are stable fixed points (7).
I
Pi
Proof. First, observe that both
and
are both always invertible. Hence
HHyy
Hyx
I
P2
fixed points of (7) are exactly stationary points. Let == my 7x. given by
Note that the Jacobian of (7) is
I
Pi
Hxx cHyx
Hgy -cHyy
J= 1/x
H vy
Hyx
P2
which is similar to
J
H yy Hyx
I
- H Hyr
!
P
Hxx
Hxy
Hyy yx
Hxy cH yy
=I 7x
P2
Therefore the eigenvalues of J are exactly those of Th (Hxx my P2yyy By Proposition 5, the cigenvalues of both matrices are all real. When the learning rates are small enough, i.e., when
Hxy Hy Hyx) and
2
7x max {p (Pı Hxy Hy, Hyx)) cp( -oc(-PPpp) P-Hyy)}
whether p(J) 1 solely depends whether P1 (Hxx Hxy HyyH and -P2Hyy have negative eigenvalues. By Proposition 5, the number positive, negative and zero eigenvalues the two matrices the same as those of Hxx Hxy H Hyx Hyx and - Hyy respectively. Therefore the proposition follows from the same argument as in Theorem
C.2 GENERAL-SUN STACKELBERG GAMES
general-sum Stackelberg game is formulated as follows. There a leader, whose action is x E R., and follower, whose action is y Itm The leader's cost function is given by f(x, y) while the follower's given by g(x, y). The generalization of minimax general-sum Stackelberg games is Stackelberg equilibrium.
Definition (Stackelberg equilibrium). (x*.y*) is (global) Stackelberg equilibrium ify E R(x"),
and Vx E X.
f(x",y")
max f(x,y),
yER(x)
where R(x)= arg min g(x.)) -) is the best response set for the follower.
15

---

Published as a conference paper at ICLR 2020
Similarly, we have local Stackelberg equilibrium (Fiez al., 2019) defined as follows. Definition 4 (Local Stackelberg equilibrium). (x",y" is local Stackelberg equilibrium if
1. y" is a local minimum of g(x",
2. Let r(x) be the implicit function defined by Vyg(x, in neighborhood of x' with r(x²) =y" Then x" is a local minimum of ((x) = f(x, r(x)).
For local Stackelberg equilibrium, we have similar necessary conditions and sufficient conditions. For simplicity, use the following notation when it is clear from the context
Hxx
Hxy
x
Gxy
42 (x)(x,))
V Vg
H
Hyy
Gyx
Gyy
Similar to the zero-sum case, local Stackelberg equilibrium can be characterized using derivatives. Proposition 7 (Necessary conditions). Any local Stackelberg equilibrium satisfies Vyg(x,,) O. V g y) 0 and
(xf(x,y) GxyG, V fx.
Hxx -Hxy Gyy Gyx Vx (Gxy Gyy V yyf) + V. (Gxy Vyf) Gyj > O.
Proposition (Sufficient conditions). If (x.y) satisfy Vyg(x.y) 0. Vxf(x.y) Gxy VyX O. V yx) and
Hxx Hxy Gyx Vx (Gxy G + Vy (y GyyGyx Gyx > 0.
then (x, y) a local Stackelberg equilibrium.
The conditions above can be derived from the definition with the observation that V²d(x) V (Vx (x)) Vyf(xx,(xx)
vr(x)) (v((x)
- xy /r Vx / Vr(x)) + V, (Vy Vr(x) = Hxx - Hxy yy Gyx Vx Gxx Vy.) + Vy (Gxy C Gyy Gyx-
Here all derivatives Rn++m -> IR, we mean the partial derivative of h for the first n entries. Similarly for h: Ra++ _ R by Vxh we mean the first n columns of the Jacobian of h, which is k-by-(n + m).
evaluated at (x, r(x)). We would like clarify that by Vxh, where h
Henceforth we will use Dxf(xx y) to denote Vx Gxy Gyy V (x, The general-sum version of Follow-the-Ride Ridge given by
X++1 y++1
X1 y1
Thx Dx I I Gyy Gyx
I
My V (x,,
Just as the zero-sum version of FR converges exactly to local minimax, we can show that the general- sum version of FR converges exactly to local Stackelberg equilibria. As in the zero-sum setting, we use stability of fixed points as a proxy discussing local convergence.
Theorem 3. The Jucobian of (8) has only real eigenvalues at fixed points. With a suitable learning rate, all strictly stable fixed points of (8) are local Stackelberg equilibria, and all local Stackelberg equilibria are stable fixed points of (8).
This theorem only analyzes the Jacobian of (8) at fixed points; thus we will only need to focus on the fixed points of (8) in the proof.
Proof.
I Gy Gyx I is always invertible. Therefore, the fixed points of (8)
Let c c= /// Note that Gyyx
exactly points (x. y) that satisfy Dxf(x, 0 and Vyg(x, y) 0, i.c. the first-order necessary condition for local Stackelberg equilibria.
Our definition is slightly different from that in Fiez al. (2019)
16

---

Published as a conference paper at ICLR 2020
In particular, consider fixed point z yx, The Jacobian of (8) at (x,y) is given by
Hxx - Vxy Hxy - Vy(Gxy Gyy vyf) dGyx
J I
1/x GyyGGyx I
cGyy
Observe that
G Gyy Gyx
1
J
GyyGyx 1
Hxx (xx GyyV
Hxy Vy(Gxy Gy y/) v
I
=I 7
Gyxx
Gyy
G yy Gyx
I
Hxx
Hxy Gyy GyGGys
Gyx
Vx (D)
Vy G yy Gyx
Hxy vy cGyy
=I 1x
0
where D is a shorthand for Gxy V Let
Hxx == Hxx Hxy Gyx
Gyx Vx (L) (L) Gy Gyx.
We can now that the eigenvalues of J are exactly those of I Zxx and those of I Fly Gyy. follows that all eigenvalues of J real. Suppose that
2
1x
(p( cp (Gyy)}
In that case, if yx, is local Stackelberg equilibrium, then from the second-order necessary condition, both Hxx and Gyy are positive semidefinite. As result, all eigenvalues of would be in (-1,1). By Definition 2, this suggests that yx is a stable fixed point.
On the other hand, if (x, y) a strictly stable fixed point, then all eigenvalues of J fall in (-1, 1),
which suggests that Hxx > 0 and Gyy > 0. By the sufficient condition, (x, is a local Stackelberg equilibrium.
Remark 2. From the proof above, it is can be seen that "strict local Stackelberg equilibria", i.e. points that satisfy the sufficient conditions, must strictly stable fixed points of (8). Then by Proposition 4, FR locally converges to such points. Thus, the set of points that FR locally converges to is the same as local Stackelberg equilibria, up to degenerate cases where the Jacobian spectral radius is exactly 1.
D EXPERIMENTAL DETAILS
D.1
Low DIMENSIONAL PROBLEMS
The algorithms we compared with are
X++1
V fx No) V [x yc)
+-
(GDA)
Ye+1
Yt
X(+1
X1
V [xf( Nt) Vxf(x,, N:)
V (x
+
2n
+
(OGDA)
Vt+1
Yt
Xt+1
X1
Vxf(x; V + 7/
ye+1
+-
Yt
yyJ(x; - (xx, V, Vy
(EG)
X(+1
Xx
I
-AH xy
V Vxf(Xi,
ye+1
+
Yt
AHyx
I
fx(,
(SGA)
X(+1
Vxf(xe. (xt.
(CO)
yr+1
yt
We used learning rate of 1) 0.05 for all algorithms. X = 1.0 for SGA and γ = 0.1 for CO. We did not find SGA with alignment (Balduzzi et al., 2018) to qualitatively different from SGA in our experiments.
HAx is always symmetric.
17

---

Published as a conference paper at ICLR 2020
D.2 MIXTURE OF GAUSSIAN EXPERIMENT
Dataset. The mixture of Gaussian dataset is composed of 5,000 points sampled independently from the following distribution pD(#) [, 0.01) + (0 0.01) + {A(44, 0.01) where M(,, o²) the probability density function of a ID-Gaussian distribution with mean μt and variance a², The latent variables z E IR_6 are sampled from standard Normal distribution (0 1). Because we want to use full-batch methods, we sample 5,000 points that we re-use for each iteration during training. For the two-dimensional case, we generate the data from 9 Gaussians with μlx E {-3, 0, 3) and My E (-3,,,,, 0,33. The covariance matrix is 0.01I.
Neural Networks Architecture. Both the generator and discriminator are 2 hidden layer neural networks with 64 hidden units and Tanh activations.
Other Hyperparameters. For FR, we use conjugate gradient (CG) in the inner-loop to approximately invert the Hessian. In practice, we use 10 CG iterations (5 iterations also works well). Since the loss surface is highly non-convex (let alone quadratic), we add damping term to stabilize the training. Specifically, we follow Levenberg- -aaeuurrr-rruurrrttt style heuristic adopted in Martens (2010). For both generator and discriminator, we use learning rate 0.0002. For consensus optimization (CO), we tune the gradient penalty coefficient using grid search over {0.01, 0.03, 0.1, 0.3, 1.0, 3.0, 10.0}.
D.3 MNIST EXPERIMENT
Dataset. The dataset we used in our experiment only includes class 0 and 1. For each class, take 4,800 training examples. Overall, we have 9,800 examples. The latent variables z E R64 are sampled from standard Normal distribution (O I).
Neural Networks Architecture. Both the generator and discriminator are 2 hidden layer neural networks with 512 hidden units and Tanh activations. For each fully-connected layer, we use spectral normalization to stabilize training.
Other Hlyperparameters. For FR, we use conjugate gradient (CG) in the inner-loop approximately invert the Hessian. In practice, we use 5 CG iterations for computational consideration. We also use the same damping scheme as MOG experiment. For both generator and discriminator, we use learning rate 0,0001. We use batch size 2,000 in our experiments.
D.4 COMPUTING CORRECTION TERM ON MOG AND MNIST EXPERIMENTS
The main innovation of this work is the introduction of the correction term which encourages both players (leader and follower) to stay close to the ridge. In the main paragraph, we focused on local convergence of our algorithm and essentially the Hessian matrix is constant. However, we know that the curvature (Hessian) of the loss surface might change rapidly in practice especially when both players are parameterized by deep neural networks, making the computation of Hessian inverse highly non-trivial. Here, summarize detailed steps in computing 7)x H X
1. Computing 1/x Hyx yx vx by finite difference b = Vy y) Vy - 7 vxf.y);
2. Assigning x
1 / such that the Hessian H below evaluated at the updated x;
3. Solving linear system H yy + XI) Ay = Hyy b using conjugate gradient to get an approx-
imation of Ay = (H yy + AI) Hyyb ss vx Hyy Vx/:
4. Adapting the damping coefficient À by computing reduction ratio
bbb fx, y) fy Vxf. Ay)
| Hy blp
which measures whether the loss surface is locally quadratic or not. We note that should be exactly 1 in the quadratic case if 0. We then adjust the damping with Levenberg- Marquardt style heuristic (Martens, 2010) as follows:
1.1A
0 < S 0.5
0.9A
if p 0.95
2.0A
if f 0 otherwise
A
18

---

Published as a conference paper at ICLR 2020
5. Setting Ay +- 0f 0 (essentially don't believe the approximation if p is negative).
When momentum or preconditioning is applied, we modify v above with the momentum or pre- conditioned version. To be specific, apply momentum and preconditioning before the computation of the correction term, Here, we give an example FR with momentum:
X(+1
I
I
1/x vx + mx,
y[+1
Yt
-
H H Hyx
I
Fy Vy. -
my,
mx,++1
M + 1/x xx
my,++1]
ymy,, -y vy
which is equivalent to (3). in the quadratic case since it is a linear dynamical system. Nevertheless, we argue that it is more effective use Eqn.(9) when the loss surface highly non-quadratic.
E ADDITIONAL RESULTS
E. THE ROLE OF PRECONDITIONING
Gradient deccent-ascent
FR with precorditionng
(50000 herations)
FR (500000 Beertionn)
generater
generstor
Figure 9: Ablation study on the effect of preconditioning. Vanilla FR also converges at the end of training though it takes much longer. The KDE plots Gaussian kernel with bandwidth 0.1.
Following the same setting Fig. 4, we investigate the effect of preconditioning for our algorithm. As we shown in section 4.1, FR is compatible with preconditioning with same theoretical convergence guarantee. In Fig. 4, the results of FR without preconditioning in Fig. 9. For fair comparison, we also tune the learning rate for vanilla FR and the optimal learning rate is 0.05. Our first observation is that vanilla FR does converge with 500,000 iterations which consistent with our theoretical results. Particularly, the discriminator is being fooled at the end of training and the gradient vanishes. Our second observation is that it takes much longer to converge, which can be seen from the comparison between the second column (preconditioned version) and the third column. With the same time budget (50,000 iterations), preconditioned FR already converges seen from the gradient norm curves while the vanilla FR is far from converged.
diagonal preconditioning for accelerating the training. Here, we report
E.2 THE ROLE MOMENTUM
In this subsection, we discuss the effect of momentum in algorithm. We first consider the following quadratic problem:
f(x.y) = -0.45x - 0.5x3 0.5y? 0.05y² + 2182 + Z2822
In this problem, 00 is a local (and global) minimax. We run FR with learning rate = 0.2 and momentum values 7 {0.0, 0.5, 0.8), and observe how fast the iterates approach the origin.
We also compare FR with gradient descent-ascend in this problem. Note that when learning rate ratio (ratio of the follower's learning rate to the leader's learning rate) is GDA diverges. We use
19

---

Published as a conference paper at ICLR 2020
grid search for the follower's learning rate My E {0.1, 0.4, and learning rate ratio
c E {5, 10, 20, 40, 80). We experiment with momentum 7 E 2,, =0.4, =..8). The best result for GDA without momentum is achieved by fly 0.8, 20; the best result for GDA
with momentum is achieved by fly = 1.6, c = 40 and y = 0.2. The results are plotted in Fig. 10.
10
GDA 0.2
Distance to origin
10
10-37
FR-0.5
10"34
GDA
10-99
FR
FR-0.8
-5
500
1000
1500
2000
-5.0
-2.5
0.0
2.5
5.0
7.5
10.0
iteration
Figure Left: distance the origin for GDA, GDA 0.2 momentum, FR, FR with momentum and FR with 0.8 momentum; Right: trajectory of each algorithm; we plot the values of xı and y/ and the contour for the function value on the plane (71, 0, V1, 0).
We that momentum speeds up FR dramatically. In contrast, GDA with momentum does not improve much over GDA without momentum. Moreover, under large momentum values (i.e. 7 0.8), GDA diverges even when using very large learning rate ratios.
Gradient Descent Ascent
Follow ridge (mom=0..) ())
ridge (mom=0
Follow the ridge (mom=0 9)
20003
andi
53555
1030
20093
15322
40000
59005
70090
19003
4000
2000
70000
$1530
43669
Figure 11: Empirical investigation on the effect of positive momentum. With larger momentum coefficient (e.g., = 0.9), the convergence of FR gets further improved. The KDE plots use Gaussian kernel with bandwidth 0.1.
We further test the acceleration effect of momentum on the mixture Gaussian benchmark. Keeping all other hyperparameters the same as those used in Fig, 4, conduct experiments with momentum coefficient 7 E {0.8, 0.9]. As shown in the gradient norm plots of Fig. 11, FR with large positive momentum coefficient converges faster than the with momentum (the second column). Particularly, FR is able to converge within 10,000 iterations with = 0.9, yielding roughly factor of improvement terms of convergence.
E.3 SPECTRUM FOR GAN MODEL
disc
schur
As we claimed in Section 6.2.1, all eigen- values of Hxx Hxy Hy are non- negative while all eigenvalues of Hyy are non-positive, Here we plot all eigenvalues of them in log scale. To be noted, we plot the eigenvalues for Hyy for convenience. As expected, the Hessian matrix for the discriminator negative semi-definite while the Schur compliment is positive semi-definite.
10:11
10
10-15
10-2
10-21
10:28
1000 2000 3000
4000
2000
4000
Figure 12: Top-20 20 eigenvalues.
20


Reviews:
[{"review_id": "r1x_rSVkqr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "In this paper, the authors introduce a new optimization algorithm for minimax problems, or finding equilibria in sequential \ntwo-player zero-sum games. Such problems are common in machine learning, including generative adversarial networks or primal-dual reinforcement learning. The commonly used gradient descent-ascent algorithm, corresponding to taking a gradient step for both players (or for both variables being minimized and maximized over), does not converge, in general, to local minimax points. Moreover, it can converges to fixed points which are not local minimax. To address these issues, the authors introduce the \"follow the ridge\" algorithm for minimax optimization problems. Given a minimax problem min_x max_y f(x, y), this algorithm consists in adding a correction term to the gradient corresponding to the y variable (corresponding to the max). This term is derived from the observation that minimax optimization should follow ridges (i.e. local maximum w.r.t. to y) of the function. Ridges can be defined as the implicit functions such that the gradient w.r.t. y is equal to zero, allowing to design an update that would stay \"close\" to the ridge. The correction term corresponding to the update thus involve the inverse of the Hessian w.r.t. y. The authors prove that all the fixed points of this algorithm are minimax, and that all local minimax are fixed points of the algorithm. The proof use first and second order conditions for local minimax points, which were recently derived in a paper by Jin et al. The proposed algorithm can also be used with momentum and preconditioning, and be generalized to Stackelberg games. Finally, the authors evaluate the follow the ridge algorithm on toy low dimensional GAN problems, as well as experiments on the MNIST dataset, showing better convergence that other methods used for minimax optimization problem.\n\nThe problem studied in this paper is an important one, as it arises in multiple area of machine learning such as adversarial \ntraining or reinforcement learning. It has also received significant attention from the community in the recent years. This paper propose a simple solution, which is well motivated, to the problem as well as a proof of convergence. A limitation of the proposed method is that it uses the Hessian of the problem, probably making it hard to apply on large  scale problems that are common in deep learning. I believe that it would make the paper stronger to discuss potential ways to mitigate this issue (e.g. inspired by L-BFGS), and their impact on theoretical guarantees. (Note that the authors briefly mention using the conjugate gradient algorithm in the experimental section).\n\nOverall, the paper is well written, and easy to follow (even for non-expert like me). I believe that it does a good job at introducing the problem and existing work on which it builds, and to motivate the proposed solution. I have not checked the proofs carefully, but they seem sensible. A small weakness of the paper is the experimental section: for example, I am not sure the MNIST experiments bring much to the paper, and would have preferred more convincing experiments. However, this is mostly a theoretical paper, and I do not think this is a big concern.\n\nTo summarize, I think the paper study an important problem, proposes a sound solution and is clearly written. For these reasons, I believe that the paper should be accepted to the ICLR conference. However, as I am not an expert on this area, my recommendation is a low confidence one.\n\n\nMinor comment: I believe that at the beginning of second paragraph of section 4, \"Suppose that y_t is a local minimum of f(x_t, .)\" should be \"maximum\".", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1xED6s2YB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 designs a set of dynamics for learning in games called follow-the-ridge with the goal of finding local stackelberg equilibria. The main theoretical results show that the only stable attractors of the dynamics are stackelberg equilibria. Moreover, the authors give a deterministic convergence rate for the vanilla algorithm and a convergence rate using momentum. Empirical results show the learning dynamics cancel out rotational components and drive the vector field to zero rapidly, while reaching good performance on simple GAN examples.\n\nReview: This paper focus on sequential games, which is the common formulation of GANs and a number of games in machine learning applications. From this perspective, it is natural to look at Stackelberg equilibria. In my opinion, the objective of the paper is important and relevant. The theoretical and empirical results are reasonably convincing. However, I do have some rather serious concerns about the general-sum game results and several questions regarding the relation to related work and the experiment details that need to be addressed.\n\n1. The FR dynamics in algorithm 1 are closely related to the dynamics in [1]. In particular, the Jacobian of the FR dynamics is a similarity transform of the Jacobian of the dynamics in [1]. As a result, each algorithm has the same set of stable attractors. This should probably be mentioned in the paper. Given this relation, it is not clear what the advantage of the FR dynamics are over the dynamics in [1]. Could you please discuss this?\n\n2. The gradient penalty regularization connection does not make sense in section 4.1. The optimization problem presented has an issue because the dimensions do not align in the constraint. The quantity \\nabla_x f(x, y)^T H_yy^{-1}\\nabla_x f(x, y) would not be defined if the dimensions of the players are not equal. \n\n3. In the related work it is claimed that two time-scale GDA converges only to local minimax and [2] is cited. I would avoid using this claim with respect to that paper since the statement following the main result in the paper is not right (see proposition 11 of [3] for proof). It is not clear what is meant when it is claimed that [1] can converge to non-local Stackelberg points. The dynamics in [1] only converge to local minimax points in the special case of zero-sum games.\n\n4. Since the dynamics in the paper are the closest to those in [1], it seems that the paper would be stronger by comparing with that set of dynamics. \n\n5. I found it to be quite impressive that the vector field is driven to zero in the GAN examples. Just to clear, for each algorithm when the ‘gradient norm’ is shown, does this mean the norm of the update for each norm or does it mean the individual derivative for each player. For example in FR, would it be the norm of the derivative with respect to the follower variable of the function or the norm of the update including the second order information?\n\n6. The path angle plot was interesting to see for the GAN example. The authors claim that the eigenvalues of the second order equilibria condition are non-negative. It would be nice if the authors could show the eigenvalues in the appendix and discuss how they were computed since it may be non-trivial to compute depending on the network size.\n\n7. The damping method to stabilize training is not quite clear. Could you provide more details about how this was done?\n\n\nMy primary concerns have to do with the portion of the paper considering general-sum games. I do not understand where proposition 7 and 8 come from. I am not convinced the definitions provided are necessary and sufficient conditions for Stackelberg equilibria. In [1], a differential Stackelberg equilibrium is defined. The definition in this paper does not appear to agree with the definition in [1]. The final positive definite condition in proposition 7 and 8 does not appear to be taking the total derivative 2 times when I evaluate the derivatives, so I am not sure what the quantity is. If this is not a proper set of conditions for the equilibria, then it would also mean that the dynamics do not only converge to equilibria in general-sum games. It is important that the authors clear up this concern since I do not believe Theorem 3 holds as a consequence of problems with propositions 7 and 8.\n\n[1] Fiez et al.,  \"Convergence of Learning Dynamics in Stackelberg Games\",  2019.\n[2] Heusel et al., \"GANs trained by a two time-scale update rule converge to a local Nash equilibrium\", 2017.\n[3] Mazumdar et al.,  \"On Finding Local Nash Equilibria (and only Local Nash Equilibria) in Zero-Sum Games\", 2019.\n\nPost Author Response: Thanks to the authors for the effort in discussing the paper with me. The authors made several changes to the paper in response to my comments including removing section 4.1, fixing comments about related work, including details on the damping procedure, showing experimental comparisons to [1] along with an explanation of why the dynamics in this paper may be preferred for training GANs, providing details on propositions 7 and 8 and including reference to [1], adding further assumptions on the functions, and attempting to make theorem 3 more clear. Overall, I think this paper proposes an interesting set of dynamics, several meaningful theoretical guarantees, and impressive empirical results. I would be curious to see how it performs on even more large-scale GAN problems in the future. As a result, I have changed my original score from a weak reject to a weak accept. My primary concerns with the paper regarded the general-sum convergence results and I appreciated the explanations from the authors. I am still of the opinion that theorem 3 could be stated more rigorously in the sense that the neighborhood on which the local convergence holds should be more explicit. It seems to me that the convergence result may only hold in a ball around an equilibrium in which the implicit function is well-defined and the FR dynamics will be attracted to r(x) and that this space could be arbitrarily small for some problems. Nonetheless, this result is only in the appendix, and the paper includes enough contributions beyond this to warrant acceptance. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "r1g-eWsqKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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\nThe present work proposes a new algorithm, \"Follow the Ridge\" (FR) that uses second order gradient information to iteratively find local minimax points, or Stackelberg equilibria in two player continuous games. The authors show rigorously that the only stable fixed points of their algorithm are local minimax points and that their algorithm therefore converges locally exactly to those points. They show that the resulting optimizer is compatible with heuristics like RMSProp and Momentum. They further evaluate their algorithm on polynomial toy problems and simple GANs.\n\nDecision\nI think that this is a solid paper that addresses the well-defined goal of finding an optimizer that only converges to local minimax points. This is established based on both theoretical results and numerical experiments. Since there has been a recent interest in minimax points as a possible solution concept for GANs, I believe the paper should be accepted.\n\nThe paper occasionally makes claims that the solutions of GANs should consist of local minimax points (\"We emphasize that GAN training is better viewed as a sequential game rather than the simultaneous game, since the primary goal is to learn a good generator.\"), which are not backed up by empirical results or reference to existing literature. If anything, the empirical results in this paper do not show improvement of the resulting generator (with the exception of the 1-dimensional example that has a particular rigidity since low discriminator output can easily restrict the movement of generator mass based on first order information). The right solution concept for GANs is not what the paper is about, but before publication the authors should remove these claims, identify them as speculative, or substantiate them .\n\nSuggestions for revision\n(1) In the last displayed formula on page 4 it should be the gradient w.r.t x.\n(2) Remove, substantiate, or mark as speculative the claims regarding the right notion of solution concept for GANs.\n\nQuestions to the authors\n(1) You write \" There is also empirical evidence against viewing GANs as simultaneous games (Berard et al., 2019). \". Could you please elaborate, why Berard et al. provides empirical evidence against viewing GANs as simultaneous games?\n(2) The Batch size for MNIST of 2000 is much larger than the values I have seen in other works. What is the effect of using more realistic batch sizes in training?\n(3) When measuring the speed with which consensus optimization and FR converge, shouldn't you allow consensus optimization five times as many iterations, since you are using five iterations of CG to invert the Hessians in each step?\n(4) You mention that you use CG to invert the Hessian, but the Hessian is not positive definite? Do you apply CG to the adjoint equations?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission proposes a novel solution for minimax optimization which has strong theoretical and empirical results as well as broad relevance for the community. The approach, Follow-the-Ridge, has theoretical guarantees and is compatible with preconditioning and momentum optimization strategies.

The paper is well-written and the authors engaged in a lengthy discussion with the reviewers, leading to a clearer understanding of the paper for all. The reviews all recommend acceptance. 
Decision: Accept (Poster)