LEAD: Min-Max Optimization from a Physical Perspective
Authors: Reyhane Askari Hemmat
Amartya Mitra
Guillaume Lajoie
Ioannis Mitliagkas
Venue: Accepted by TMLR ()

Abstract: Adversarial formulations such as generative adversarial networks (GANs) have rekindled interest in two-player min-max games. A central obstacle in the optimization of such games is the rotational dynamics that hinder their convergence. In this paper, we show that game optimization shares dynamic properties with particle systems subject to multiple forces, and one can leverage tools from physics to improve optimization dynamics. Inspired by the physical framework, we propose LEAD, an optimizer for min-max games. Next, using Lyapunov stability theory and spectral analysis, we study LEAD’s convergence properties in continuous and discrete time settings for a class of quadratic min-max games to demonstrate linear convergence to the Nash equilibrium. Finally, we empirically evaluate our method on synthetic setups and CIFAR-10 image generation to demonstrate improvements in GAN training.

Published in Transactions on Machine Learning Research (06/2023)
LEAD: Min-Max Optimization from a Physical Perspective
Reyhane Askari Hemmat"
Deportment of Computer Science and Operations Research University of Montreal and Mila, Quebec AT Institute
Amartya Mitra"
omitr009@ucrr.o edu
Department of Physics and Astronomy University of California, Riverside
Guillaume Lajoie
g. l.aaoose Dumontralll.
Deportment of Mathematics Statistics
University of Montreal and Mila, Quebec Al Institute Canada CLEAR Al chair
Toannis Mitliagkas
tounnis &iroo www.aatiiioooooommaraaaa..ao wwwnntrall.cc
Deportment of Computer Science and Operations Research University of Montreal and Miln, Quebec AI Institute Canada CIEAR Al chair
Reviewed on OpenReview: ht tp o/ en revi ew et /f or um P6 d= TY s62B
Abstract
Adversarial formulations such generative adversarial networks (GANs) have rekindled interest in two-player min-max games. A central obstacle in the optimization of such games is the rotational dynamics that hinder their convergence. In this paper, show that game optimization shares dynamic properties with particle systems subject to multiple forces, and one can leverage tools from physics to improve optimization dynamics. Inspired by the physical framework, we propose LEAD, an optimizer for min-max games. Next, using Lyapunov stability theory and spectral analysis, we study LEAD's convergence properties in continuous and discrete time settings for a class of quadratic min-max games to demonstrate linear convergence to the Nash equilibrium. Finally, we empirically evaluate our method on synthetic setups and CIFAR-10 image generation to demonstrate improvements in GAN training.
1 Introduction
Much of the advances in traditional machine learning can be attributed the success of gradient-based methods. Modern machine learning systems such as GANs (Goodfellow al., 2014), multi-task learning, and multi-agent settings (Sener & Koltun, 2018) in reinforcement learning (Bu et al., 2008) require joint optimization of two more objectives which can often be formulated as games. In these game settings, best practices and methods developed for singlo-objective optimization are observed to perform noticcably poorly (Mescheder et al., 2017; Balduzzi el al., 2018h; Gidel et al., 2019). Specifically, they exhibit rotational dynamics in parameter space about the Nash Equilibria (Mescheder et al., 2017), slowing down convergence. Recent work in game optimization (Wang et al., 2019; Mazumdar al., 2019; Mescheder al., 2017; Balduzzi et al., 2018b; Abernethy et. al., 2019; Loizou et al., 2020) demonstrates that introducing additional second-order terms in the optimization algorithm helps suppress these rotations, thereby improving convergence.
Taking inspiration from recent work in single-objective optimization that re-derives existing accelerated methods from a variational perspective ( (Wibisono et al., 2016; Wilson et al., 2016), in this work, we adopt
FEqual Contribution. Significant, part this work was done while Amartya Mitra was interning Mila.

---

Published in Transactions on Machine Learning Research (06/2023)
similar approach in the context of games. To do so, borrow formalism from physics by likening the gradient-based optimization of two-player (zero-sum) games to the dynamics of system where we introduce relevant forces that helps curb these rotations. We consequently utilize the dynamics of this resultant system to propose our novel second-order optimizer for games, LEAD.
Next, using Lyapunov and spectral analysis, we demonstrate linear convergence of our optimizer (LEAD) both continuous and discrete-time settings for a class of quadratic min-max games. In terms of empirical performance, LEAD achieves an FID of 10.49 CIFAR-10 image generation, outperforming existing baselines such as BigGAN (Brock et al., 2018), which is approximately 30-times larger than our baseline ResNet architecture.
What distinguishes LEAD from other second-order optimization methods for min-max games such as Mescheder et al. (2017); Wang et al. (2019); Mazumdar et al. (2019); Schäfer & Anandkumar (2019) is its computational complexity. All these different methods involve Jacobian (or Jacobian-inverse) voctor-product computation commonly implemented using a form of approximation. Thus making majority of them intraclable in real-world large scale problems. On the other hand, LEAD involves computing only one-block of the full Jacobian of the gradient vector-field multiplied by vector. This makes our method significantly cheaper and comparable to several first-order methods, as we show in section 6. We summarize our contributions below:
In section 3, model gradient descent-ascent as physical system. Armed with the physical model, we introduce counter-rotational forces to curb the existing rotations in the system. Next, employ the principle of least action to determine the (contimuous-time) dynamics. We then accordingly discretize these resultant dynamics to obtain our optimization scheme, Least Action Dynamics (LEAD).
In section 4, we use Lyapunov stability theory and spectral analysis to prove a linear convergence of LEAD in continuou and discrete-time settings for quadratic min-max games.
Finally, in section 7, we empirically demonstrate that LEAD is computationally efficient. Additionally, we demonstrate that LEAD improves the performance of GANs on different tasks such as 8-Gaussians and CIFAR-10 while comparing the performance of our method against other first and second-order methods.
The source code for all the experiments is available at https://github httpp:///gthabb..co/aaamiiiiiiie gam es es/LEAD. Furthermore, we provide a blog post that summarizes our work, which is also available at https:/rreylaneastari..e hwt.eeaaaaaaiiiighuubbb.b -ithub. io/LEAD. html.
2 Problem Setting
Notation Continuous time scalar variables are in uppercase letters (X), discrete-time scalar variables are in lower case (x) and vectors are in boldface (A). Matrices are in blackboard bold (M) and derivatives w.r.t. time are denoted as an over-dot (#). Furthermore, off- is equal to Mi,j for i * j, and equal to for i= where i 1, ,,,,..
Setting In this work, we study the optimization problem two-player zero-sum games,
min max / (X,Y),
(1)
X
where f: R" X Rd + R. and is assumed to be a differentiable w.r.t. X,Y E It to be noted that though developing our framework below, X, Y are assumed to be scalars, it is nevertheless found hold for the more general case of vectorial X and Y, as we demonstrate both analytically (Appendix C) and empirically, our theoretical analysis is found to hold.
function which is continuous and twice
2

---

Published in Transactions on Machine Learning Research (06/2023)
3 Optimization Mechanics
In our effort to study min-max optimization from physical perspective, we note from classical physics the following: under the influence of a net force F, the equation of motion of a physical object of mass m, is determined by Newton's 2nd Law,
mx=F.
(2)
with the object's coordinate expressed as x, X. According to the principle of least action (Landau & Lifshitz, 1960), nature "selects" this particular trajectory over other possibilities, as a quantity called the action extremized along it.
We start with a simple observation that showcases the connection between optimization algorithms and physics. Polyak's heavy-ball momentum (Polyak, 1964) is often perceived from a physical perspective as a ball moving in 'potential" well (cost function). In fact, it is straightforward to show that Polyak momentum is discrete counterpart of contimuous-time equation of motion governed by Newton's 2nd Law. For single-objective minimization of an objective function f (z:), Polyak momentum follows:
2k+1 = 2% + (zx zx-1) - V (xx),
(3)
where y) is the learning rate and is the momentum coefficient. For simplicity, setting B to one, and moving to continuous time, one rewrite this equation as,
(0k+s TR) (Ix
Tkk Fk-6)
7 va (IK),
(4)
82
and in the limit 6, + 0, (4) then becomes (I' (t) XX,
mx = -Vx
(5)
This is equivalent Newton's 2nd Law of motion (2). of a particle of mass m = =82/n, and identifying F = - V (X) (i.e. I (X) acting potential function (Landau & Lifshitz, 1960)). Thus, Polyak's haavy-ball method E3. can be interpreted as object (ball) of mass rolling down under potential f (X) to reach the minimum while accelerating.
Armed with this observation, we perform an extension of 5 to our min-max setup,
mX (X,,
(6)
mý = (x)(X,
which represents the dynamics of an object moving under curl force (Berry & Shukla, 2016): Feur (-Vxf, f) in the 2-dimensional X-Y plane, see Figure 1 (a) for simple example where the contimuous- time dynamic of curl force (or equivalently vortex force) diverges away from the equilibrium.
Furthermore, it is to be noted that discretization of (6) corresponds to Gradient Descent-Ascent (GDA) with momentum 1. Authors in (Gidel et al., 2019) found that this optimizer is divergent in the prototypical min-max objective, f (X,Y)= = XY, thus indicating the need for further improvement.
To this end, we note that the failure modes of the optimizer obtained from the discretization of (6), can be altributed to: (a) an outward rotatory motion by our particle of mass m, accompanied by (b) an increase in its velocity over time. Following these observations, dissipative forces to our system above, in order to tackle (a) and (b) in an attempt to achieve converging dynamics.
aim to introduce suitable counter-rotational and
Specifically, as an initial consideration, we choose to add to our system, two ubiquitous forces:
magnetic force,
F Fmag 10---(0-x-0
x)
(7)
1 Also referred the Principle of Stationary Action.
3

---

Published in Transactions on Machine Learning Research (06/2023)
known to produce rotational motion (in charged particles), to counteract the rotations introduced by Feur-- Here, is the charge imparted to our particle.
friction,
Firic (nX, uV)
(8)
to prevent the increase in velocity of our particle (μ: coefficient of friction).
Assimilating the above forces Feurl, Fmag and Firies the equations of motion (EOMs) of our crafted system then becomes,
mX = Feurl + Fmag + Firics
(9)
my Fonn + Fmag + Firic-
Or equivalently,
mX = -ux V vVx mř = -uY +yf+oVxrfX
(10)
Without loss of generality, from hereon set the mass of our object to be unity. In the rest of this work, we study the above EOMs in continuous and discrete time for min-max games. See Figure (c) for a simple example where the continuous-tine dynamic of a particle under all the above forces converges to the equilibrium.
Vortox
Start
Start
Start
frictios
vortek
Equilibrium
tmagrjotic
y
y
Equillorium
Equilibrium
maguelic
(a)
(b)
(c)
Pigure Depiction of the continuous dymamics a particle experiencing different forces. (a), particle inside a vortex diverges from the equilibrium. This corresponds to the continuous- time dynamics gradient descent-ascent with momentum in the bilinear game. In (b), we introduce a counter-rotational magnetic force to the existing system with the vortex force, assuming the particle is charged. The magnetic force is exerted in a perpendicular direction to current direction of the partiele and affects the rotations induced by the vortex. However, we do not observe convergence, which expected from a physics perspective. The vortex force is known to increase the particle's speed over time Berry & Shukla (2016), while the magnetic force does not affect the particle's speed. Therefore, the particle's velocity will keep increasing over time, preventing convergence. To decrease the particle's ' velocity for convergence, we introduce friction to the system in (c). As result, we observe that the friction causes the particle to lose speed and converge.
3.1 Discretization
With the continuous-time trajectory of (10) in hand, proceed to discretize it using combination of Euler's implicit and explicit discretization schemes. To discrotize X = Vx we have,
Euler Implicit Discretization Fk-1 2z. 80
(1I)
Euler Explicit Discretization Fh-1 - de
where 8 is the discretization step-size and k is the iteration step.
4

---

Published in Transactions on Machine Learning Research (06/2023)
Proposition 1. The continuous-time EOMs (10) be discretized in implicit- way, to yield,
Fk+1 I& + f( xx-1) v/V Uk)
a sy f (0k, Uk) (yk= yk-1),
(12)
U yh (yk yk-1) 1/ vf (It Vk)
+ a yz f (Ik, yk) (2x - Ik-1),
where we have defined a - μu and n 82 (Proof in Appendix B).
Taking inspiration from the fact that Eq. 10 corresponds to the trajectory of charged particle under curl, magnetic and frictional force, governed by the principle of least action, refer to the discrete update rules of Eq. 12 as Least Action Dynamics (LEAD). (Algorithm 1 details the pseudo-code of LEAD).
Understanding the terms in LEAD: Analyzing our novel optimizer, we note that it consist three types of terms, namely,
Gradient Descent or Ascent: vv Vyf: Each player's immediate direction of improving their own objective.
Standard Polyak momentum term; known to accelerate convergence in optimization and recently in smooth games. (Gidel et al., 2019; Azizian et al., 2020b; Lorraine & Duvenaud, 2022)
Momentum:
Coupling term:
wyy (Iz, 9k) (yx- yk- V y (Ix, Uk) (2x Tx-1)
Main new term in our method. Tt captures the first-order interaction between players. This cross-derivative corresponds the counter-rotational force in our physical model; it allows our method to exert control on rotations.
Algorithm Least Action Dynamics (LEAD)
Input: learning rate 77, momentum B, coupling coefficient Initialize: Zo f Zinit, Yo < Yinit, t 0
while not converged do
t t 1
Ix f- (xt, Mt)
Jxy Ay + V (g (1) 1/-1)
1++1 t + 3(1t xt-1) 179 Ogzy Av:
9y (x,, y1)
Iny A + V (g (xr - 1)
Mi+1 + V/ + B(g Vt-1) + n99 + agay Az
end while
return (I2+1, #1+
4 Convergence Analysis
We now study the behavior of LEAD on the quadratic min-max game,
h
(( Y)
s(x
(13)
where X, R", A Rd Rd is a (constant) coupling matrix and h is a scalar constant. Additionally, the Nash equilibrium of the above game lies above game, as,
X 0, Y 0. Let us further define the vector field of the
Vx/(X, Y) VYX Y)
hx + AY hY
(14)
X

---

Published in Transactions on Machine Learning Research (06/2023)
4.1 Continuous Time Analysis
A general way to prove the stability of dynamical system is to Lyapunov function (Hahn et al., 1963; Lyapunov, 1992). A scalar function & IR x R > R, is Lyapunov function of continuous-time dynamics if 4 4
(X, Y) 2 0, ( Y) 0
The Lyapunov function & can be perceived as a generalization of the total energy of the system and the requirement (it) ensures that this generalized energy decreases along the trajectory evolution, leading the system to convergence as we will show next.
For the quadratic min-max game defined in (13), Eq.(10) generalizes to,
X = (h+ A)Y QAY
(15)
Y = -u - (h 1 A X + X
Theorem 1. For the dynamics of (15);
X + pxx + ) T (x + + + HAY)
& =
2
+ (Y + JY -AA T +YY - -HAXx)
1
(16)
2
1
+ (h AA7)X y A
is a Lyapunov function of the system.
Furthermore, setting q (2/p) + ,e we find & s P31 for
p 11
2p(lonin h)) + 2h) (n² + 11) + 20 min
p S min
with miin being the smallest singular value of A. This consequently ensures linear convergence of the dynamics of Eq. 15,
Eo exp (-pl)
X
(17)
h + 2
(Proof in Appendix C).
4.2 Discrete- Timee Analysis
In this section, we next analyze the convergence behavior of LEAD, Eq. the case of the quadratic min-max game of E1.(, using spectral analysis,
xb++ = .t + 3Ax - Thaa - -Ays -AAAE
(18)
yx+1 yk 3Ayz T/yy nAT=, xxxx abd A
where Ary Fk --
For brevity, consider the joint parameters Wi == (x,, y:). We start by studying the update operator of simultancous gradient descent-ascent,
(w(w)) wi -))((:-1)-

---

Published in Transactions on Machine Learning Research (06/2023)
where, the rector-field is given by Eq. 14. Thus, the fixed point w" of (wr(w) satisfies Fy(w²) w".
Furthermore, at w*, we have,
VFn(W") Ln 18.-11 -1/Vow""")
(19)
with In being the n x identity matrix. Consequently the spectrum of VFi((*)) in the quadratic game considered, is,
Sp(VFr(w")) (1 -nnh-- y7i A Coofoflddiag/oo((
(20)
The next proposition outlines the condition under which the fixed point operator is guaranteed to converge around the fixed point.
Proposition 2 (Prop. 4.4.1 (Bertsekas, 1999)). For the spectral radius,
Pmar == p(VF, <1
(21)
and for some wo in neighborhood of w", the update operator F, ensures linear convergence to w" at rate,
4+1 S V
where A441 || w01l || w0
Next, we proceed to define the update operator of Eq.(12) as FLEAD (wr, (Wi-1. quadratic min-max game of (q.(1 the Jacobian of FLEAD takes the form,
For the
VFLEAD = 12n + MT (1 + a) Vo
TTn + aao
(22)
12n
the next Theorem 2, we find the set of eigenvalues corresponding to the update operator VLLEADD which are then used in Thcorem 3, where we show for selected values and a, LEAD attains linear rate.
Theorem 2. The eigenvalues of VFLRAD(W") are,
1- (m a)) + np VA
(23)
2
where,
A A = (1 (1 mh)2 4 - aa)
and X Sp(off-diag) Vo(w"))
Furthermore, for h, la). |8| << 1, we have,
(1) + ++))22² + 11212 + 32 2
#4 =1 - 1/h +
4
(24)
17 n a
+ >
(nh 33 -
2
and
(n + (1++))2) xx)² x² +- 1112 + ,32 2nh1
#_ R8
4
(25)
+ a
+ >
(B - -n))
2
7

---

Published in Transactions on Machine Learning Research (06/2023)
Im
Re
Figure 2: Dingram depicts positioning of the eigenvalues of GDA in blue (Eq. 19) and those of LEAD (egs. (24) and (25) with 3= h 0) in red. Eigenvalues iuside the black unit circle imply convergence such that the closer to the origin, the faster the convergence rate (Prop. 2). Every point solid blue and rod lines corresponds to specific choice of learning rate. No choice of learning rate results in convergence for gradient ascent descent method as the blue line is tangent to the unit circle. At the same time, for fixed value of LEAD shifts the eigenvalues (x+)) into the unit circle which leads to convergence to the radius of the red dashed circle. Note that LEAD also introduces extra of eigenvalues (n-) which close to and do not affect convergence.
proportional
See proof in Appendix D.
Theorem 2 states that the LEAD operator has two eigenvalues μ44, and μ_ for each À E Sp [off-diag[oo(<>]]] Specifically, μ.=.. can be viewed as a shift of the eigenvalues GDA in Eq.,, while additionally being the leading eigenvalue for small values h, 77, la] and [@]. (See Fig. 2 for a schematic description) Also, for small values of a, μ4 is the limiting eigenvalue while μ =
In the following Proposition, next show that locally, choice of positive decreases the spectral radius of v Fn (w=) defined as,
p := max max 11- 1111-11 AA
Proposition 3. For any X E Spl off-diag Vo(w")]], [
2 Im (Amox)
Vap(A) a= <O 00,
(26)
where Im(Amar) is the imaginary component of the largest eigenvalue Xmaz-
See proof in Appendix E.
Having established that small positive value of a improves the rate of convergence, in the next theorem, we prove that for a specific choice of positive a and r in the quadratic game (13), a lincar rate convergence to Nash equilibrium attained.
Theorem 3. Setting 17 A()m then we have V e >> 0,
A EO (1- 4(amaz h)2
a min
(1+ 8/2)h +
3/22
Ao
(27)
Omax + h
8(amaz h)2
where Gmax (mmin) the largest (smallest) eigen value of l and
A == || 31 ||: - w01
Theorem 3 ensures linear convergence of LEAD in the quadratic min-max game. (Proof in Appendix F).

---

Published in Transactions on Machine Learning Research (06/2023)
5 Comparison of Convergence Rate for Quadratic Min-Man Game
In this section, we perform a Big-O comparison of convergence rates of LEAD (Eq. 59), with several other existing methods. Below in Table 5 we summarize the convergence rates for the quadratic min-max game of Eq. 13. For each method that converges at the rate (((1-r)) we report the quantity r (larger r corresponds faster convergence). We observe that for the quadratic min-max game, given the analysis 3/2
in Azizian et al. (2020a), for h < max (A) and B > th)m "LEAD 2 TBG and FLEAD 2 ToG- Furthermore, for the bilinear case, where h = 0, LEAD has faster convergence rate than EG and OG.
Method Alternating-GDn
h/2L
Extra-Gradient (EG)
[h/LL + oin (A) 11612)
Optimistic Gradient(OG)
{h//L+ omin (A) /32222)
Consensus Optimization (CO)
122 /2/2L3; + omin (A) / i
LEAD (Th. 3)
(1 3/2)//22// + h) + o min// / m + h12 3h2 (8
(8(omma man + h))2
Big-O comparison of convergence rates LEAD against FG (Korpelevich, 1976), OG (Mertikoponlos et al., 2018) and CO (Mescheder et al., 2017) for the quadratic min-max game of Eq. 13. We report the EG, OG and CO rates from the tight analysis in Azizian et al. (2020a) and Alt-GDA from Zhang et al. (2022). For each method that couverges at the rate of O((1 r))),, we report the quantity (larger corresponds to faster convergence). Note that L = v max(h, d'axx ma)) }, is the Lipschitz constant of the vector field and and 12 is the Lipachitz-smoothness of |||u||?
Table 1:
6 Comparison of Computational Cost
In this section we first study several second-order algorithms and perform computational comparisons on an 8- 8-Gaussians generation task. The Jacobian of the gradient. vector field = (V= y). (x, y)) given by,
V (x, v yzf (x,
V aay (x,3) V Vf (2.
J =
(28)
Considering player x, LEAD update requires the computation of the term Vayf (xt, yk) (y): yk-1)) thereby involving only one block of the full Jacobian J. On the other hand Symplectic Gradient Adjustment (SGA) (Balduzzi et al., 2018a), requires the full computation of two Jacobian-vector products Jo v. Similarly, Competitive Gradient Descent (CGD) (Schäfer & Anandkumar, 2019) involves the computation of the following term,
(1+ f Mk) V flx yx)x)))))
along with the Jacobian-vector product,
v by of Dkd V Vyf(w yk).
While the inverse term approximated using conjugate gradient method, it still involves the computation of approximately ten Jacobian-vector products for each update. To explore these comparisons in greater detail and on models with many parameters, we experimentally compare the computational cost of our method with several other second as well first-order methods on the 8-Gaussians problem in Figure (architecture reported in Appendix J). We calculate the average wall-clock time (in milliscconds) per iteration. Results are reported on an average of 1000 iterations, computed on the same architecture and the same machine with forced synchronous execution. All the methods are implemented in Py Torocc Paszke et al. (2017) and SGA is replicated based on the official implementation 2.
Furthermore, we observe that the computational cost per iteration of LEAD while being much lower than SGA and CGD, is similar to WGAN-GP and Extra-Gradient. The similarity to Extre-Gradient is due to
PSGA official DeepMind implementation (non-zero sum setting): http:///gggggtthoo.o/////s///s/a wwwp///opmia///ygppeettttt..eeee graddagnnt-t---ajssteeee hebb/naatter//ypleettte Au Adjustnant. 1pynb
9

---

Published in Transactions on Machine Learning Research (06/2023)
Average per iteration (wus)
Extra-Adam
GP
LEAD
10a
SGA
CGD
10a
10a
0
1000
2000
3000
4000
5000
6000
7000
Size of hidden dimension
Figure Average computational cost per iteration of several well-known methods (non-saturating) GAN optimization. The numbers are reported on the S-Caussians generation task and averaged over 1000 iterations. Note that the y-axis is log-scale. We compare Competitive Gradient Descent (CGD) (53) (using official CGD optimizer code), Symplectic Gradient Adjustment (SGA) (6), Consensus Optimization (CO) (39), Extra-gradient with Adam (Extra-Adam) (17), WGAN with Gradient Penalty (WGAN CP) (21). Wc observe that per-iteration time complexity of our method is very similar to Extra-Adam and WGAN GP and is much cheaper than other second order methods such as CGD, Furthermore, by increasing the size of the hidden dimension of the generator and discriminator's networks we observe that the gap between different methors increases.
the fact that for each player, Extra-Gradien requires the computation of a half-step and a full-step, so in total each step requires the computation of two gradients. LEAD also requires the computation of a gradient (2f2) which is then used to compute (a multiplied by (3i- yk-1)). Using PyTorch, we do not require to compute faz and then perform the multiplication. Given Vfz the whole term Va (3): yk-1), is computed using PyTorchh' Autograd Vector-Jacobian product, with the computational cost of single gradient. Thus, LEAD also requires the computation of two gradients for each step.
7 Experiments
In this section, first empirically validate the performance of LEAD several toy well large- scale experiments. Furthermore, we extend LEAD based on the Adam algorithm to be used in large-scale experiments. See 2 for the detailed Algorithm.
7.1 Adversarial vs Cooperative Games
In Section we showed that using Auto-grad software tools such as TensorFlow and Py LEAD can be computed very efficiently and fast as extra-gradient. In this section we compare the perforamce of LEAD with several first order methods in toy setup inspired by (Lorraine & Duvenaud, 2022). Consider the following game,
min max xT (TA)y + x (I- (F((I-7) (II y
(29)
compare the performance of different methods in cooperative games, adversarial games, and any interpolation between the two. Namely, varying y from 0 to I changes the dynamics of the game from purely cooperative to adversarial. Many real-world applications such as GANs exhibit an analogous range of adversarial to cooperative changes during training (Lorraine & Duvenaud, 2022).
Such formulation Eq. 29 enables
In Figure 4, we compare LEAD against several methods including gradient descent-ascent (GDA), extragradient (EG) (Korpelevich, 1976), optimistic gradient (OG) (Mertikopoulos al., 2018), complex momentum (CM) (Lorraine Duvenaud, 2022), negative momentum (NM) (Gidel et al., 2019), and positive momentum (PM) (Polyak, 1964). Each method is tuned optimality for each setup.
10

---

Published in Transactions on Machine Learning Research (06/2023)
1.00
Spectral Radius
0.85
95
PM CM (22)
NM
EG
0.60
0.2
0.8
Ymax
Figure 4: Comparison of several methods the game in Eq. 29. The diagonal matrix determines the degree of adversarialness along each direction. Flements on the diagonal are sampled from uniform distribution, Uniff0, ?maz]. By varying Timar from 0 to 1, move from purely cooperative setup to hybrid setup with mixture of cooperative and adversarial games. The spectral radius (shown the y-axis) determines the convergence rate this game and is function of Ymaz. The smaller the spectral radius, the faster the convergence rate. A spectral radius of corresponds compare several methods including gradient descent-ascent. (GDA), extragradient (EG) (Korpelevich, 1976), optimistic gradient (OG) (Mertikopoulos et al., 2018), complex momentum (CM) (Lorraine & Duvenaud, 2022), negative momentum (NM) (Gidel et al., 2019), and positive momentum (PM) (Polyak, 1964). Each method has been tuned to optimality cooperative games (on the leftmost), LEAD and Positive Momentum achieve great performance. In more adversarial settings (on the rightmost), LEAD performs on par with other game-specific optimization methods (excluding Negative Momentum, GDA and Positive Momentum which diverge). This plot suggests that LEAD a robust optimizer across different types of games. We conjecture that for the same reason, LEAD performs desirably in real-world sctups such as CANs where the adversarialness changes dynamically throughout the training (Lorraine & Duvenaud, 2022).
non-convergent dynamics. We
each setup. For
7.2 Generative Adversarial Networks
We study the performance of LEAD in zero-sum as well as non-zero sum settings. See Appendix for comparison of LEAD-Adam against vanilla. Adam on the generation task of a mixture of 8-Gaussians.
We evaluate LEAD-Adam on the task of CIFAR-10 (Krizhevsky Hinton, 2009) image generation with non-zero-sum formulation (non-saturating) on DCGAN architecture similar Gulrajaní et al. (2017). As shown in Table. 2, compare with several first-order and second order methods and observe that LEAD-Adam outperforms the rest in terms of Fréchet Inception Distance (FID) (Heusel FID score of 19.27-10.10 which
CIFAR-10 DCGAN:
et al., 2017) and Inception score (IS) (Salimans et al., 2016) 3, reaching outperforms OMD (Mertikopoulos et al., 2018) and CGD (Schäfer & Anandkumar, 2019). See Figure 5 that shows the improvement of FID using LEAD-Adam vs vanilla Adam and Figure 9 for a sample of the generated images.
CIFAR-10 ResNet: Furthermore, we evaluate LEAD-Adam on more complex and deep architectures. We adapt the ResNet architecture in SN-GAN Miyato et al. (2018). We compare with several existing results the task of image generation on CIFAR-10 using ResNets. See Table 2 for full comparison. Note that state of the art performance in recent. work such Style-GAN based models (Sauer et al., 2022; Kang et al., 2021; Lee et al., 2021) or BigGAN based models (Brock et al., 2018; Lorraine & Duvenaud, 2022) use architectures that are 30 times or more larger than the architecture that we have chosen to test our method on.
We report our results against a properly tuned version of SNGAN that achieves an FID of 12.36. Our method obtains a competitive FID of 10.49. We give a detailed description of these experiments and full detail on the architecture and syper-paramedd in Appendix J. See also Figure 10 for sample of generated samples ResNet using T.FAD-Adam
TThe FID and metrics for evaluating the quality of generated samples generative model. Lower FID and higher inception score (IS) correspond better sample quality.
11

---

Published in Transactions on Machine Learning Research (06/2023)
Adam
LEAD-Adarn
40
25-
20
100
200
300
400
Epochs
Figure Plot showing the evolution of the FID over 400 epochs for method (LEAD-Adam) vs vanilla Adam on DCGAN architecture. It is important to note that compared the Adam, Adam is twice expensive computationally.
Table Performance of several methods on CIFAR-10 image generation task. The FID and IS reported over 50k samples unless mentioned otherwise.
DCGAN
FID (4)
IS (1)
Adam (Radford et al,, 2015)
24.38
0.13
6.58
LEAD-Adam
19.27 1 0.10
7.584 0.11
CGD WGGN (Schäler & Anandkumar, 2019)
21.3
7.2
OMD (Daskalakis al., 2018)
29.6 = 0.19
5.74 + 0.1
ResNet
SNGAN
12.10 +: 0.31
8,58
+: 0.03
HEAD-Adam (ours)
10.49
0.11
8.82 + 0.05
ExtraAdam [Gidel et 2018)
16.78
0.21
8.47
1 0.1
LA-GAN (Chavdarowa et al., 2020)
12.67
0.37
8.53
0.04
ODE-GAN (Qin et al., 2020)
11.85
0.21
8.61 = 0.06
Evaluated with 5k samples
SN-GAN (DCGAN) (Miyato et al., 2018)
29.3
7.42 + 0.08
SN-GAN (ResNet) (Miyato et al., 2018)
21.7 + 0.21
8.22
0.05
8
Related Work
Game Optimization: With increasing interest in games, significant effort is being spent in understanding common issues affecting optimization in this domain. These issues range from convergence to non-Nash equilibrium points, to exhibiting rotational dynamics around the equilibrium which hampers convergence. Authors in Mescheder et al. (2017) discuss how the eigenvalues of the Jacobian govern the local convergence propertics of GANs. They argue that the presence of cigenvalues with zero real-part and large imaginary part results oscillatory behavior. To mitigate this issue, they propose Consensus Optimization (CO). Along similar lines, Balduzzi et al. (2018b); Gemp & Mahadevan (2018); Letcher al. (2019); Loizou al. (2020) use the Hamiltonian of the gradient vector-field to improve the convergence in games through discntangling the convergent parts of the dynamics from the rotations. Another line of attack taken in Schäfer & Anandkumar (2019) is to use second-order information as regularizer of the dynamics and motivate the use of Competitive Gradient Descent (CGD). In Wang et al. (2019), Follow the Ridge (FtR) is proposed. They motivate the use of a second order term for one of the players (follower) as to avoid the rotational dynamics in a sequential formulation of the zero-sum game. See appendix K for full discussion on the comparison of LEAD versus other socond-order methods.
Another approach taken by Gidel et al. (2019), demonstrate how applying negative momentum over GDA can improve convergence in min-max games, while also proving linear rate of convergence in the case of bilinear games. More recently, Zhang& & Wang (2021) have shown the suboptimality of negative momentum in specific settings. Furthermore, in (Lorraine & Duvenaud, 2022) authors carry-out an extensive study on the effect of momentum in games and specifically show that complex momentum is optimal in many games ranging from adversarial to non-adversarial scttings. Daskalakis et al. (2018) show that extrapolating the next value of the gradient using previous history, aids convergence. In the same spirit, Chavdarova al. (2020), proposes Look Ahead GAN (LA-GAN) and show that the Look Ahead algorithm is compelling candidate in improving
12

---

Published in Transactions on Machine Learning Research (06/2023)
convergence in GANs. Gidel et al. (2018) also explores this line of thought by introducing averaging to develop variant of the extra-gradient algorithm and proposes Fatra--Adam-Averaging Similar to Extra- Adam--veraging is SN-EMA Yazııı et al. (2019) which uses the SN-GAN and achieves great performance by applying an exponential moving average on the paramcters. More recently, Fiez & Ratliff (2021) study using different time-scales for each player in zero-sum non-convex, non-concave games. Furthermore, in Rosca et al. (2021) authors study the dynamics of game optimization in both continuous and discrete time and examine the effects of discritization drift on the game performance. They suggest a modified continuous-ting dynamical system that more closely matches the discrete time dynamics and introduce regularizers that mitigate the effect harmful drifts.
Lastly, in regard to convergence analysis in games, Zhang et al. (2022) study the convergence of alternating gradient descent-ascent for minmax games, Golowich et al. (2020) provide last iterate convergence rate for convex-concave saddle point problems. Nouiched et al. (2019) propose a multi-step variant of gradient descent-ascent, to show it can find game's c-frrstoorder stationary point. Additionally, Azizian al. (2020a) and Tbrahim et al. (2020) provide spectral lower bounds for the rate of convergence in the bilinear setting for an accelerated algorithm developed in Azizian et al. (2020b) for specific families of bilinear games. Furthermore, Ficz& & Ratliff (2020) use Lyapunov analysis to provide convergence guarantees for gradient descent ascent using timescale separation and in Hsich et al. (2020), authors show that commonly used algorithms for min-max optimization converge to attractors that are not optimal.
Single-objective Optimization and Dynamical Systems: The authors of Su et al. (2014) started a new trend in single-objective optimization by studying the continuous- time dynamics of Nesterov's accelerated method (Nesterov, 2013). Their analysis allowed for a better understanding of the much-celebrated Nesterov's method. In similar spirit, Wibisono et al. (2016); Wilson et al. (2016) study continuousttime accelerated methods within a Lagrangian framework, while analyzing their stability using Lyapunov analysis. These work show that a family of discrete-time methods can be derived from their corresponding contimuuus-tine formalism using various discretization schemes. Additionally, several recent work (Muchlebach & Jordan, 2019; Bailey & Piliouras, 2019; Maddison et al., 2018; Ryu et al., 2019) cast game optimization algorithmss as dynamical systems so to leverage its rich theory, to study the stability and convergence of various continuous- time methods. Nagarajan & Kolter (2017) also analyzos the local stability of GANs as approximated continuous dynamical system.
9 Conclusion and Future Direction
In this paper, we leverage tools from physics to propose a novel second-order optimization scheme LEAD, to address the issuc of rotational dynamics in min-max games. By casting min-max game optimization as a physical system, we use the principle of least action to discover an effective optimization algorithm for this setting. Subsequently, with the use of Lyapunov stability theory and spectral analysis, we prove L.EAD to be convergent at linear rate in bilinear min-max games. We supplement our theoretical analysis with experiments on GANs and toy setups, demonstrating improvements over bascline methods. Specifically for GAN training, we observe that our method out performs other second-order methods, both in terms of sample quality and computational efficiency. Our analysis underlines the advantages of physical approaches in designing novel optimization algorithms for games as well as for traditional optimization tasks.
It is important to note in this regard that our crafted physical system is a way to model min-max optimization physically. Alternate schemes to perform such modcling can involve other choices of countor-rotational and dissipative forces which can be explored in future work. Other directions for future work can extend the Lyapunov analysis to the general convex-concave setting. Our existent analysis and the subsequent promising experimental results there upon, makes us believe that analysis can be extended to the more general convex-concave setting. Nevertheless, such an attempt is dependent on finding an appropriate Lyapunov function which may be challenging given the complex game dynamics.
As a future direction, one may pursue other types of games where LEAD may be uscful. Any 2- 2-parameter dynamical system can be interpreted as a 2-player game. Since LEAD models second-order interactions of the players, it may be a preferable optimization algorithm for games with higher-order structure. Furthermore,
13

---

Published in Transactions on Machine Learning Research (06/2023)
studying the performance of LEAD on larger GAN architecture such as Style-GAN may be studied in future work.
Broader Impact Statement
While contribution is mostly thcorctical, rescarch has the potential to improve the optimization of multi-agent machine learning models, such as generative adversarial networks (GANs). GANs have been very successful in generating realistic images, music, speech and text, and for improving performance on an array of different real-world tasks. On the other hand, GANs can be misused to generate fake news, fake images, and fake voices. Furthermore, a common problem encountered during GAN training mode-collapse. This results GANs being biased in generating certain types of data moreover others, thereby causing data misrepresentation. In this paper, we show that our proposed method can tackle the mode collapse problem by observing improvements over baseline methods. However, we would like to emphasize that practitioners should use research with caution as the change of dataset and tasks might not prevent the mode collapse problem.
Acknowledgments
The authors would like thank Mohammad Pezeshki, Gauthier Gidel, Tatjana Chavdarova, Maxime Laborde, Nicolas Loizou, Hugo Berard, Giancarlo Kerg, Manuela Girotti, Adam Ibrahim, Damien Scieur and Michael Mulligan, for useful discussions and feedback.
This work is supported by NSERC Discovery Grants (RGPIN-2018-0482) and RGPIN-2019-06512), FRQNT Young Investigator Startup Grants (2019-NC-253551 and 2019-NC-257943), a startup grant by IVADO, the Canada CIFAR AI chairs program and collaborative grant from Samsung Electronics Co., Ltd.
Reyhane Askari Hemmat also acknowledges support of Borealis AT Graduate Fellowship, Mierosoft. Diversity Award and the NSERC Postgraduate Scholarships. Amartya Mitra acknowledges support of the internship program at Mila and the UCR Graduate Fellowship.
This research was enabled in part by compute resources, software and technical help provided by Mila (mila.quebec)) and Compute Canada.
References
Jacob Abernethy, Kevin A Lai, and Andre Wibisono. Last-iterate convergence rates for min-max optimization. arXiv preprint arXiv:1906 020602 2019.
Waiss Azizian, Toannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. A tight and unified analysis of gradient-based methods for whole spectrum of differentiable games. International Conference on Artificial Intelligence and Statistics, pp. 2863 2873, 2020a.
Waiss Azizian, Damien Scieur, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. Accelerating smooth games by manipulating spectral shapes. International Conference on Artificial Intelligence and Statistics, 2020b.
James P Bailey and Georgios Piliouras. Multi-agent learning network zero-sum games is a hamiltonian system. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 233-241. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
D Balduzzi, S Racaniere, J Martens, J Focrster, K Tuyls, and T Gracpel. deepmind-spmpleeti-gnaeeen adjuslment, 2018a. https: //tttt/////tbb//// httpiittuu..oooeeepeeiieeeee httpp//////ppppeeeeeeeieeiaaaaaa Symplectic_Gradde Gradientt Arr.dieett.duuustmeettttttttettt ipynb.
D Balduzzi, Racaniere, J Martens, Foerster, K Tuyls, and T Graepel. The mechanics of n-player differentiable games. In ICML, volume 80, pp. 363-372. JMLR. org, 2018b.
MV Berry and Pragya Shukla. Curl force dynamics: symmetries, chaos and constants of motion. New Journal of Physics, 1866:0063018, 2016.
14

---

Published in Transactions on Machine Learning Research (06/2023)
Dimitri P Bertsekas. Nonlinear programming. Athena scientific Belmont, 1999.
Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale gan training for high fidelity natural image synthesis. arxiv preprint 1XX::1809.11190 2018.
Lucian Bu, Robert Babu, Bart De Schutter, et al. A comprehensive survey of multiagent reinforcement learning. IEFE Transactions on Systems, Man, and Cybernetics, Part C' (Applications and Reviews), 38 (2):156 172, 2008
Tatjana Chavdarova, Matteo Pagliardini, Martin Jaggi, and Francois Fleuret. Taming gans with lookahead. arXiv preprint arXiv:2006.1450 2020.
Constantinos Daskalakis, Andrew Nlas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In International Conference on Learning Representations, 2018.
Tanner Fiez and Lillian Ratliff. Gradient descent-ascent provably converges to strict local minmax equilibria with a finite timescale separation. arXiv preprint arXiv:2009.14820 2020.
Tanner Fiez and Lillian Ratliff. Local convergence analysis of gradient descent ascent with finite timescale separation. In Proceedings of the International Conference Learning Representation, 2021.
Jakob Foerster, Richard Y Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-learning awareness. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 122 130. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
Ian Gemp and Srichar Mahadevan. Global convergence to the equilibrium of gans using variational inequalities. arXiv preprint Xiv: 1 1808.01531, 01531, 2018.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. variational incquality perspective on generative adversarial networks. In International Conference on Learning Representations, 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, pp. 1802-1811, 2019.
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. arXiv preprint arXi::2002.0055 2020.
Ian Goodfellow, Jean Pouget-Abadic, Mchdi Mirza, Bing Xu, David Warde- Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information processing systems, pp. 27780,680.22 2014.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. In Advances in neural information processing systems, pp. 5767-5777, 2017.
Wolfgang Hahn, Hans H Hosenthien, and H Lehnigk. Theory and application of Liapunov's direct method. Prentice-Hall Englewood Cliffs, NJ, 1963.
Martin Heusel, Hubert Ramsaner, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by two time-scale update rule converge a local nash equilibrium. In Advances in neural information processing systems, pp. 6626-6637, 2017.
Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min-max optimization algorithms: convergence to spurious non-critical sets. arXiv preprint arXiv:2006.000 090665 2020.
Adam Ibrahim, Waiss Azizian, Gauthier Gidel, and Ioannis Mitliagkas. Linear lower bounds and conditioning of differentiable games. In International conference on machine learning, 2020.
15

---

Published in Transactions on Machine Learning Research (06/2023)
Minguk Kang, Woohyeon Shim, Minsu Cho, and Jaesik Park. Rebooting acgan: Auxiliary classifier gans with stable training. Advances in Neural Information Processing Systems, 1123505-233111 2021.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ar preprinl 1f1.i:1412.666 6980, 2014.
GM Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12: 747 756, 1976.
Alex Krizhevsky and Geoffre Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
LD Landau and EM Lifshitz. Course of theoretical physics. vol. 1: Mechanics. Oxford, 1960.
Kwonjoon Loe, Huiwen Chang, Lu Jiang. Han Zhang, Zhuowen Tu, and Ce Liu. Vitgan: Training gans with vision transformers. Xix preprint arXiv:2107. 04589489..99 2021.
Alistair Letcher, David Balduzzi, Sébastien Racaniere, James Martens, Jakob N Foerster, Karl Tuyls, and Thore Graepel. Differentiable game mechanics. Journal of Machine Learning Research, 20(84):1-40, 2019.
Nicolas Loizou, Hugo Berard, Alexia Saicoeur-Martineau Pascal Vincent, Simon Lacoste-Julien, and loannis Mitliagkas. Stochastic hamiltonian gradient methods for smooth games. ICML, 2020.
David Acuna Paul Vicol Lorraine, Jonathan P. and David Duvenaud. Complex momentum for optimization in games. In International Conference on Artificial Intelligence and Statistics, pp. 7742-7765. PMLR, 2022.
Alcksandr Mikhailovich Lyapunov. The general problem of the stability of motion. International journal of control, 55(3):531-534 -534, 1992.
Chris J Maddison, Daniel Paulin, Yee Whye Teh, Brendan O'Donoghue, and Arnaud Doucet. Hamiltonian descent methods. arXiv preprint 1xXxx:8099.0000 2018.
Eric V Mazundar, Michael Jordan, and S Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. arXiv preprint 1xXi:119010000 2019.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in padtte-point problems: Going the extra (gradient) mile. arXiv preprinl Xr:: (ff::887.0222 02629, 2018.
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of gans. In Advances in Neural Information Processing Systems, pp. 1825-1835, 2017.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprint arXiv:1802.08 05957, 2018.
Michael Muchlebach and Michael Jordan. A dynamical systems perspective on nesterov acceleration. In International Conference on Machine Learning, pp. 4656-4662, 2019.
Vaishnavh Nagarajan and J Zico Kolter. Gradient descent gan optimization is locally stable. In Advances in neural information processing systems, pp. 5585-5595, 2017.
Yurii Nesterov. Introductory lectures on conver optimization: basic course, volume 87. Springer Science & Business Media, 2013.
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. In Advances in Neural Information Processing Systems, pp. 14934 14942, 2019.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. 2017.
16

---

Published in Transactions on Machine Learning Research (06/2023)
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathemalics and Mathematical Physics, 4(5):1-17, 1964.
Chongli Qin, Yan Wu, Jost Tobias Springenberg, Andrew Brock, Jeff Donahue, Timothy Lillicrap, and Pushmeet Kohli. Training generative adversarial networks by solving ordinary differential equations. arXiv preprint Xr1::20010. 15040, 2020.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv:1511.06494, 2015.
Mihaela C Rosca, Yan Wu, Benoit Dherin, and David Barrett. Discretization drift in two-player games. In PMLR, 2021.
International Conference on Machine Learning, pp-
Ernest K Ryu, Kun Yuan, and Wotao Yin. Ode analysis of stochastic gradient methods with optimism and anchoring for minimax problems and gans. Xi preprinl arXiv: 10899, 2019.
Tim Salimans, Tan Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans, In Advances in neural information processing systems, pp. 2234 2242, 2016.
Axel Sauer, Katja Schwarz, and Andreas Geiger. Stylegan-xl: Scaling stylegan to large diverse datasets.
ACM SIGGRAPH 2022 Conference Proceedings, pp. 1-10, 2022.
Florian Schäfer and Anima Anandkumar. Competitive gradient descent. In Advances in Neurol Information Processing Systems, pp. 7623-7633, 2019.
Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimization. In Advances in Neural Information Processing Systems, pp. 527-538, 2018.
Bin Shi, Simon S Du, Weijic Su, and Michael Jordan. Acceleration via symplectic discretization of high- resolution differential equations. In Advances in Neural Information Processing Systems, pp. 5745 5753, 2019.
Weijie Su, Stephen Boyd, and Emmanuel Candes. A differential equation for modeling nesterov's accelerated gradient method: Theory and insights. In Advances in Neural Information Processing Systems, pp. 2510 2518, 2014.
Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A follow-the-ridge approach. In International Conference on Learning Representations, 2019.
Andre Wibisono, Ashia C Wilson, and Michael I Jordan. A variational perspective on accelerated methods in optimization. Proceedings of the National Academy of Sciences, 113(47):E7351-E7333 2016.
Ashia Wilson, Benjamin Recht, and Michael Jordan. A Iyарunov analysis of momentum methods in optimization. arXiv preprint Xrm 1.02635, 2016.
Yasin Yazıcı, Chuan-Sheng Foo, Stefan Winkler, Kim-Hui Yap, Georgios Piliouras, and Vijay Chandrasekhar. The unusual effectiveness of averaging in gan training, 2019.
Guodong Zhang and Yuanhao Wang. On the suboptimality of negative momentum for minimax optimization. In International Conference on Artificial Intelligence and Statistics, pp. 2098 2106. PMLR, 2021.
Guodong Zhang, Yuanhao Wang, Laurent Lessard, and Roger Grosse. Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization. In International Conference on Artificial Intelligence and Slatislics, pp. 7659 7679. PMLR, 2022.
17

---

Published in Transactions on Machine Learning Research (06/2023)
A Appendix
B Proof of Proposition
Proof. The EOMs of the quadratic game in continuous-time (Eq,()0)), can be discretized in using combination of implicit and explicit update steps as (Shi et al., 2019),
xk+1 2g 6v
(30a)
1k-1 yk = 5v
(30b)
uk+1 Uk -qdV fy (0ks yu) v yóvu oV (2), 2 2t1 " = goV.yf f (I yk) vf pd0k + oV of (IK: Mk)
(30c)
(30d)
where is the discretization step-size. Using Equs. (30a) and (30b), we can further re-express Equs. (30c), (30d)
88
#b+1 = Tkk + 3A 7, Vas (#x 4k) - a V 2.y (I's 9k) Ays yk+1 = yk + BAyk + 1, of (Irks 8k) a x.y. (Th, ykk Dark
(31)
where Arx 26 - 11 and,
8 = 1 - μō, = 8², a= =296
(32)
C
Continuous-time Convergence Analysis: Quadratic Min-Max Game
Proof. For the class of quadratic min-max games,
)(X,Y) h h 2 2
x X
(33)
where X = (x x²) Y (Y,,... r") E R and Anxa is constant positivo-defnite matrix, the continuous-time FOMs of (10) become:
X - hX AY QAY
(34)
Y = = hY + A X q X
We next define our continuous-time time Lyapunov function in this case be,
X + px + HAY)" T (X + μX - HAY
&
2
1
(Ý + WY -A x²" (x + PY UA x)
(35)
1
(X x + YT +
Y A
2
2 20
The time-derivative of & is then given by,
== + ux + FAYY T + + (Ý + +WY =A"x) T (Y + - x)
+ x +2 + +Y
-X" +xx" + AYY"" -Y) + (-qRE-pX
- -xX -1X-AY) AYY
+ +(* - (==" + ST (qA - ur + A
(36)
= = u) ( - -2 + +Y
(x"
AA (X+ - -TÝ)
18

---

Published in Transactions on Machine Learning Research (06/2023)
where we have used the fact that XTAY being scalar thus implying XTAY YTAXX. If we now set q =2//M) + y in the above, then that further leads to,
E. = (x T (h + AA AAT)X X Y (h - =X YTY) = = 14
(37)
|| 2 M| YI + || X + x +|AAI| - (1
+ 1|-1)) SOVP
exhibiting that the Lyapunov function, (16) is asymplotically stable at all times t.
Next, consider the following expression;
-PE
Pf || x 1 PM Y - PM 2
2 1| AYII PM
2 || + &12
-PE 2 |X|2 + +|111() + pp (x + +Y - PH (1|x|| + [
pH
pp (x T AY - -X-AX)= - PH (1147) x 11+ + [1471))
2
(38)
=-p(1 + 1)) (|x11| + +11x11) P (1² +M+ 2h) (IX + +|x11²)
- - (n² [n² + + + 2) (|A*X||+||AYTP)) +1AAY|)
S -pp:
where p is some positive definite constant. This implies that the above expression is negative semi-definite by construction given μ 2 O. Now, for a general square matrix A. we can perform singular value decomposition (SVD) as A VTSU. Here, U and V are the right and left unitaries of A, while S is diagonal matrix of singular values (o+) of A. Using this decomposition in Eq.(38), then allows us to write,
- -1 + u) (| + +1211²) 2 (n² + + +
+ +
2 (n² + (1[ATX]) x1² + +1[Ay11))
= =-p(1 + 11) (|/V1) 1 + +||U8| 12) - (n² + 21:)
P (n² + / #+2? 2) (ISVX 1 + ||SUY I²)
2
=-p(1 + 11) (1) ||2 + +11>11) - / (u² + + 2h) +
(39)
P (n² + 4 # 2) (1sx1) 2 + [[S
2
n
- Σ p(1 + 14) (110)1 + +113ン11²)
12 Σ (11 00² + + 2h) (1² + n) + +20)) (1130|/+ + [|D0)1?)
where we have made use of the relations V'- UV U, vTV VVT, and additionally performed a basis change, as X VX and y UY. Now, we know from (37) that,
& = 1 [1|]I|12 + h Y 2 + A x
+ +|AX111* a 11 + 1|11)()
= 1 (N]]x]|² + M Y 2
|USVX
+ || 1²²) - (IIVX + ||-
= - (1||2112++)) + 1 | 2 + || 2 + [|SV|p) - - +
(40)
--Eue 1 (o3 + h) (1|**) 1 + ||>> 13) - Σ # (11*01]++1 + IP)
1=1
19

---

Published in Transactions on Machine Learning Research (06/2023)
Comparing the above expression with (3.(3 note that choice of p as,
2pllo + h)) 11+ (1 onin + 2h) (12 + 11) + 20 min
p x min
vj [1,
(41)
implies;
&, S -pE
+ & S Eo exp (-pt)
X (h+ X (h+ Y & exp (-pl)
(h+ $ & exp (-pt)
Σ (h+ o3) (1121 ||>0|| & exp (-pl)
(42)
Σ (h + 03) (1|*1|22 + | S Eo exp (-pt)
&n
X 1 Y 12 S
exp (-p(-t) V
h + of
Yk 0.00
-025
-0.50
0.75
-1.08
-1.00
-3.75
-4.50
0.08
0.25
1.00
Iteration
Figure 6: Left: Contours of the Lyapunov function Ex, Eq. (35) (black), and convergence trajectory of LEAD (red) in the quadratic min-max game (34))31) to the Nash equilibrium (0,0). Right: The evolution of the discrete-time Lyapunov function Eq. (35) over ileration, confirming & Ex 4AAA E.N.
Proof of Theorem
Theorem. The eigenvalues of VFLEAD(W") about the Nash equilibrium wt (x*, of the quadratic
min-mar game ore,
P+ (a, B, 1 (n a) + 9 nph + VA
(43)
2
20

---

Published in Transactions on Machine Learning Research (06/2023)
4(8 - ad) and X E Sploff-digg Furthermore, for where, A (n (1-(1 x 3 -- nh)²
h, 1), |o], |8| << 1, we have,
M - (1 +n+ a)² X₂ n + 32 2m1118
4 +\ 1 (n/ 3) -1
(44)
(1) a) X + 1/11² + -82 24/h13
(a.
4
11 n+a a A
(3 mh) ai 2
Proof. For the quadratic game 33, the Jacobian of the vector field v is given by,
V ( M10 y (2 (t))
hI2n A
A hT2n
2
R.".
(45)
Let us next define a matrix DD as,
V
By f(x
A
0
D2
5 (xx 3)
=
0
- A
E
R2
x RR
(46)
Consequently, the update rule for LEAD can be written
x++1
3t
Et 12
V fx yt)
(tt 31)
yt
y/
+ B
yt Y
17
y.f (xt; y:)
my I (x y Aap
(47)
3t
Ct -t-1
Ay:
+ B
1/0 DDg
y/
yt 41
Azc
where Ay: y: 1t-1 and Aa, Dc 11 Next, by making use of the permutation matrix IP,
1n
P
E R2 x R2n
In
we can re-cxpress Eq. 47 as,
I2n
Wi
Mln
1lnn
Dg
wM
Wi
I2n
W
0
W
17
0
0
W
(48)
T2n
Wi
Man
1ln
W.
1
D₂P
IP
D2
12n
Wi-1
0
W
17
0
W1-1
where w: = (Ii, Be.. Hence, the Jacobian of FLEAD is then given by,
Ten
Ten
T2n
Vu
DD
P
-
PD,P
FLEAD =
Izn 0
+
0
0
0
0
(49)
(1 + () I2n
Vo
DDyP
Blnn
+
all F
I2n
It is to be noted that, for games of the form of Eq. 33, specifically have,
Ve DgI + hllen
and,
off-diag [o] = D.P
21

---

Published in Transactions on Machine Learning Research (06/2023)
Therefore, Eq. 49 becomes,
(1 +1+ - -n/h llan - (n+ + a) 1P -B12n + a
FLEEAD =
(50)
I12n
We next proceed study the eigenvalues of this matrix which will determine the convergence properties of LEAD around the Nash equilibrium. Using Lemma 1 of (Gidel et al., 2019), can then write the characteristic polynomial of VLLEAD as,
det (X1l4n - V VILEAD)= 0
[X - 1) I2n -(3 (1)) I2n + a7+ 312 P
1)
det
=0
-112n
Xl22
det
([(X 1) (X - 12 + Xnphllnn + (X1+ Xa a) D2P)) =0
det
([((X - 1) (X 3) xxa a) UAU 0
(51)
det
([((X - 1) (x- 3) + Xnhh (Xn A]) =0
2n
II [X - 1) (x- + (x
Where, in the above, we have performed an eigenvalue decomposition of DgP = UAU-!. Therefore,
x2 -21 + + - x E Sp(D,,)
1- (17 )1 + + nh
(52)
x
(2) f
with
A = (1- (1 A B- nh)² 433 adi)
(53)
Furthermore for h |a] << 1, we can approximate the above roots to be,
(a, + (n+ a)² X² + h22h2 B2 -2gh/
+ As
n + a
(nh - 3) -))
n)
4
2
(54)
(a, (n+ a)² X2 + 12122 + 32 2
+
+ >
(3 nh) a
2
E
Proof of Proposition 3
Proposition. For any X (ioodddag[V[[ Vu(w"))),
Vap(A) a=D <0 (0,
2 Im()mos))
(55)
where Tm(Amaz) is the imaginary component of the largest eigennalue Xmaz-
We observe from Proposition above that for h, 17, |a], |/3|
<< 1,
pla.n.3) n. B) == max
(i) 11.1p" 22 AA
(56)
(2)
max{
1+
4 744
22

---

Published in Transactions on Machine Learning Research (06/2023)
{"² 1A:11 - -1ph1² _3 111112 + 1/h.3 - (17h -3)² 12:1
Vapla max
(1+ 5) 1b,12) 14
11" |Aol* - 11+ 352
(57)
max
3 4
1 mriil?) } iA
4
{
|2 -1 111--1) n n1ir1 ii
max
4
where we have retained only terms up to cubic-order 7,, 13] and h. Hence, choosing 1) E ensures:
0, Fm((Aax)))
Vapla <
(58)
We thus posit, that choice of positive causes the norm of the limiting eigenvalue p4 of FLEAD to decrease.
F Proof of Theorem 3
Theorem. Setting 1 2()mm(AA+h) then we have V e > 0,
A+1 EO ((-4
(1-- 4(amaz + h)2
(1 8/2)h
3h2
min
Do
(59)
mmaa + h
8(amaz + h)2
where Tmax (mmin) the largest (smallest) eigenvalue of A, A.+1 == ||wc+1 - w0 + ||w - w1
Proof: From Eq. (52), we recall that the cigenvalues of V.LEADD (w0) for the quadratic game are,
(1 (1- (a - 1))d; + B -nhh
4 4 - 172ss) 1 (1 (a n) 3 n/)2
11 (a,
(.) B,
(60)
2
with A E (oapif-ddag(V(((")))) Now, since in the quadratic-gamo sctting considered, we have,
A
[[-diag[VV(("")) = D,P = AT
(11)
hence, \; tia; with or being the singular values of A. This, then allows us to write,
( (a, (1- ( + B-nh)
4 - a(tio,)) (1 (a + +)( + -3-nh)²
1 +
(62)
2
According to Proposition the convergence behavior of LEAD is determined as, A411 S O t) v 0, where (setting =))
1 (1 p := max
(63)
100(0) 1
Now assuming that y) is small enough, such that, 173 z 0 and 3² 0, we have,
= 1 o² + +, nn² - + B) n/
(64)
Furthermore, using learning rate as prescribed by Proposition 3, such as 17 == a (1)+ we find
σ min
(1 + 3/2)h
3/22
FLEAD
4(0maz + h2²
+
Omaz + h 8(0maz + h)2
(65)
23

---

Published in Transactions on Machine Learning Research (06/2023)
Therefore,
A441 S 50(11 (LEAD) A0)
(66)
mmnn
(1+ 8/2)h
3h²
= m(maax + h)2
Ao)
0 man + h
8(0 + h)2
where A441 = ||0+1 w01 + ||,, w/
G Robustness to the Discretization Parameter
In this section study the effect of the discretization parameter 8, defined in equation 32 and Proposition on the quadratic game defined in 29,
min max xT (y4)yy + x
In Figure 7, we provide grid of experiments to study the effect of discretization on the convergence of the quadratic game explored in section 7.1 (Adversarial vs Cooperative games). We observe that for every level of "moa that changes the dynamics of the game from adversarial to cooperative game, LEAD allows for wide range of discretization steps that lead to convergence. Note that the discretization step and consequently the learning rate can be viewed as hyper-parameter and consequently require tuning.
Spectral Radius
== 2
0.95
0.90
0.85
6
0.80
0.75
0.70
0.65
2-13
00
Yours
Ymax
Figure 7: The effect of discretization parameter (8) on the convergence of LEAD the quadratic min-max defined in 29. The x-axis changes the game dynamics from cooperative to adversarial. The y-axes shows the range of 8. The color shows the spectral radius which corresponds to the convergence rate (smaller spectral radius leads to faster convergence). Convergent. dynamics, require spectral radius that is smaller than one. We plot experiments with non-convergent dynamics (spectral radius in white. Darker colors correspond faster convergence. We observe that LEAD allows for wide range 6 that result in convergent dynamics. Thus, LEAD is robust against the discretization parameter.
LEAD-Adam
Since Adam algorithm is commonly used in large-scale experiments, we extend LEAD be used with the Adam algorithm.
24

---

Published in Transactions on Machine Learning Research (06/2023)
Algorithm Least Action Dynamics Adam (LEAD-Adam)
1: Input: learning rate 7, momentum 3, coupling coefficient a.
Initialize: æo f- Winit, Yo < Yinit: f- 0, mg + 0, vo + mg - 0, v/
while not converged do
t 1+1
9x Vaf V1)
6:
Jay Ay - V (f()) 1/- 11-
7:
of + By + 9z
8:
m. t m, + + 31).
9:
oi + 82,15_1
1+ +(1 (2)-
10:
fy m4/(1 (1
11:
6 0t/(1 (2)
12:
2++1 21 17 m//e//// (v0e t))
13:
By V,J(1++1, Ht)
14:
Jxy Az + (gg)
12t)
15:
of + May Ar + By
16:
m. + fm + (1 (1-311).9
31).98
17:
v t B2.0/11
(1
(2)2
fH < my/ (1 BB
19:
6 c v/ (1 B5)
20:
Mt41 + V1 + w +
21: end while
22: return (z,
8-Gaussians Generation
We compare method LEAD-Adam with vanilla-Adam (Kingma & Ba, 2014) the generation task of mixture of 8-Gaussians. Standard optimization algorithms such vanilla-Adam suffer from mode collapse in this simple task, implying the generator cannot produce samples from one or several of the distributions present in the real data. Through Figure 8, we demonstrate that LEAD-Adam fully captures all the modes in the real data in both saturating and non-saturating losses.
Real Data
Adam Non-Saturating Loss
LEAD Saturating Loss
LEAD Non-Soturesing Loss
Figure 8: Performance of L.EAD-Adas on the generation task of 8-Gaussians. All samples are shown after 10k iterations. Samples generated using Adam exhibit mode collapse, while L.AAD-Aam daes suffer from this issue.
25

---

Published in Transactions on Machine Learning Research (06/2023)
J Experiments and Implementation Details
J.1 Mixture of Eight Gaussians
Dataset The real data is generated by 8-Gaussian distributions their mean are uniformly distributed around the unit. circle and their variance is 0.05. The code to generate the data is included in the source code.
Architecture The architecture for Generator and Discriminator, each consists of four layers of affine transformation, followed by ReLU non-linearity. The weight initialization is default PyTorch's initialization scheme. See schematic of the architecture Table 3.
Table 3: Architecture used for the Mixture of Eight Gaussians.
Generator
Discriminator
Input: E I864 ~ A( I)
Imput: E IR2
Linear (64 -> 2000)
Linear (2 - 2000)
ReLU
ReI.U
Linear (2000 - 2000)
Linear (2000 - 2000)
ReLU Linear (2000 2000)
ReLU Linear (2000 2000)
ReLU Linear (2000 + 2)
ReLU Linear (2000 - 1)
Other Details We the Adam (Kingma & Ba, 2014) optimizer top of our algorithm in the reported results. Furthermore, use batchsize of 128.
J.2 CIFAR 10 DCGAN
Dataset The CIFAR10 dataset is available for download at the following link; https://www.c cs. www.otootooo....ooooooo du/-kriz/cifar. html
Architecture The discriminator has four layers of convolution with LeakyReLU and batch normalization. Also, the generator has four layers of deconvolution with ReLU and batch normalization. See schematic of the architecture in Table 4.
Table Architecture used CIFAR-10 DCGAN.
Generator
Discriminator
Input: 1000 ~ NVO, I)
Imput: æ R3x32x02
conv. (ker:: 4, 100 - 1024 stride: 1; pad: 0)
conv. (ker:: 4x 3 -> 256; stride: 2; pad:
Batch Normalization ReLU
LeakyReTU
conv. (ker: 4x.4, 256 > 512; stride: 2: pad: 1)
conv, (ker: 4x4, 1024 -> 512; stride: 2; pad: 1)
Batch Normoalzaaiinn
Batch Normalization
LeakyReLU
ReLU
conv. (ker: 4x4, 1024; stride: 2: pad: 1)
conv. [ker: 4x4, 512 256; stride: 2: pad: 1)
Batch Normalization
Batch Normalization
LeakyReLU
ReLU
conv. (ker: 4x4, 1024 + 1; stride: pad: 0)
conv. (ker: 4x4, 256 + stride: 2: pad: 1)
Tanh
Sigmoid
Other Details For the baseline we use Adam with 81 set to 0.5 and Bg set to 0.99. Generator's learning rate is 0.0002 and discriminator's learning rate 0.0001. The same learning rate and momentum were used to train LEAD model. We also add the mixed derivative term with ay = 0.3 and ag = 0.0.
The baseline is DCGAN with the standard non-satugg loss (non-zero sum formulation). In our experiments, compute the FID based 50,000 samples generated from our model 50,000 real samples.
26

---

Published in Transactions on Machine Learning Research (06/2023)
Samples
Figure 9: Performance of LEAD on CIFAR-10 image generation task on DCGAN architecture. Left: LEAD achieves FID 19.27. Right: Vanilla Adam achieves FID 24.38. LEAD is able to generate better sample qualities from several classes such as ships, horses and birds (red). Best performance is reported after 100 epochs.
J.3 CIFAR 10 ResNet
Dataset The CIFAR10 dataset is available for download at the following link; httpps//wwrt cs. toronto. du/-kriz/cifar. html
Architecture See Table 6 for schematic of the architecture used for the CIFAR10 experiments with ResNet.
Table 5: ResNet blocks used for the ResNet architectures (see Table 6).
Dis Dis-Block
Gen Block
Shortcut:
downsample
Shortcud:
convv (ker: 1x1, 1/18/128 - 128; stride: 1)
Upsample(x2) x2)
Spectral Normalization
Residual:
[AvgPool (ker:2x2, stride:))), if +f
Batch Normalization ReLU
Residual:
ReLU J. if e
Upsample(x2) x2)
conv. (ker: 3x3, 3 3 + 128; stride: 1; pad: 1)
conv. (ker: 3x3, 256 + 256; stride: 1; pad: 1)
Spectral Normalization ReLU
Batch Normalization
ReLU
conv. (ker: 3x3, 128 -> 128; stride: 1; pad: 1)
conv. (ker: 3x3, 256 + 256; stride: 1; pad: 1)
Spectral Normalization AvgPool (ker:2x2) )
Other Details The baseline is ResNet with non-saturating loss (non-zero sum formulation). Similar to (Miyato et al., 2018), for every time that the generator is updated, the discriminator is updated 5 times. For both the Baseline SNGAN and LEAD-Adam we use a 31 of 0.0 and 82 of 0.9 for Adam. Baseline SNGAN uses a learning rate of 0.0002 for both the generator and the discriminator. LEAD-Adam also uses a learning rate of 0.0002 for the generator but 0.0001 for the discriminator. LEAD-Adam uses an a of 0.5 and 0.01 for the generator and the discriminator respectively. Furthermore, we evaluate both the baseline and our method exponential moving average of the generator's parameters.
27

---

Published in Transactions on Machine Learning Research (06/2023)
Tahle 6: ResNet architertures used for experiments on CIFAR10.
Generator
Discriminator
Inpul: E R6 ~ NO I)
Impul: E R3x33x32
Linear(64 + 4096)
D ResBlock
G ResBlock
D ResBlook
G Rlock
D- D-ResBlock
G Reockkllock
D-ResBlock
Batch Normalization
ReLU
ReLU
AvgPool (ker:8x8
conv. (ker: 3x3, 256 3; stride: 1; pad:1)
Linear(128 + 1)
Tanh(-)
Spectral Normalization
In our experiments, we compute the FID based on 50,000 samples generated from our model vs 50,000 real samples and reported the mean and variance over 5 random runs. We have provided pre-trained models well the source code for both LEAD-Adam and Bascline SNGAN in our GitHub repository.
Samples
Figure 10: Generated sample of LEAD-Adam CIFAR-10 after 50k iterations ResNet architecture. We achieve an FID score of 10.49 using kearning rate the generator and the discriminator, for generator set 0.01 and the discriminator is set to 0.5.
K
Comparison to other methods
In this section compare our method with several other second order methods in the min-max setting.
The distinction of LEAD from SGA and LookAhead, can be understood by considering the 1st-order approximation of .++1 = FA V.f (Ix, yk + 7/yk)) where Ayk = vvy (æx + nı,, yk).
For FtR, provide the update for the second player given the first player performs gradient descent. Also that in this table SGA simplified the two player zero-sum game. Non-zero formulation of SGA such the used for GANs require the computation of Iv.J"e
28

---

Published in Transactions on Machine Learning Research (06/2023)
Table 7: Comparison of several second-order methods in min-max optimization. Each update rule, corresponding particular row; can constructed by adding cells in that row from Columns to 7 and then multiplying that by the value Column 1. Parthermore, Ark41 = #k41 Sky while C = vf (Vae))) We compare the update rules of the first player for the following methads: Gradient Descent-Ascent (GDA), Least Action Dynamics (LEAD, ouss), Symplectic Gradient Adjustment. (SGA), Competitive Gradient Descent (CGD), Consensus Optimization (CO), Follow-the-Ride (FtR) and Learning with Opponent Learning Awareness (LOLA), zero-sum game.
Coefficient
Momentum
Gradient
Interaction-xy
Interaction-xx
GDA
Are+1
VS
0
LEAD
Axk+1
B BAx
V
-a TAyk
0
SGA
Ari11
1
0
V my Vu
0
(GD(
AT141
C-1
- Vy VV
0
CO
Att+1
1
0
-, V Ve Tvyf
V
/v.f
FTR(57)
Atk-1
Ny Vy
te (ndd) V...V..
(OLA
1
0
-nVaf
-2na VVy. [V
0
This gives rise to:
Tk+1 = of (Ik, yk) - V2 zf (Ik, yk) Ay. Mk+1 yk + V,, (Ik, yk) + v (Itk: yk. Ar.
(67)
(68)
with Ar. Ay corresponding to each player accounting for its opponent's potential next step. However, SGA and Ahead additonally model their opponent as naive learners i.e. Ar = - (= yk), Ay = V Me). On the contrary, our method does away with such specific assumptions, instead modeling the opponent based on its most recent move.
Furthermore, there is a resemblance between LEAD and OGDA that we would like address. The 1st order Taylor expansion of the difference in gradients term of OGDA yields the update (for x):
Tk- V 1 2 /V
VVF.
(69)
which contains an extra 2nd order term 2 compared to ours. As noted in Schäfer & Anandkumar (2019),
the V2.f term does not systematically aid in curbing the min-max rotations, rather causing convergence to
non-Nash points in some settings. For c.g., let us consider the simple game f(z, y) 7(x² - y²), where x, y, 7 are all scalars, with the Nash equilibrium of this game located at (x" = 0.y" 0). For a choice of 2 6, OGDA fails to converge for any learning rate while methods like LEAD, Gradient Descent Ascent (GDA) and CGD (Schäfer Anandkumar (2019)) that do not contain the aæz (V vu term do exhibit convergence. See Figure 11 and Schäfer & Anandkumar (2019) for more discussion.
100
10a
LEAD/GDA/CGD
Log Distance to eq
Log Distance to eq
10-4
OGDA
10a
10
10-4
10-12
10-9
10-16
10-14
LEAD/GDA/CGD
10
10-18
OGDA
10
20
30
40
10
20
30
40
Iterations
Iterations
Figure 11: Figure depicting convergence/dlivergenne several algorithms the game of f(x.y) 7xx - ? (Nash equilibrium 0,y² 0). Left: For 1, OGDA and L.EAD//DA/ /GG///D//D (overlaying) found to converge the Nash eq. Right: For 6, find that OGDA fails converge while LEEA//GA//COT (overlaying) converge. We conjecture that the reason behind this observation is the existence V2 / term optimization algorithm of OGDA.
29


Reviews:
[{"review_id": "gavTbqv0fj", "reviewer": "Reviewer_nSLp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The paper is well written. It starts with a discussion of the optimization mechanics, providing good intuition for how the optimization method was developed by introducing two different kinds of \"forces\" and showing their effect on the final update equations of the algorithm. Making an analogy to Newton's second law and using (for the most part) familiar physical terminology was helpful. I didn't fully understand why magnetic force does what the authors describe, and it might be good to add an illustrative physical (or abstract) example in the paper. \n\n2. The rotational dynamics hindering the convergence of gradient descent ascent is a well-talked-about phenomenon, and several algorithms have been proposed to avoid it. I found the discussion of the existing algorithms a bit lacking. In particular, while many works were cited, the precise convergence rates were not discussed. This makes it difficult to put the theoretical results in this paper in perspective. \n\n3. The authors don't discuss if their results can be extended to the general quadratic setting and, more broadly, to convex-concave games. I think this is a major limitation of the paper and requires discussion.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new optimization algorithm called LEAD for min-max optimization. The algorithm is developed by observing gradient descent dynamics, drawing analogies with a physical system, and modifying it using momentum and a coupling term. The convergence of LEAD is analyzed on a quadratic min-max optimization problem. It converges exponentially and is asymptotically quicker than an extra-gradient method in some regimes. The paper also provides a detailed empirical study of the computational cost of implementing LEAD v/s other methods, showing LEAD can be implemented with two gradient computations at each step. Finally, the paper compares the optimization of LEAD v/s previous methods on a family of synthetic and well-known non-convex tasks, showing either improved or comparable performance. \n\n**Overall, I like the writing and the flow of the paper and recommend accepting it.** ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Add an intuitive example discussing the effect of the magnetic forces. This is not a big issue but might help provide further physical intuition. \n\n2. Add theoretical comparison to other methods. A table earlier in the paper discussing the convergence rates for all the methods would be most desirable. This should be discussed for all the algorithms used in Figure three. This is an important addition. \n\n3. Discuss any difficulties in extending the results to the general convex-concave games. \n\n ", "broader_impact_concerns": "None. I appreciate the authors adding a broader impact section. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "zsSlxEwJIW", "reviewer": "Reviewer_5Tbx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is paper is very well written and organized. The novelty of the proposed method lies on the connection between optimization method with momentum and physical laws. I am not aware of such explicit proposal in the literature. \n\n$\\mathbf{1}.$ The technical analysis is thorough where authors considered both discrete and continuous cases, and the convergence analysis is sound and solid. \n\n$\\mathbf{2}.$ The novel proposal of connecting momentum with physics in solving min-max game can be considered as a solid contribution, as well as the intuitive design of the algorithm.\n\n$\\mathbf{3}.$ The related work is very well stated with detailed background information and lines of research. The motivation and physical connection are very well stated with intuitive illustrations, mainly on Section $3$. Authors also conduct a good comparison with existing algorithms especially on the computational cost. \n\n$\\mathbf{4}.$ The experiment is very comprehensive as I see, as well as being supported by comprehensive details, such as the experiment setup. The appendix has extensive details that helps get further understanding of the empirical experiments. I see the proposed toy experiment on the min-max problem in Eq. (31) is very helpful in understanding the practical convergence between LEAD and other existing algorithms. Followed by the toy problem, the experiments on GAN is also presented and designed well to support the claim of the paper. \n\n$\\mathbf{5}.$ Author provided extensive details in appendix as well as a blog post of a nice illustration in the supplementary material. I found it very helpful to understand the problem to be solved and the proposed algorithm. \n\n--------------------\n\nRegarding the weakness, I defer it to the next section where I'd like to ask questions and propose a few changes. $\\textbf{To highlight my major concern}$, I see the proposed algorithm performs well on top of Adam on a few GAN, but I'd like to understand more of its general applicability during discussion, as it could be potentially the limitation of the proposed method. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a novel optimization method to solve min-max game optimization problems, and the proposed method leverages physical properties, e.g., mechanism of forces, to design the proposed optimization methods.    ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "There are some trivial and non-trivial issues I found in the paper.\n\n$\\mathbf{1}.$ It seems as Figure 1 is not referred in the text, and I found its graphic/notation is a bit confusing. It'd be nice to add its context in the text and make its explanation clearer.\n\n$\\mathbf{2}.$ In the experiment, authors mention \"State-of-the-art methods use architectures that are 30 times or more larger than the architecture that we have chosen to test our method on”. Is it necessary to evaluate the proposed methods on more up-to-date models/instances? If so, it'd be a good practice to add additional experiments into the paper. If not, please explain. \n\n$\\mathbf{3}.$ I understand there exists a section discussing the computational cost of proposed algorithm again other existing methods. However, in the experiment, e.g., when comparing Adam vs. LEAD, it would be good to add either cost of computation (e.g., # of gradient) or wall clock time. \n\nTrivial one:\n\n$\\mathbf{4}.$ in Section 7.2 on page 10, “See H for a comparison” missed “Appendix”.  ", "broader_impact_concerns": "Author stated a possible concern of broader impact in the end of the main paper. I do not have any concerns on the ethical implications of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QhgwMyUZLb", "reviewer": "Reviewer_8GPk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(1)\tThe motivation rooted in physics is robust and easily comprehensible.\n\n(2)\tThe proof is overall clear and persuasive.\n\n(3)\tComputationally efficient – it does not require the entire Jacobian matrix, but only a quarter block of it. This \"partial\" Jacobian can be computed using auto-grad tools.\n\nWeaknesses:\n\nThe scope of applicability is unclear. This work focuses on two-player quadratic games, specifically requiring an objective function in the form of Eq. 13 in the main text. It is not evident whether the method works for generalized quadratic objective functions, such as objective functions in the form of $X^{T}AX + Y^{T}BY + X^{T}CY$, where A, B, and C are not guaranteed to be positive-definite (in which case the Nash equilibrium may not be zero).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Inspired by the intuition behind Polyak's momentum methods, which interpret the process of gradient-based optimization as an object (ball) rolling downhill to reach a minimum, the author introduces a similar physics formalism for two-player zero-sum games. They apply \"forces\" to the object in Polyak's physical intuition, which helps curb rotations and limit speed. Based on this intuition, the author proposes the Least Action Dynamics (LEAD) optimization scheme, which describes these \"forces.\"\n\nThe work then extends Lyapunov analysis from momentum methods to LEAD, proving its linear convergence in both continuous and discrete-time settings for quadratic min-max games. Experimentally, the author demonstrates that LEAD is computationally efficient and improves the performance of GANs against multiple baselines across various tasks. The main contributions are as follows:\n\n(1)\tLEAD is well-motivated by the physical intuition behind the common momentum method.\n\n(2)\tLyapunov stability analysis guarantees linear convergence speed in both discrete and continuous-time settings for min-max games.\n\n(3)\tExperiments effectively support the performance claims made by the author.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It is difficult to determine how the discretization parameter affects performance. It would be beneficial if you could display your parameters in the experimental section or provide empirical justification.\n\nAs stated immediately before Equation 19, the fixed point $\\omega^*$ satisfies $F_{\\eta}(\\omega^*) = \\omega^*$. Does this lead to Equation 19 when $\\nabla v(\\omega^*)$ (the second term on the RHS of Eq 19) is equal to zero?\n\nThe spectrum of $\\nabla F_{\\eta}(\\omega^*)$ is defined in Eq. 20, but the definition of “Sp(off-diag(.))” remains unclear.\n\nThe attached blog images in the supplementary, which depict the dynamics in the x-y plane, effectively illustrate the outward rotatory motion and increasing velocity. It would be advantageous to include these images in the main text if possible.\n", "broader_impact_concerns": "There is no concern to be addressed as far as I know.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a physics-inspired formalism for two-player zero-sum games and an optimization scheme, called LEAD. The work applies Lyapunov analysis to LEAD, proving its linear convergence in both continuous and discrete-time settings for quadratic min-max games. The connection to physics is well grounded and the theoretical contributions are solid. Besides that, the authors demonstrate experimentally that LEAD is computationally efficient and improves the performance of GANs. The paper contains a lot of details that show evidence of the empirical performance.

The reviewers found the contributions of this work are solid. Moreover, the paper is very well written. All reviewers unanimously voted for acceptance.

Therefore, the paper is ready for acceptance almost in its current form. Please make sure to remove the red font from the text. I also found a relevant reference that I think should be included in the final version of the paper: https://arxiv.org/abs/2105.13922
Decision: Accept (poster)