Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
Authors: Yi Feng
Kaito Fujii
Stratis Skoulakis
Xiao Wang
Volkan Cevher
Venue: ICML 2025 poster (2025)
Keywords: Min-Max Games
Heavy Ball Momentum
Continuous-Time Analysis
Primary area: theory->game_theory
TL;DR: We study the dynamical behaviors of heavy ball momentum in min-max games.

Abstract: Since Polyak's pioneering work, heavy ball (HB) momentum has been widely studied in minimization. However, its role in min-max games remains largely unexplored. As a key component of practical min-max algorithms like Adam, this gap limits their effectiveness. In this paper, we present a continuous-time analysis for HB with simultaneous and alternating update schemes in min-max games. Locally, we prove *smaller* momentum enhances algorithmic stability by enabling local convergence across a wider range of step sizes, with alternating updates generally converging faster. Globally, we study the implicit regularization of HB, and find *smaller* momentum guides algorithms trajectories towards shallower slope regions of the loss landscapes, with alternating updates amplifying this effect. Surprisingly, all these phenomena differ from those observed in minimization, where *larger* momentum yields similar effects. Our results reveal fundamental differences between HB in min-max games and minimization, and numerical experiments further validate our theoretical results.

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
Yi Feng' Kaito Fujii Stratis Skoulakis
Xiao Wang" 14 Volkan Cevher
Abstract
valuable insights it provides into the behavior of discrete- time algorithms, the approach of using continuous-timg equations to analyze momentum- based methods in mini- mization has seen significant advancements in recent years (Su et al., 2016; Kovachki & Stuart, 2021; Shi et al., 2022).
Since Polyak's pioneering work, heavy ball (HB) momentum has been widely studied in minimiza- tion. However, its role in min-max games remains largely unexplored. As a key component of prac- tical min-max algorithms like Adam, this gap lim- its their effectiveness. In this paper, we present continuous-timg analysis for HB with simul- tancous and alternating update schemes in min- max games. Locally, we prove smaller momen- tum enhances algorithmic stability by enabling local convergence across a wider range of step sizes, with alternating updates generally converg- ing faster. Globally, we study the implicit reg- ularization of HB, and find smaller momentum guides algorithms trajectories towards shallower slope regions of the loss landscapes, with alternat- ing updates amplifying this effect. Surprisingly, all these phenomena differ from those observed in minimization, where larger momentum yields similar effects. Our results reveal fundamental differences between HB in min-max games and minimization, and numerical experiments further validate our theoretical results.
Min-max games model optimization scenarios where two players interact such that one's gain is the other's loss, with the objective of finding local Nash equilibrium. They are widely applied in tasks like GANs (Goodfellow et al., 2014) and ad training (Madry, 2017). Due to their extreme importance, many specialized algorithms like Extra- Extra-gradient (Korpelevich, 1976) and optimistic methods (Daskalakis et al., 2017) have been proposed to solve this type of prob- lems. However, heavy ball momentum, as a crucial com- ponent of practical min-max algorithms such as Adam, is extensively employed in solving min-max games (Wang et al., 2019; Do et al., 2022). Our understanding of heavy ball momentum in min-max games remains relatively lim- ited compared to minimization.
For example, Gidel et al. (2019) observed that in min-max games, negative momentum can enhance training outcomes, which is surprising given that positive momentum is typ- ically employed in minimization. Morcover, in min-max games, players can update their strategies simultaneously, as in repeated Dock-Paper-Seissene training, where the discriminator is updated firstly, and then the generator updates based on the feedback received from the discriminator. turns out that this subtle difference on the update rules can greatly affect the results of learning process, and Gidel et al. (2019) proved in the special cases of bilinear games, only combining negative momentum with the alternating updates can lead to convergence. These dis- coveries motivate the following questions:
or alternately, as in GANs
1. Introduction
The Heavy Ball momentum (a.k.a. Polyak's momentum) (Polyak, 1964) has played important role in modern op- timization for machine learning (Sutskever et al., 2013). In the context of minimization, the mechanism of heavy ball momentum is typically explained by modeling it as a continuous-time differential equation that describes the physical process of mass moving through a frictional medium (Qian, 1999). Due to its intuitive appeal and the
What is the impact of momentum and update rules on the learning dynamics in min-max games?
The first four authors are listed in alphabetical order. 'Shanghai University of Finance and Economics, Shanghai, China Nationnl Institute of Informatics, Tokyo, Japan' AArrhus University. Aarhus, Denmark 'Key Laboratory of Interdisciplinary Research of Com- putation and Economics, China 'EPFL, Lausanne, Switzerland. Correspondence to: Xiao Wang <wangxiao sufe.edu.en'>
In this paper, investigate min-max learning dynamics through the lens of continuous-time analysis, focusing on both local and global aspects. Locally, we quantitatively analyze how momentum and update rules influence the con- vergence rates of continuous-tin models near local Nash equilibrium-a crucial first step understanding algorith- mie behavior (Ochs, 2018). Globally, given the limited understanding of heavy ball momentum's 's properties even
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
in minimization (Lessard et al., 2016; Wang et al., 2022), we take qualitative approach to explore global dynam- ics. In minimization, such global dynamics can be inter- preted through implicit gradient regularization (Barrett & Dherin, 2021), which describes how optimization trajecto- ries interact with loss landscape geometry. We extend this perspective to heavy ball momentum in min-max games.
(SCSC) min-max games, highlighting its suboptimality, the result later extended to global convergence under the same condition by (Zhang et al., 2021). (Azizian et al., 2020) demonstrated that HB accelerates local convergence when the underlying games closely resemble to minimization problems. (Fang et al., 2025) investigated the no-regret properties of heavy ball momentum. (Lotidis et al., 2024) examined Nesterov's 's mo- mentum in general games with strict equilibrium. Our work differs from the studies above. We do not assume SCSC con- ditions and instead focus on more representative min-max games, where strong player interactions fundamentally dis- tinguish them from minimization. Furthermore, our goal is not to prove that HB achieves a better convergence rate than other algorithms like Extra-gradient, which has been shown to be impossible by (Azizian et al., 2020). Instead, we aim to explore how the parameters of momentum algorithms influence the dynamics of min-max games.
1.1. Summary of Contributions
In this paper, we investigate local convergence and implicit gradient regularization of heavy ball momentum in min-max games through their continuous-time models. Our main contributions be summarized as:
Local Convergence: Our results highlight two insights. Firstly, there exists a trade-off between positive and neg- ative momentum: positive momentum achieves an opti- mal local convergence rate under small step sizes (The- orem 4.8), whereas negative momentum enables conver- gence across a broader range of step sizes (Corollary 4.7). This contrasts with minimization, where large positive mo- mentum can facilitate local convergence over broader range of step sizes (O' OO'onoghuue & Candes, 2015). Sec- ondly, we establish conditions under which alternating updates outperform simultaneous ones (Theorem 4.9). These conditions capture important min-mat game scenar- ios where players' optimization dynamics have strong in- teraction, including bilinear games in (Gidel et al., 2019).
Alternating Updates in Game Dynamics. Recent studies have demonstrated the benefits of alternating updates in var- ious theoretc settings. (Bailey al., 2020; Wibisono et al., 2022; Hait et al., 2025) showed that alternating up- dates lead to a slower regret growth rate from an online learning perspective. (Feng et al., 2024) studied the complex dynamical behaviors of alternating updates from the predic- tion accuracy perspective. (Rosca et al., 2021) investigated different discretization drifts arising from simultaneous and altermating GDA, i..., algorithm without momentum. (Yang et al., 2022) showed that alternating GDA achieves a faster convergence rate under PL condition. (Zhang et al., 2022; Lee er al., 2024) proved that alternating GDA converges more rapidly than simultancous GDA in SCSC settings. To the best of our knowledge, the convergence separation result between simultaneous and alternating HB in bilinear games (Gidel et al., 2019) is the only known theoretical result on alternating HB.
Implicit Gradient Regularization: Our analysis of continuous-time models reveals that smaller momentum and alternating updates steer algorithm trajectories toward regions with shallower slopes in the min-max loss land- scape, characterized by smaller gradient norms. Interest- ingly, this contrasts with minimization problems, where larger momentum facilitates convergence to shallow slope regions (Ghosh et al., 2023). To validate these findings, we conduct numerical experiments exploring various dy- namical behaviors, including convergence to equilibrium, limit cycles, and GAN training dynamics. Furthermore, since sharp gradient regions are major source of insta- bility in min-max training (Thanh-TTun) et al., 2019; Wu et al., 2021), our results provide an explanation for the observed benefits of negative momentum in improving stability, as noted in (Gidel et al., 2019).
Differential Equations for Optimization. Differential equations are powerful tools for studying optimization algo- rithms. In the following, and future related works can be found in the references therein. For minimization, (Su et al., 2016; Wibisono et al., 2016) purposed ODEs to investigate momentum in convex minimization. The use of SDEs for the stochastic setting was developed by (Li et al., 2017) and future developed by (Compagnoni et al., 2024a) recently. For (Lu, 2022) introduced methods for deriving high resolution ODEs to study algorithms' convergence behaviors. (Hsieh et al., 2021) purposed mean dynamics for Robbins-Monro algorithms to study algorithms'' long-time behaviors. For the stochastic setting, recent work of (Compagnoni et al., 2024b) derived SDEs to model the behaviors of several min- max algorithms under the weak approximation framework.
present very brief summary,
1.2. Related Works
games,
Momentum in Games Dynamics. The role of momen- tum in min-max games has received considerable attention. (Gidel et al., 2019) empirically observed that negative mo- mentum enhances min-max training and established its theo- retical benefits in bilinear games. (Zhang& & Wang, 2021) in- vestigated the local convergence rate of simultaneous HB in
2

---

Continuous-Tineg Analysis of Heavy Ball Momentum in Min-Max Games
1.3. Organization
or M E Caxd, we use Sp(M) represent the set of its eigenvalues in C. Given À E Sp(M), use R(A) and ( to denote the real and imaginary parts of X, respec- tively. The notation M * 0 or . ' 0 indicates that M is a negative or positive semi-definite matrix, respec- tively. We use EigVec(MM) to denote the eigenspace of M, and Ker(M) to represent the kernel space of M, i.e., Ker(M) {2 E Cd M==00.
In Section 2, we outline the background for this paper. Sec- tion 3 introduces tum algorithms. In Section 4, we present the local analysis results, followed by discussions on implicit gradient regular- ization in Section 5. Numerical experiments are integrated into the main text, while additional experiments and proofs are provided in the appendix due to space constraints.
continuous- caatinuuus-time models for momen-
3. Continuous- Time Models
2. Preliminaries
Continuous-time models have proven to be effective in ana- lyzing momentum based algorithms in minimization prob- lems. We extend this approach to heavy ball momentum algorithms in min-max games. We firstly define the modi- fied loss function F(x, y) as follows:
Min-Max Games. A min-max game with smooth payoff function f(z,y) can be formulated as
min max f(z,8) 3)
(Min-Max Games)
EER" yER"
If a pair of strategies (x" (y) satisfies Va E, f(x,y") 2 [a" :y") and Vy E V, fx= ,1" 2 f(x",) y) for some x*'s neighborhood U R" and v neighborhood V R", then (x", y²) is called local Nash equilibrium, which is standard solution concept in min-max games (Ratliff et al., 2016).
F(z.9)
1 - 3 f(z. v)
h(1 + 3)
4(1 Bys (IVef(t.:\I
For Sim-HB, the continuous-time models are given by:
Heavy Ball Momentum. In this paper, we both consider the simultaneous heavy ball momentum method:
= v(F==,,[(,,,, i(() F(r,
(Continuous Sim-HB)
1 = Fn - 11 N. Un) + Man xn- yn+1 = yn. + hV yf yn) B(yn- - 3n-1) (Sim-HB)
For Alt-HB, the continuous-time models are:
i(t) = v, (F(I.))
2(1 - 3)2 V (25(2, (2))
h
and the alternating heavy ball momentum method:
+(1) = V..
(Continuous Alt-HB)
Fn+1 In AV vn) B(5m xn-1)
Un+1 yn + Av f (In+1, + Blyn Dn-1)
It may seem surprising that our equations are first-order rather than the commonly used second-order equations for modeling momentum in minimization (Su et al., 2016). However, we chose not to adopt their approach for two reasons. First, their method couples the step sizes and mo- mentum parameter, which hinders the independent analysis of the impact of each term. Second, their approach requires / to be positive to align with physical intuition, whereas our goal is to also explore algorithms with negative momentum.
(Alt-HB)
Here 3 E (-1,1) is the momentum parameter and h > 0 is the step size. We refer to 3 < 0 as negative momentum. We use the word "smaller momentum" to mean that the value of 33 is smaller, not its absolute value.
Local Behaviors of Dynamical System. For a system of differential equations a(t)= = g(xx) where g : R" + R=
is differentiable function, let ã E R" satisfy g(ž) 0.
The derivation of our equations is inspired by (Ghosh et al., 2023), which employed continuous-time models to study the implicit regularization of the heavy ball method in mini- mization. However, our equations differ significantly due to the presence of two interacting players and the distinct update sequences inherent to min-man max games.
Then the local behavior of the system near J. is determined
by the eigenvalues of Jacobian [z(
[ag
(7)
In
dzz
i.j
particular, we have the following standard result:
Proposition 2.1 (Muchlebach & Jordan (2021)). If a maxxesp(J.)) R(A) < O, then there exist constants 5 >> 0 and C > 0 such that for all initial conditions satisfying [|x(0)- - I < 8, we have [[x(t) - ق|| V C
We provide analysis of the approximation error between continuous-time equations and original algorithms in the following Theorem. The proof is deferred to Appendix B. Theorem 3.1. Let f(x, y) be a smooth function with bounded derivatives up to the fourth order. Then for
t Vt > O.
Notation. We denote the set of real numbers by IR and the set of complex numbers by C. For any matrix M E Rdxd
3

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
continuous-time models in predicting discrete-time dynam- ics provided in Appendix I.
midd djpeee
4.1. Jacobian of Continuous-time Models
This section examines the Jacobian of the continuous-time models. As demonstrated in Proposition 2.1, the Jacobian matrices play crucial role in analyzing the local behavior of these equations. We start by presenting the Jacobian for the Gradient Descent-Ascent flow, given by:
+ -V)((,))) y Vyf(x, (Gradient Flow)
Lemma 4.1. The Jacobian of Gradient Flow at a local equilibrium point (x", -y" is given by:
Figure 1. Comparison of O(h2) and -oocal emorr models with payoff function f(z, v) zy.
= fifl""00 -Vzyf(e* y²))
(Jacobian)
any given finite time horizon, the solution trajectories (a(t), of Continuous Sim-HB (resp. Continuous Alt- HB) is locally ((h))-clos to the trajectories of Sim-HB (resp. Alt-HIB) after 4 log h/ log|3| steps.
Vyef(x", Vgf(""
By the definition of local Nash equilibrium, we also have
22f(x" v²) > 0, Vzf(2" .0"""") < 0.
To highlight the advantages of our Ohh²) local error models, we compare them with existing continuous-time approxima- tions of the gradient descent-ascent (GDA) method (B case). The 0(22) model proposed by (Bailey et al., 2020) introduces larger local errors, failing to accurately capture GDA dynamics. For example, while simultaneous GDA is known to diverge in bilinear games, their model incorrectly predicts cyclic behavior. In contrast, as illustrated in Fig- ure the (h models address these shortcomings. Future experiments ar presented in Appendix A.
We now present the Jacobian of Continuous Sim-HB and Continuous Alt-HB at equilibrium. The detailed calcula- tions are deferred to Appendix D.
Proposition 4.2 (Jacobian for simultaneous updates). Let Is denote the Jacobian of Continuous Sim-HB at the lo- cal equilibrium (x", " Then, Is can be expressed as a quadratic polynomial terms of (Jacobian):
1 -1- 2(1 3)3
+(1+8)
3) J
Js
Our continuous-time models also have strong consistency with prior works. First, (Rosca et al., 2021) purposed continuous-time equations to model the dynamics of GDA algorithm. Notably, when 3 = 0, our equations reduce to their formulation. Second, (Gidel et al., 2019) proved that in bilinear games, Alt-HB with negative converges to equilibrium at an exponential rate, whereas Sim- HB di- verges regardless the choice of and B. In Proposition 3.2, we show that our continuous-time equations yield the same conclusion. The proof is provided in Appendix C.
where I denotes the identity matrix.
Proposition 4.3 (Jacobian for alternating updates). Let J denote the Jacobian of Continuous Alt-HB at the local equi- librium (x" ). Then, JA can be expressed as
0
h
JA = 31-3)2
yz. V
xy
(a","")
Proposition 3.2 (Consistency with Gidel et al. (2019)). In matrix games [xx v) = x² Ay, Continuous Sim-HB di- verges at an exponential rate, regardless of the values of h and B. In contrast, Continuous AlI-HB converges exponen- tially when negative and is sufficiently small.
In Sections 4.2 and 4.3, we use these Jacobian matrices to study the local convergence behavior of the continuous- time models. To facilitate this analysis, we first revisit the decomposition (Jacobian) introduced in (Letcher et al., 2019):
I=
(Decomposition)
4. Analysis of Local Dynamies
where
In this section, we analyze the local behavior of the continuous-tin equations introduced in Section near equilibrium. Additional numerical experiments validating our theoretical findings and demonstrating the accuracy of
Vaf(o",0"
S
(Potential)
T
V3f("")"")

---

Continuous- Analysis of Heavy Ball Momentum in Min-Max Games
called the potential part of the game dynamics, and
Negative momentum and positive momentum benefit game dynamics in distinct ways. Negative momentum en- hances algorithm stability by enabling convergence even with large step sizes (Corollary 4.7). Conversely, if a suffi- ciently small step size h is employed, positive momentum can achieve an optimal convergence rate (Theorem 4.8).
0
V zy (x ,y")
A
(Hamiltonian)
V f (x*)
is called the Hamiltonian part. Recall that the local structure of game near an equilibrium is essentially captured by the quadratic form:
We first recall the following assumption from (Wang & Chizat, 2024), which is used to guarantee the local conver- gence of (Gradient Flow) in their work:
= r 2
y
j 2
Assumption 4.5. In (Decomposition), we assume
myJ fx" y )
EigVec (A) n Ker (S) =
y" From (1), (Potential) represents the non-interactive aspects of player behavior, while (Hamiltonian) captures player interactions. In the context of min-max games, the most interesting scenarios arise when there is strong interaction between the two play- ers, i.e., A > S, which is the focus of this paper. This contrasts with cases where players independently optimize their objective functions, such as in games with payoff func- tion (zz 3) = (z) + fe(y), where A We formulate this in the following assumption:
where =
Assumption 4.5 holds generically in the following sense: for any fixed S * if A sampled independently from an absolutely continuous distribution, then Assumption 4.5 holds with probability one. Compared to the strongly- sonvex-strongly-coneay setring, which requires all eigen- values of block matrices of S to be strictly negative, As- sumption 4.5 permits many eigenvalues of these matrices to be zero. This significantly broadens the applicability beyond the strongly- sellly-oovvx---steteee
framework.
Assumption 4.4. In the following, we assume A >>> S in (Decomposition). Since A is an antisymmetric matrix and has purely imaginary eigenvalues, A >> S implies [((A]>> RXA).. AA E Sp(T).
Theorem 4.6. Let J be the (Jacobian) defined in Lemma 4.1. If the momentum parameter 3 E (-1, and the step size h >> 0 satisfy the inequality
min 3)-
RYAA
(2)
XESP(T) J) (1+ (3(A)2 -OPP-MOA R(A)²)
4.2. Analysis of Simultaneous Updates
In this section, we study the local behavior of Continuous Sim-HB. Unlike minimization, where local convergence of algorithms is usually guaranteed, the scenario for min-mac games is more complex. As shown in Proposition 3.2, heavy ball momentum may fail in bilinear games. This observation leads to our first question:
and if f(x,y) satisfies Assumption 4.4 and 4.5 at the lo- cal equilibrium (x",""), then Continuous Sim-IIB achieves local convergence.
Since Assumption 4.4 captures the critical scenarios where player interactions dominate game dynamics, and Assump- tion 4.5 holds generically, Theorem 4.6 implies that Con- tinuous Sim-HB achieves local convergence under fairly mild conditions. Furthermore, the bilinear games studied in Proposition 3.2 do not satisfy Assumption 4.5 S is al always zero matrix in that case.
Does the failure of Continuous Sim-HB in bilinear games indicate general limitation of this method, or is it simply because bilinear games are not representative?
Furthermore, Gidel et al. (2019) observe that negative mo- mentum can significantly enhance training performance in practice. This is in sharp contrast to minimization, where positive momentum is used accelerate convergence. This observation motivates second question:
The proof of Theorem 4.6 is based on the analysis of the Jacobian of Continuous Sim-HB. By Proposition 4.2, this Jacobian can be expressed as a quadratic polynomial in terms of J, establishing a connection between Sp (Js) and Sp (J), which simplifies the analysis. The detailed proof is deferred to the Appendix E.
What are the respective benefits of using Continuous Sim-HB with negative versus positive momentum for local dynamics?
Corollary 4.7. Since the function (31-3)2/C2 + 3) in Theorem 4.6 is a decreasing function of E (-1,1), smaller value of B E (-1,1) enables local convergence of Continuous Sim-HB across a broader range of step sizes.
Our answers to above questions can be summarized as:
The failure of Continuous Sim-HB HB in bilinear games is not representative. In Theorem 4.6, we prove that simul- taneous heavy ball momentum generically achieves local convergence under appropriate parameter choices.
Corollary 4.7 highlights an interesting contrast between the role of momentum in min-max games and in minimization.
5

---

Continuous- Time Analysis of Heavy Ball Momentum in Min-Max Games
ask the following questions:
Given the same step size h and momentum 3, which types of games enable Continuous Alt-HB to achieve better con- vergence rate compared to Continuous Sim-HB? Moreover. how can we quantitatively characterize the difference in their convergence rates?
Moximall Real
Nomentum B
0.3
To answer above questions, we first present more refined version of Assumption 4.4. Especially, for the Jacobian decomposition J S + A from (Decomposition), we introduce a small nonnegative number 2 0 to scale S, leading to the refined version of (Decomposition):
-0.2
-03
0ut-nol Ponennu
-0.4
Step size h
Figure Distribution on the eigenvalues' maximal real part of Js. which governs the local behaviors according to Proposition 2.1. The black region indicates divergence for the corresponding parameters. Smaller momentum expands the range of step sizes for convergence, supporting Corollary 4.7. For small step sizes, the optimal momentum is positive, consistent with Theorem 4.8.
2
0
VayJ
J =
+
(3)
R
V
yz
(x w²))
where a V2J yy", and aR (a ("""""))" This
decomposition is also utilized establish the convergence rate of (Gradient Flow) in (Wang & Chizat, 2024).
In minimization, it is well known that larger momentum can enable local convergence with a broader range of step sizes. We also provide proof and experiments on this point in Appendix
In Theorem 4.9, we characterize the largest real part of the eigenvalues of JA, the Jacobian of Continuous Alt-HB. According to Proposition 2.1, a smaller real part implies a faster convergence rate. Additionally, for technical reasons, we assume m n for (Min-Max Games).
However, Corollary 4.7 does not imply that the smallest possible momentum should always be used. Theorem 4.8 shows that excessively negative momentum can slow con- vergence. Additionally, for sufficiently small step sizes, the optimal momentum is positive.
Theorem 4.9. Suppose Vay [x"" ; .y") is full-rank and has distinct singular values. Let XA be the eigenvalue of Ja with the largest real part. Then there exist an eigenvalue As of Is and singular value a of aay [x" .35" such that Theorem 4.8. If [ v) satisfies Assumption 4. and 4.5, [R(A]] and i S minxesp(J) R(X))) then the momentum parameter 3(h) that achieves optimal local convergence rate for Continuous Sim-IIB is positive number.
R((A)) = -R(As) (1 - 3) -1-9)210PP
+0
ha).
(4)
Theorem 4.9 demonstrates that when and are sufficiently small, such that the term O + ha) becomes negligible, Continuous Alt-HB exhibits exponentially accelerated lo- cal convergence rate compared to Continuous Sim-HB. The algebraic condition for V2vf(=",,'' is mild, as it holds with probability one for randomly generated matrices from absolutely continuous distribution. The numerical experi- ments for Theorem 4.9 are provided in Appendix I.3.
Theorem 4.8 is proved by analyzing the derivative of the eigenvalue of Is with respect to the momentum parameter 33 and examining the location of the roots of this derivative. The detailed proof is provided in Appendix G.
In Figure 2, we presents numerical experiments validating the theoretical results in this section. The findings show that smaller momentum allows the algorithm achieve local convergence over broader range of step sizes. Additionally, for sufficiently small step sizes, positive momentum enables the algorithm to achieve the optimal convergence rate. These results align with the theoretical predictions in this section.
To establish Theorem 4.9, we regard JA as perturbation of Js with respect to parameters a and h. The theorem can be proved using tools from matrix perturbation theory. The detailed proof is provided in Appendix H. Additionally, computing the coefficients of ((ha) in (4) requires calcu- lating perturbed normalized eigenvectors, which is widely recognized as a challenging problem (Bamieh, 2020), and choose leave this topic for further work.
4.3. Analysis of Alternating Updates
In this section, we investigate the convergence rate of Con- tinuous Alt-HB near local Nash equilibrium (z", y²). Specifically, drawing on the observation from Proposi- tion 3.2, which highlights the separation between Continu- ous Sim-HI HB and Continuous Alt-HB in bilinear games, we
Remark 4.10. The requirement that hs and a in Theorem 4.9 be sufficiently small is crucial for establishing the superior- ity of Continuous Alt-HB, Appendix 1.4 presents an example illustrating that this superiority may not hold if the condition is not satisfied.
6

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
5. Implicit Gradient Regularization
which drives V
2 to decrease. Conversely, the second
equation contains a gradient ascent term with respect to y:
Recent studies in minimization have shown that continuous- time models can reveal how algorithms like gradient descent implicitly regularize optimization trajectories, guiding them toward shallower slope regions of the loss landscape, i.e., areas with smaller [xx)) when (1x) is the objective function. This phenomenon, known as implicit gradient regularization (Barrett & Dherin, 2021), is crucial for un- derstanding the effectiveness of optimization algorithms in modern deep learning, as flatter solutions are linked to bet- ter generalization (Foret et al., 2021). Additionally, (Ghosh et al., 2023) investigated the implicit gradient regulariza- tion of heavy ball momentum algorithm in minimization and demonstrated that a larger momentum parameter / can amplify this effect. Motivated by these findings, a natural question arises:
h 5) 4(1 B13
h(1+8) 4(1 - B)3 V yas Vaf,
(6)
which tends to increase V Since the coefficient h + B)/4(1 3)3 is an increasing function of B, smaller / reduces both effects.
In games satisfying Assumption 4.4, the interaction between players dominates game dynamics, that is, f2 y) < V ya (r. y). Thus, with a smaller momentum parameter B, the reduction in the gradient ascent effect from (6) out- weighs the diminished descent effect from (5). Conse- quently, smaller 3 leads to trajectories in Continuous Sim- HB with shallower slope in terms of I| A similar conclusion applies to yfl?.
How does momentum influence the interaction between al- gorithm trajectories and the shallow slope regions of the loss landscapes in min-max games?
Next, we consider Continuous Alt-HB. Since the x z-player's equation remains the same as in simultaneous updates, we focus on the y y-player's equation:
This section aims to argue the following thesis, highlighting that the phenomenon in min-max games is opposite to that in minimization (Ghosh et al., 2023):
h(1 + (3)
④ 1 B
V 21
4(1 - 9)3
h(38 1)
Thesis. In min-max games where players' interactions dom- inate the overall dynamics as described in Assumption 4.4, smaller momentum guides algorithmss' trajectories towards shallower slope regions of loss landscapes, i.e., regions with lower values of f/l + ,|l Moreover, alternat- ing updates amplify this effect compared to simultaneous updates.
+ 4(1 - B)3 V V
(7)
The key difference between the y-player's equation in al- ternating and simultaneous updates lies in the coefficient of the V V term. In simultancous updates. this co- efficient is h11 + 8)/4((1 - 33)², which is always positive for 3 E (-1,1). However, in alternating updates, the co- efficient changes to h(33 1)/4(1 - g)3, which becomes negative when 3 E (-1, }) This implies that for small val- ues of B, the y-player performs gradient descent on V/ 11? in order to minimize it. This is in contrast to simultaneous updates, where the y-player always maximizes || V Consequently, alternating updates encourage trajectories to explore regions with shallower slopes.
In Section 1. we present observations from our continuous- time models of momentum methods that support this the- sis. Section 5.2 provides experimental validation of this thesis. Additional numerical results are provided in Ap- pendix J.
5.1. Observations from Continuous-time Models
To justify the above thesis, we first examine Continuous Sim-HB:
5.2. Experimental Results
Unlike minimization, where algorithms almost always con- verge to local minimum (Lee et al., 2019), the limit sets of algorithms in min-max games are more complex. Beyond convergence to local equilibrium, typical behaviors include convergence limit cycles and other non-convergent dy- namics, commonly observed in practical tasks such GAN training (Mescheder et al., 2018). Our experiments show that the thesis holds across these diverse dynamical patterns. Additional experiments are provided in Appendix J.
1
h(1+ 3)
V
V. [ |V,)
4(1-8)3
1
h(1+ 9)
0- =
vyf
V,
V ll
1 3
4(1 - 3)3
The evolution of the slope / 2 in these equations is influenced by two key terms. The first equation includes gradient descent term for 21 with respect to a::
Experiments on 2D test functions. We present experi- ments on two 2D test functions, which lead the algorithms' trajectories converge to either local equilibrium or a limit
M1 + 8) 4(1 3)3 V.IV2
A(1 + (8) V2J VaJ, (5) B)3

---

Continuous-Tine Analysis of Heavy Ball Momentum in Min-Max Games
cycle, and most parts of these trajectories satisfy Assump- tion 4.4. The test functions are descrihed as follows:
function 1. The test function is [x, v) = -xy², 2 O, where all points on the line (z, 0) are equilibrium points. As shown in Figure 3(a), regions near equilibrium with smaller a values have lower gradient norms.
(a) Convergence equilibrium
(b) Average slopes
Test fumction The test function is f(z. y) 3ry
0.45) + g(x) g(y), where g(2) _ 2 + 6= This construction was also used by (Hsieh et al., 2021; Pethick et al., 2023) to show that certain min-max algorithms exhibit limit cycles. As shown in Figure 3(c), the game has a unique equilibrium, and regions near the equilibrium exhibit lower gradient norms. Furthermore, under this test function, heavy ball momentum converges limit cycles, highlighted by the white curves Figure 3(c).
(c) Convergence to limit cycles
(d) Average slopes
For each function, we present sample trajectories and the evolution of trajectories' average slopes as / changes. The average slopes are numerically calculated through
Figure 3. Trajectories and average slopes for test function and 2. The background color in trajectories' pictures represent the magnitude of the gradient norm, i.c., +l.fl"+IIVvfff
[ (IV=//1²+IV ds AvgSlope(B) [(B) S(())
To measure the implicit regularization effects, evaluate the average slopes of algorithm trajectories, as in previ- ous experiments. Since integrating over high-dimensional GANs training trajectories challenging, we use cumula- tive average slopes as an alternative measure. At iteration I, the cumulative average slope of algorithms' trajectory calculated as
where [(3) denotes the total trajectory length for given momentum 5(3). Lower average slope values indicate that algorithms'' trajectories explore shallower slope regions of min-max loss landscapes.
Figure 3(a) and 3(C) show that smaller 3 guides the sample trajectories toward regions with lower slopes. Figure 3(b) and 3(d) demonstrate that for both simultaneous and alter- nating updates, smaller results in trajectories with lower average slopes. Additionally, for fixed Alt-HB produces trajectories with lower average slopes than Sim-HB, These experimental results fully support our thesis.
1 AvgS (t) = Σ
Figure 4(a) shows the evolution of AvgS (tt))tt for trajectories with different 3 under alternating updates. The results indi- cate that smaller momentum leads to smaller average slopes. Figure 4(b) compares two trajectories that differ only in their update rules, and alternating update has lower average slopes than simultaneous update. All of these results support the predictions made by the thesis.
Experiments on GANs training. We provide experi- ments on GANs training dynamics. The aim these experi- ments is not to beat the state-of-the-art, but rather to validate our thesis on the implicit gradient regularization effect of momentum in GANs training setting. Future details and experiments are presented in Appendix J.2. Our setup gen- erally follows the Wasserstein GANs framework (Gulrajani et al., 2017) using the CIFAR- 10 dataset. We train GANs using the Adam algorithm with different heavy ball momen- tum parameters, updating the generator and discriminator either alternately or simultaneously. Future details include: Neural network architecture: Both generator and discrimi- nator the ResNet-33 32 architecture. Both generator and discriminator use the learning rate 2e-4, with linearly de- creasing step size schedule. The batch size is 64. During the training, we update both the generator and discriminator in each iteration, which is consistent with the algorithms investigated in this work.
Interestingly, the implicit gradient regularization effect ap- pears to be linked to GAN training quality. In Figures 4(c) and 4(d), we use the Fréchet Inception Distance (FID) to evaluate GANs performance, where lower FID values indi- cate better GANs performance (Heusel al., 2017). The results show that trajectories with lower average slopes cor- respond to better training outcomes. This may be attributed to the implicit gradient regularization effect, which guides optimization trajectories away from sharp gradient regions in the min-max loss landscape, and these regions are be- lieved to be a major factor in GAN training failures (Thanh- Tung al., 2019; Wu al., 2021).
8

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
complished under Grant Number W911NFF24-1-0045 This work supported by the Swiss National Science Founda- tion (SNSF) under grant number 200021
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential socictal consequences of our work, none of which we feel must be specifically highlighted here.
(a) Average Slopes, different (b) Average Slopes, vs. sim
B
References
Azizian, W., Scieur, D., Mitliagkas, I., Lacoste-Julien, S., and Gidel, G. Accelerating smooth games by manipulat- ing spectral shapes. In International Conference on Arti- ficial Intelligence and Statistics, pp. 1705-1715. PMLR, 2020.
(c) FID, different B
(d) FID, alt vs. sim
Figure 4. Experimental results for GANs training dynamics. Smaller momentum and alternating updates lead the trajectories to lower average slopes. Trajectories with lower average slopes also have lower FID, indicating the better GANs training outcome.
Bailey, J. P., Gidel, G., and Piliouras, G. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent, In Conference on Learning Theory, pp. 391 407. PMLR, 2020.
Bamich, B. A tutorial on matrix perturbation the- ory (using compact matrix notation). arXiv preprint arXiv:2002.0500/, 2020.
6. Conclusions and Future Directions
In this paper, explored the effects of momentum and updates rules in min-max games using continuous-time models. We analyzed the local convergence properties and the implicit gradient regularization effects of momentum algorithms, revealing fundamental differences in the role of momentum between min-max games and minimization. One of the limitations of this work is that do not consider the potential impact of using stochastic gradient methods algorithms' dynamics. Our results also suggest a potential link between implicit regularization and training outcomes in min-max games. Exploring this connection further and developing a general theoretical framework, similar to that established the minimization setting, presents an exciting avenue for future research.
Barrett, D. G. and Dherin, B. Implicit gradient regulariza- tion. ICLR, 2021.
Compagnoni, E. M., Liu, T., Islamov, R., Proske, N., Orvieto, A., and Lucchi, A. Adaptive methods through the lens of sdes: Theoretical insights on the role noise. arXiv preprint arXiv:2411.15955 2024a.
Compagnoni, E. M., Orvicto, A., Kersting, H., Proske, F., and Lucchi, A. Sdes for minimax optimization. In Interna- tional Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2024b.
Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng, H. Training GANs with optimism. arXiv preprint 1rXiv:111.0004411 2017.
Acknowledgments
Do, K., Le, T. H., Nguyen, D., Nguyen, D., Harikumar, H., Tran, T., Rana, S., and Venkatesh, S. Momentum adversarial distillation: Handling large distribution shifts in data-fre free knowledge distillation. Advances in Neural Information Processing Systems, 15:10055-10067, 2022.
The authors sincerely thank the valuable comments from the anonymous reviewers. Kaito Fujii was supported by FY2024 Researcher Exchange Program between JSPS and ETH and JSPS KAKENHI Grant Number 22K17857.
Stratis Skoulakis supported by Villum Young Investiga- tor Award no. 72091. Xiao Wang acknowledges Grant 2021 10458 from SUFE and support from the Shanghai Re- search Center for Data Science and Decision Technology. This work was supported by Hasler Foundation Program:
Fang, Z., Liu, Z., Yu, C., and Hu, C. Rapid learning in constrained minimax games with negative momentum. AAAI, 2025.
Feng. Y., Piliouras, G., and Wang. X. Prediction accuracy of learning in games: Follow-the-regularizedd leader meets heisenberg. ICMI., 2024.
Hasler Responsible AI (project number 21043). Research was sponsored by the Army Research Office and was ac-

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
Foret, P., Kleiner, A., Mobahi, H., and Neyshabur, B. Sharpness-aware minimization for efficiently improving generalization. ICLR, 2021.
Lee, J., Cho, H., and Yun, C. Fundamental benefit of alter- nating updates in minimax optimization. In Proceedings of the 41 International Conference Machine Learn- ing. 2024.
Ghosh, A., Lyu, H., Zhang, X., and Wang, R. Implicit regu- larization in heavy-ball momentum accelerated stochastic gradient descent. ICLR, 2023.
Lee, J. D., Panageas, I., Piliouras. G., Simchowitz, M.. Jor- dan, M. I., and Recht, B. First-order methods almost always avoid strict saddle points. Mathmatical program- ming, 176:311 1-371 2019.
Gidel, G., Hemmat, R. A., Pezeshki, M., Le Priol, R., Huang, G. Lacoste-Juliens S., and Mitliagkas, I. Negative mo- mentum for improved game dynamies. In The 22nd Inter- national Conference on Artificial Intelligence and Statis- tics, 2019.
2019.
Lessard, L., Recht, B., and Packard, A. Analysis and de- sign of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57-95, 2016.
Goh, G. Why momentum really works. Distill, 2017. doi: 10. 10.23915/dissiil.00006 URL htt.httt///ditiil... pub/ 7 /mmmentum.
Letcher, A., Balduzzi, D., Racanière, S., Martens, J., Foer- ster, J., Tuyls, K., and Graepel, T. Differentiable game mechanies. Journal of Machine Learning Research, 20 (84):1-40, 2019.
Goodfellow, I. J., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. Generative adversarial nets. In Proceedings of the Neural Information Processing Systems Volume 2, NIPS 14, pp. Cambridge, MA, USA, 2014. MIT Press.
Li, Q., Tai, C., al. Stochastic modified equations and adap- tive stochastic gradient algorithms. In International Con- ference on Machine Learning, pp. 2101-2110 PMLR, 2017.
27th International Conference
Graham, A. Matrix Theory and Applications for Scientists and Engineers. Courier Dover Publications, 2018
Lotidis, K., Giannou, A., Mertikopoulos, P., and Bambos, N. Accelerated regularized learning in finite n-person games. In The Thirty-eighth Annual Conference on Neural Infor- mation Processing Systems, 2024.
Gulrajani, I., Ahmed, F., Arjovsky, M., Dumoulin, V., and Courville, A. C. Improved training of Wasserstein GANs. Advances in neural information processing systems, 30, 2017.
Lu, H. An o (sr)-resolution ode framework for understand- ing discrete-time algorithms and applications to the linear convergence of minimax problems. Mathematical Pro- gramming. 194(1):1061-1122 2022.
Hait, S., Li, P., Luo, H., and Zhang, M. Alternating regret for online convex optimization. arXiv preprint arXiv:2502.12529 2025.
Madry, A. Towards deep learning models resistant to adver- sarial attacks. arXiv preprint arXiv:1706.0660 06000.00003.....00000000000...88 2017.
Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., and Hochreiter, S. GANs trained by two time-scale update rule converge local Nash equilibrium. Advances in Neural Information Processing Systems, 30, 2017.
Mescheder, L.., Geiger, A., and Nowozin, S. Which training methods for GANs do actually converge? In Interna- tional Conference Machine Learning, pp. 3481-3490. PMLR, 2018
Hsieh, Y.P.., Mertikopoulos, P., and Cevher, V. The limits of min-max optimization algorithms: Convergence to spurious non-critical sets. International Conference on Machine Learning, pp. 4337-4348. PMLR, 2021.
Muehlebach, M. and Jordan, M. A dynamical systems per- spective on Nesterov acceleration. In International Con- ference Machine Learning, pp. 4656-4662. PMLR, 2019.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.69888 2014.
Muehlebach, M. and Jordan, M. I. Optimization with mo- mentum: Dynamical, control-theoretic, and symplectic perspectives. Journal of Machine Learning Research, 22 (73):1-50, 2021.
Korpelevich, G. M. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Kovachki, N. B. and Stuart, A. M. Continuous time analysis of momentum methods. Journal of Machine Learning Research, 22(17):1 2021.
Ochs, P. Local convergence the heavy-ball method and iPiano for non-convex optimization. Journal of Optimiza- tion Theory and Applications, 177(1):153-18) 2018.
10

---

Continuous-Tineg Analysis of Heavy Ball Momentum in Min-Max Games
O'Donoghue, B. and Candes, E. Adaptive restart for accel- erated gradient schemes. Foundations of Computational Mathematics, 15:715-732, 2015.
of Polyak-Lojasiewiez functions when the non-convexity is averaged-out, In International Conference on Machine Learning, pp. 228644 PMLR, 2022.
Pethick, T., Xie, W. and Cevher, V. Stable nonconvex- nonconcave training via linear interpolation. Advances in Neural Information Processing Systems, 36:49830- 49841, 2023.
Wang. Y., Ma, X., Bailey, J., Yi, Zhou, B., and Gu, Q. On the convergence and robustness of adversarial training. In International Conference on Machine Learning, pp. 6586-6595. PMLR, 2019.
Polyak, B. T. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
Wibisono, A., Wilson, A. C., and Jordan, M. I. A variational perspective on accelerated methods in optimization. pro- ceedings of the National Academy of Sciences, 113(47);
E7351-E7358, 2016.
Qian, N. On the momentum term in gradient descent learn- ing algorithms. Neural networks, 12(1):145-151, 1999.
Wibisono, A., Tao, M., and Piliouras, G. Alternating mir- ror descent for constrained min-max games. Advances in Neural Information Processing Systems, 35:35201- 35212, 2022.
Ratliff, I.. Burden, A., and Sastry, S. On the charac- terization of local Nash equilibria in continuous games. IEEE Transactions Automatic Control, 61(8):2301- 2307, 2016.
Wu, Y.-L., Shuai, H.-H., Tam, Z.-R., and Chiu, H.-Y. Gradi- ent normalization for generative adversarial networks. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp- 6373-6382, 2021.
Rosca, M. C., Wu, Y., Dherin, B., and Barrett, D. Discretiza- tion drift in two-player games. In International Con- ference on Machine Learning, pp. 9064-9074. PMLR, 2021.
Yang. J., Orvieto, A., Lucchi, A., and He, N. Faster single- loop algorithms for minimax optimization without strong concavity. In International Conference on Artificial Intel- ligence and Statistics, pp. 5485-5517, PMLR, 2022.
Salimans, T., Goodfellow, I. Zaremba, W., Cheung, V.,
Radford, A., and Chen, X. Improved techniques for training gans. Advances in neural information processing systems, 29, 2016.
Zhang, G. and Wang. Y. On the suboptimality of negative momentum for minimax optimization. In International Conference on Artificial Intelligence and Statistics, pp. 2098-2106. PMLR, 2021.
Shi, B., Du, S. S., Jordan, M. I., and Su, W. J. Understanding the acceleration phenomenon via high-resolution differ- ential equations. Mathematical Programming, pp. 1-70, 2022.
Zhang, G., Bao, X., Lessard, L., and Grosse, R. A unified analysis of first-order methods for smooth games via inte- gral quadratic constraints. Journal of Machine Learning Research, 22(103):1-39, 2021.
Su, W., Boyd, S., and Candès, E. J. A differential equa- tion for modeling nesterov's 's accelerated gradient method: Theory and insights. Journal of Machine Learning Re- search, 17(153):1 1-:3, 11.1111416.6.6 2016.
Zhang, G., Wang. Y., Lessard, L., and Grosse, R. B. Near- optimal local convergence of alternating gradient descent- ascent for minimax optimization. In International Con- ference on Artificial Intelligence and Statistics, pp. 7659- 7679. PMLR, 2022.
Sutskever, I., Martens, J., Dahl, G., and Hinton, G. On the importance of initialization and momentum in deep learn ing. In Proceedings of the 30th International Conference on Machine Learning, Proceedings of Machine Learning Research, pp. 1139-1147, PMLR, 17-19 Jun 2013.
Thanh- Tung, H., Tran, T., and Venkatesh, S. Improving generalization and stability of generative adversarial net- works. ICLR, 2019.
Wang, G. and Chizat, I.. Local convergence of gradient methods for min-max games: partial curvature generi- cally suffices. Advances in Neural Information Process- ing Systems, 36, 2024.
Wang, J.-K., Lin, C.H.,, Wibisono, A., and Hu, B. Provable acceleration of heavy ball beyond quadraties for a class

---

Continuous-Timen Analysis of Heavy Ball Momentum in Min-Max Games
A. More Experiments on Comparing Trajectories between Continuous-time Equations and Discrete-time Algorithms
In this section, we provide experiments in examples provided in Figure of (Compagnoni et al., 2024b).
Trajectories Update, B 0.4
selrien
6imH8
Distance Curve, Simultneous Update
Jest Potcl
Sinultneous Update
Funciion Value
Fudiier Dataoce
45
-10
Tonation
(a) Trajectories of Continuous Sim-HH and Sim-HB.(b) Distance between ODEs and algorithms, simulta- neous update.
Trajectories Altemating Update. 0.4
Distance Curve, Alternating Update
bedd Poirt
Alteraatng Updale
Funchton Vslue
NM
Mm Wyy
Builder
(c) Trajectories of Continuous Alt-HB and Alt-HB. (d) Distance between ODEs and algorithms, alternat- ing update.
- This function is also used by top left of Figure in (Compagnoni et al., 2024) to compare the trajectories between algorithms and their SDE models. Here we set step size h 0.001 and -0.4 for the heavy hall method. The trajectories converge limit cycles. From 5(a) and 5(c), the trajectories of the discrete-ting time algorithms closely match our continuous time equations. In 5(b) and 5(d), we show the Euclidean distance between these traeectories. Specially, the distance between trajectories remains around 0.01 after 100000 iterations
Figure 5. The function f(r. v) = >(y 0.45) <(x) ply), x(=) 1
B. Proof of Theorem 3.1
B.1. Proof Overview and Discussions
There are several methods the minimization literature to provide continuous-time equations to model the discrete-time momentum methods, for example, (Su et al., 2016; Shi et al., 2022) and (Muehlebach & Jordan, 2019). Most these methods are specially designed for the setting where the objective function f(xx) a (strongly) convex function, and the choice of step size and momentum are coupled together using numerical conditions of f(z) such the condition numbers. These methods not suitable for purposes because aim to develop models that allow the momentum and step size to change independently, thus enabling us to better understand the effects of each term on the learning dynamics in min-max games.
The continuous-time time models used the current paper is inspired by recent work (Ghosh et al., 2023), which try to use continuous- time models of heavy ball momentum to understand their implicit gradient regularization in minimization problems. The proof strategies of Theorem 3.1 can be summarized in two steps:
12

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
Trajectories of Simutaansus Update, B
0.5
086
072
Distance Curve, Simultaneous Update
Indial Paint Equiliiium
0-1
Simutheous Update
00000 Value
024
Dudiden Tldtrre
0.0
000
-232
?
-0.40
-0.22
3.3
(a) Trajectories of Continuous Sim-HB and Sim-HB.(b) Distance between ODEs and algorithms, simulta- neous update.
Trajectories of Altemating Update, 8-
0.5
0:4
Contimannn anfiliin
072
Distance Curve, Alternating Update
Equiliriam tra
3.11
Allemeting Updale
Buckea Oetano
4220
4.54
4.20
100
1.00
00
05
08
23
100
(c) Trajectories of Continuous Alt-HB and Alt-HB. (d) Distance between ODEs and algorithms, alternat- ing update.
Figure 6. The test function is f(2 ry + <(x) -(y), <(=) - - 8 g2" This function is also used by bottom left Figure in (Compagnoni et al., 2024) to compare the trajectories hetween algorithms and their SDE models. Here we set step size h = 0.001 and = 0.5 for the heavy hall method. The trajectories converge to equilibrium. From 6(a) and 6(c), the trajectories of the discrete- tetrette-immeeeee algorithms closely match our continuous- time equations. In 6(b) and 6(d), we show the Euclidean distance between these trajectories. We find these two curves only have very slightly differences. Morcover, the distances between these curves are close 0.00001 after 10000 iterations
Step 1: Firstly, we calculate family of piecewise differential equations indexed by n. and each one is defined on the finite time region [4n, (1)1) where in = Jn, and h is the step size of the discrete-time algorithms. The solution of these equations can be linked to continuous curves that serve as good approximations of the original discrete-time algorithms. In our case, it can be proved that the local error between these continuous- solutions and the discrete- time trajectories belongs to (1h)). However, this family of equations has several drawbacks: they are not differentiable the time nodes, and their formulation is dependent on n, which lead them be complex analysis.
Step 2: Secondly, we show that this family of differential equations can converge to a differential equation which independent of and is differentiable everywhere with an exponential rate. This exponential rate convergence enables to consider the solution of this single differential equation instead of the family of equations defined in Step 1. In fact, we can prove that after very short time region, the distance between the trajectories of this single equation and the solution of the equations defined in step 1 stops growth and can be bounded in (1,3) local error. This provide the theoretical guarantee that this single equation can serve as a good approximation of the original discrete-time algorithms.
The above two steps are needed both for simultaneous updates and alternating updates of heavy ball momentum in min-max games. In Lemma I.I and Lemma B.4, we will calculate the family of piecewise differentiable equations for Sim-HB and Alt-HB. We will see that because there are two players in a min-mat max game, the continuous-ti equations we get for heavy
13

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
ball momentum methods very different from the in (Ghosh al., 2023).
For example, if we consider the simultaneous update, as Lemma B.1 shows, the a-player's equation is written
1 - -- 3m
h
a(t)
1-3 V=f(=(t).u(t)) 2(1 8)2
(z v(t)) Vaf(z(t) V (aff(((t), Vyf(e(t),
and the equations in (Ghosh et al., 2023) (Theorem 4.1 in their paper) are written as
1 1-98 8 V v.f(x(t))
h7n
i(t)
2(1 B)2 (af(x(t)) Vaf(x(()),
((((ttt)Vva((((()))
1-3
the key term V Vayf(z(t), v(t) vaf(((t), v()) important for understanding the great differences the role of momentum in min-max games and minimization.
In Lemma B.3 and B.5, we prove the family of piecewise differentiable equations defined in Lemma B. 1 and Lemma B.4 can quickly converge to equations independent of index n. This can be seen from the fact that the dependence of n in Lemma B.I and Lemma B.4 appears only in the form 3 Since 3 E (-1,1), 8 vanishes with an exponential rate.
B.2. Simultaneous Updates
Lemma B.1. Let tn = nh where is the step size used by Sim-HB. Then in time region [ta, 1n+1), the solution of the following ODEs:
gah
a(t)
Val(o(t),
1 - 3
hnn
(Va
(ee))))0))(( v.l(a(()
2(1 - B)2
1 3m
j(t)
V Vyf(x(t).v(() v(t)
1
lnn
2(1 B)2 (Vy=f(x(t) v()) v.f(=((), - V)f(((t))u())) v)S(=(t),(())).
can approximate the trajectories of Sim-HB with an (local error.
Here 7n = - 3m [(1
() + g2i+1) 4.8+1].
Proof. Assume time region [tn, 11), we have
#(t) - + (z),
(8)
i(t)
+ (BB,()))))
(9)
Our aim is to find functions G2 (x((), w(t) F. (x(t), (z))) and (x(t), v(t) such that
(r(tn41)- - (z(tx) -
(10)
(u(1n+1) - v((n)) - B (v((n) - -
(11)
hold.
In the following, we will use the notation e(t,)) (resp. ((t+)) to denote the right first-order derivative (resp. second-order derivative) of x at t. Similarly, the notation (t,,)) (resp. ((t,)) )) is used to denote the left first-order derivative (resp. second-order derivative) of x at fn.
14

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
From Lemma B.2, we have ((1))) and 3 (1 bounded independent of h. Thus, by Taylor expansion, have r(bn+1)- x(tn) r(6n + h) - x((n)
= hb((t,t + h²2 i(t,) + O
(12)
2
From (8) and (9), can calculate a(ttt
a(t)) -
=(t,t) - (a
= De
((,))
0(4)) (13)
Take (8) and (13) into (12), we get
atIn-1 - x((n)
( v(.))) n2 A,,,,t(())
122
+
2 (tt htt.://hhhhhhhaaa.ccccooa/aaahaa +
(14)
With a similar calculation on the Taylor expansion of (1nnn1) at point s(bn), we get
h
(x((x)) 1000-x((n-10 x(tn-1)) -3 ht((t))) [t,,)
+0(h))
(15)
Recall that our aim determine the formulation of (r, v), (r y) An (x. y), B,, (,, y) such that (10) holds. From (14) and (15), we have calculated the Taylor expansion of =(tx+1)-=((( 3 (z(t.)) x(tn-1)).
Next, we will compare the coefficients of this Taylor expansion with (10), which gives
(VV.G.(((t)), - = (nNaa(
(16)
and
(n(r(t)) + (V(Gn(a(taa) - Veng) FyFa
(An-1(x((>) (a 0.
V (.F.
(17)
Note that (16) gives a recurrence relation between Vz (x(tn), (tn))) and V.Gu-1 this relation gives
(I(tn), (z(tn). for n e N, and solving
Va (z((m) = 1- gr+1
Val (I(4n),
(18)
B
With a similar argument for y-player's equation (9), we can get
gr+1
VyFn (x(tx))
1-B Vyd (I(tn),
(19)
15

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
Next solve (n, v) from (17). We first rewrite (17) the following form:
An (=((t))
= - 1 (V
-Vayy (r((n), (athh -V (o(l))
(20)
From (18) and (19), we have
V2G, (I((tn), ((T)) VaGn (oa (t)
(-- - gmtt)
2
( 1 8r)
(1-00) ))
Ve (2f(((tn) Vat (x(t
1-1 + 3
(21)
1 1- 3
and
V Gn Gn (z(4n))y(4a)) vyPn (x(lm), v((n)) + Gn (d(h)) (z( 1- (---9))) + 3
(-=)) )
1- 3m 2 Vayl (x((4), V (I((m))
(22)
Taking (21) and (22) into (20), obtain recurrence relation between A, (x(t,), v(t,)) and An (e(tn)).(tnn)) By solving this recurrence relation, we can derive the formulation of An (z(tn), (ta))
An (z((t)) (tm)))
2(1 -31- Vn Vif (z(tn). Vzf (z(tx), v(t,)) Vzyf (I(tn), (t,n) of (z(tn). v(tr)))
(23)
where %n -i=0 [(1 + B) + 3 - 43
Combining the above, we have determined the formulation of è in time region [ta, fn41) as follows:
gm+1 a(1) (1 - B h
Vol (c(())))((())
2(1 - 3)2 (Vaf (x(tn), v(t,)) Vaf (z(ta), y(tn)) (x(tx), v(t))) (x)t) Vyf (z(tz), v(t))) (I(t)))((ta))
(24)
This completes the proof of the part of Lemma B.I. Since in Simultaneous update, s(l) and y(l) are symmetrical, the part for yt) is similar to the above, and we omit it here.
Lemma B.2. Under the assumplion that [xx, y) is smooth function with bounded derivatives up to the fourth order as stated in Theorem 3.1, then (t), i(t and 5 (t) are bounded independent of h.
Proof. By assumption, we have | af assume the derivatives of f(x, y) up to the fourth order are bounded by constant C.
af (x, y) are bounded independent of h, where o, b, c, d equal to x or y. We also
The aim of this Lemma is guarantee that we can faithfully truncate the Taylor-expansion in (12) to get an error of O(1)).
To achieve this, we need to make that the terms it), (t)) and F (t) are bounded independent of h.
Let firstly consider (t). From (24) and the boundedness assumption of the first- and second-order derivatives, we have
1 gm
|+(1)1
Va. (x (ll)))))
2(1 3)2 7n 1V (a((n), ((.)) II (x((,)).((t)))
1 - 3
h
V S (z(()), 11 (x ((n))
2(1 - 8)2 Tm
1 gu+l
C+ h (1 3)2
nn C SC
1-3
16

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
Here the boundedness of h, which is a small positive number, and C2 is constant number independent of h. Note that from (12), H(t) and W (t) can also be formulated combinations of the derivatives of f(, y) up the fourth order. Therefore, their boundedness can be proved in similar way.
Lemma B.3. Let T be a fixed time horizon, and [0, T. Let (f(t), denote the solution trajectory of the equations defined in Lemmna B.I, and (æ(t)), v(t) denote the solution trajectory of the equations defined in Theorem 3.1 for Continuous Sim-HB, Ifn. n > 2 log(h)/ (8g( and at time ln nh we have
(z(tn).ū(t.)) (z(tn).
then at time tn+1= = (n + 1)h, we have
Proof. We will prove
[z0(t=+1) x -((+))))==== O(h))
and the argument for y-player follows similarly. Using Taylor expansion, we have
122
i(nh + h) - i(nh) = hx(nhh+) + i(nh+ + O(h)),
2
1²2
æ(nh + h) - x<(nh) = hx((h)) + i((h) + O1h)).
2
Thus, we obtain
222 [[ā(n)ht) ((h))))+0(()))
[a((n+1) - (l (1++))]=== Ml(((n)
=(nn))] (aa
In the following, we will show both of the terms hl[(&(n++) - i(nh))] and 4 [l(a(n)+) - #(nh))]l belong to O(h)).
From Continuous Sim-HB, we have
hā(nh) -- - (1-h h
A. + (V (al(a()))
(((((()))
2(1 2(1-3)3
v=n,(r((n). V (of(r(n)),ynnn) y(nh)))
(25)
From Lemma B.1, we have
h(1 3d)
hihnh)
V v=
1-3
h² 3)
(1-3) [+33
(1 - 4(n + 1)gn+1
32n+2)
(2((((h)) Val(a(nh),
2(1 333
(yf(z(nh). v(nh))]
(26)
Using (25) minus (26), we get
h hz(nh))hā((m -- 3 (( V h²(1+ B)
2(-B3) g2n+2 4(n + 1)g (1-9)
(V2f(x(nh)) v(nh)) V= v(nh)) (znf(=(nh)) y(nh)) Vzf(z(nh), v(nh))
(27)
Since n > llggh)) log(3) + 3m < h2 and f(z, y) have bounded first- and second-order derivatives, we have the first term the above equality, i.e., - VaJ, belongs to (1h3).
17

---

Continuous-Time Time Analysis of Heavy Ball Momentum in Min-Max Games
Similarly, for the term
+ 3) 2(1 B)3
( 1 11-2 9
1 3 }
g2nt2 + 4(n + 1)8r+1
(Vaf(r(nh)) u(nh)) (=f(x(nh)) (=(((()))))(())) Vagf(a(nh) u()))) VyJ (a((x(n)), v(nh)))
in ha(h)) (nh), due to the boundedness of first- and second-order derivatives, we only need to show that the coefficient
h (1 + B) 2(1 3333
1 (1-1)
33nt2 4(n + 1)
1+
belongs O(h9). This be guaranteed since have > 2log(h)/ log(3) f < h2 and this implies
(n + 1)3a+1 < T. gmt < TBh, gam+2 12
Similarly, under the same condition n > 2 / (8), we can prove h2n(nh) 122 (mh) E O(19) given the condition that ((x,)) has bounded derivatives to the third order.
B.3. Alternating Updates
Lemma B.4. Let la = nh where h is the step size used by Alt-HB. Then in time region (In. In),), the solution of the following ODEs:
1 gm
=(t)
Vaf(o(t),u(t))
1-3
(Vif(z(t), (..())))v((((() (vrr()))))))) (f(=(t))v(t)))
2(1 8)2
- 3"
i(t)
V vyf(z(t), v(t)
1 1- 3
hyn
+ 2(1 - 8)2 (vzzf(r(t)
hdn
2(1 - 3)2 V (or((( Vzf())
can approximate the trajectories of AlI-HB with a (1o)) error. Here in Ei= 8r-1 + 3)(1 + (2221) - 43
and 6n En E. (1 (01111+-11110000 (1 B).
Proof. Recall that Alt-HB is written as
In+1 Fn. -/Vaa Mn) + (86 xn
(28)
Un+1 Yn +
(ym mn-
(29)
Assume in time region [t,, 4n11), we have
a(t) (,Gn(I,)) (z, i(t) Fx y) hB,
(30)
(31)
Our aim is to find functions G,(x,)). (x, v), A, (x, v). and B, (x, v) such that
(x(tn+1) xt(ttt)) 3 (x((t)) ()) = hv Attt((
(32)
and
(u((n+1)-1/f )) - (y((tr) ( (l
(33)
18

---

Continuous- Time Analysis of Heavy Ball Momentum in Min-Max Games
hold.
In this proof, will focus on the derivation of (n v) and (z, v), since the derivation of (n, and An y) is the same as in Lemma B.1.
In the following, we will use the notation 5(47) (resp. ((t)) to denote the right first-order derivative (resp. second-order derivative) of x at t. Similarly, the notation i(t,,) (resp. j((t,))) is used to denote the left first-order derivative (resp. second-order derivative) of y at nn-
We begin by performing Taylor expansion of
u(tn)) time t. Recall that ćn nh, then
, + h), v(t))))))))))))))))))))))) = hV / 18-
+
= -VVyf(r(tw) v(tn) - 1/2
V /anff/ttaaluuta//////ttttttttdad - 3
(34)
Note that in (34), we use the fact that
a((n) = 11 -
1- -1--)-)--)
gatt
Va
(ts(
which can be derived in the same way in Lemma B.I.
Using the Taylor expansion of ytn, + h) at time tw. we also have
v(t, h)) = ((,.) + ho(tt) 122
+(())+
(35)
From (31), we have
((t)) v,F,(o(t,)) + (BB((((t)))v(tt.)))
(36)
and
((()t (1))) ((t)++ + VysPai -(th)))++((+++000 (T
- (or ( +0()
(37)
Taking above into (35), we can get the following formula of ((tx+1) v(t))
(tnn ((m)) = hij(tt) + - - 0(12)
1
=NV,FF((s((a), (i
122
+ 2 (ott) (FFF)) - V Fa(e(tt) V=Ga((((h) + (113).
(38)
Similarly, can get the Taylor expansion of yt.,, h) as time f,,. Note that here will use the left derivatives rather than the right derivatives as in (38). The calculation will be omitted, and we only present the final results here:
(y((t)) u(t, h)) 3h
(=G., Tha
(39)
19

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
Combine (39) and (38), get
(v((n+11) -
=h F (V - AV, (
+ + (BB
2²
+ [t
(
2
42
VV (
(40)
2
+ O(h*).
(41)
Now compare (34) and (41), get the following equalities:
V VyFn(En,Bin - ( Mn) = V Vn ( Un)
(42)
and
[n Mn) - 1
+
(z v(.)))
V (o u() (oChhoohhhhtttt-------oo-heehhhd (ett
ga+1 V y Un) (T).
(43)
1
(42) gives a recurrence relation between Fz and Fn-1, and solving this relation gives
v,F,(1,))= 1 1 1-t
1- (gf(s,
(44)
As have also known
1- gm+1
(z,,(z
V (x,
(45)
1
taking v.Fn(z. VnGn(z, y) into (43), we can get
1 +
33
(x 2(1 3)3 (zf()))) vyf(E.)) +
2(1 B)3 vorl(r,)) Va)(r,u).
(46)
and this finished the proof.
Lemma B.5. Let (ī(t), m(t) denote the solution trajectory of the equations defined in Lemma B.4, and (a(t), y(t) denotes the solution trajectory of the equations defined Theorem 3.1 for Continuous Alt-HB, If n. 2log(h) log(3), then at time In nh we have
(x(t.).
then at time tn+1 (n + 1)h, we have
((ttt)))))((())1)))__))) ((t+)) ||= O(1)). O((7))
The proof of this lemma follows in the same way as that of Lemma B.3; thus, we omit it here.
20

---

Continuous- Time Analysis of Heavy Ball Momentum in Min-Max Games
C. Proof of Proposition 3.2
The proof of Proposition 3.2 is divided into two parts. In Lemma C.I, we prove the part for Continuous Sim-HB. In Lemma C.2, we prove the part for Continuous Alt-HB. Proposition 3.2 directly follows from these two lemmas.
Lemma C.1. In matrix games f(x y) T Ay, Continuous Sim- Sim-HB diverges at an exponential rate regardless of the choice of h and B.
Proof. The Jacobin of Continuous Sim-HB is written
A(++8) R1-838 AAT
Is =
(47)
AT
k(1-8) (1-8)
A
Let A = UEV* be the SVD decomposition of the payoff matrix A. Thus, Σ is a diagonal matrix, and Ut V are orthogonal matrices. Then the matrix in (47) can be decomposed as
u
4(1+8) 211-Bp
ΣET
1-B
U 0
Js
(48)
0
V
A カ1-3
0
v
U
Moreover, it is easy the matrix
is also orthogonal matrix. Thus, the eigenvalues of (47) are the same
the cigenvalues of
h(++2) ΣΣT 21-333
T-3 Σ
(49)
k(++8) Σ 21-33"
I-8
Any eigenvalue λ of matrix (49) satisfies the following equation:
x h(1+
(^
h(1 + 3)
1
2(1 2(13333p)
2(1 - 3333)
+
1 1- 3
0,
(50)
here 2 0 is an cigenvalue of TΣ The solution of (50) is
h(1 + 8)p 2(1 - B)3
+ VA.
(51)
where A -(1-pp> [1-3}²
0. Thus, V is always purely imaginary number, and
1(1 3)p R(A)
2(1 3)3 20, 0,
for any E (-1,1) and h > 0. Therefore, the equation always diverges exponential rate regardless of the choice of h and B.
Lemma C.2. In matrix games f(x, v) Ty, Continuous Alt-HB converges exponentially if 3 is negative and h is
sufficiently small.
Proof. The Jacobin of Continuous Alt-HB is written as:
h(1+8)
AAT
21-3P
JA
(52)
AT
k(1388) 21-37-
A
1-8
21

---

Continuous-Timee Analysis of Heavy Ball Momentum in Min-Max Games
Let A = UEV be the SVD decomposition of the payoff matrix A, where E is diagonal matrix. Then for similar reason in (48), the eigenvalues of matrix in (52) are same the eigenvalues of
M1+0
EST
21-88
(53)
1-3 T E
K1-30
ΣT>
Σ
20-3)3
Any eigenvalue À of matrix (53) satisfies the following equation:
(A
1(1 +
) (*+
1(1 3,3)
1
2(1 (1))))p)
2(1 3)3 p)
+
P
0,
(54)
1 3
where p 2 0 an eigenvalue of ΣΣ The solution of (54) are
h.3p x (1- B)²
+ VA.
(55)
where
p2 (1-
11 + +13)(1 33)pp²
A
(56)
4(1-B)6
(1 (1- B)2
From (56), we can choose sufficiently small h so that A < 0 because the negative term -I-3z= P is independent of h. For such small h and negative B, due to the negativity of A, the real part of is negative number; therefore, the equation has local convergence.
D. Proof of Proposition 4.2 and 4.3
D.1. Proof Proposition 4.2
Proof. Recall that we define
F(x,8)=
f(x. v)
1-
h(1 3)
+
4(1 3)3 (l
and the continuous-time model for simultaneous heavy ball method is given by:
a(t) = -xF(xx)
((t) = Fzr
(Continuous Sim-HB)
The gradient of F(x, y) with respect to is calculated
Vaf(z.v) + h(1 + (8)
(xr =
Va (IV -1
4(1 - 8)3
ht1 3)
Vzf(z.v) + 2(1-3)3 (Vif(x.v) v.f(x.v) vayf(z.v) vzf(z,v)..
1
The gradient of F(x, y) with respect is calculated
Vzf(z.y) + h(1 + B)
V v(x,))
v, ([
4(1 - 3)3
1(1 + (
(zf(z,))
(V
(V v) v.f(z,v) v,5(1,)) v,f(z,))
2(1 - 3)3
22

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
The second-order partial derivative matrix F2 y) is calculated as
1
(a,
1-
+ h(1 + 3)
-1- (Vif(z,)) + (zf(z,)) V Vay=f(z, ( vyf(z,u) - V vzf((z,)) V yunff(r 3))
(57)
Let (x","" be the local equilibrium for which we calculate the Jacobian matrix. From the first-order optimality condition of (x*,y" y), we have the terms v=f y²) and v, ,y") in (57) are zero vectors. Thus, we have
h(1+ B) 2(1 3y3 (V ./) V2f(e' ,²) V Vouf( (1)) f (e",)""))))
F("("" (i- v Vaf(=' ,"'
,y"))
(58)
Similarly, we can calculate the term V Flo ,y),, V yzz .3" and ViF(t* vn) as follows:
1
1(1 + 3)
V Fzy F(*",1")
V VayS (x" ,1
(Vaj(a", Vayd(x', Vayl(x', (zf("" .v)).,))
1-
2(1 - -333
(59)
1
h(1 + 3)
V y0r ,3") =
V fz=f(x" 18")
(Vraf(=',)) Vif(=".0) - Vzf(x"")") - yuaf(="
1 - 3
2(1 6{3
(60)
v """""")" + h(1 + B)
"2F(""""") =
(V (V Vayl("", -V""""""""V'''(''"'"'"""""""'")'
Vyl("" ./") V (2,("",''' y"")
1 B
2(1 3)3
(61)
The Jacobian of Continuous Sim-HB at (a*, 8²) ) is written as
V+F(""11)) -VayFle',
Js
V FuoF
VeF(="
where the terms F2F("* - V Fay v²), F2.((s Fx"" v²)
are given according to (58), (59), (60) and (61).
Val(=","" Vxri(=",0)) "
Js ( 1
1 )
V f= .8)
Vaf(=",8")
Vif(o" .8")
-Vauflz' ,8")
Vif(=" 1²)
-Vayf(e",
h(1 + 3)
2(1 3
8)3
y
Vef(xt,0")
V fx=f(x",8" ,0) (ef(=";y")
1 I
h(1 + 3)
2(1 - B)3 J
J
8
where I is the identity matrix, and
Vef(=".0" (1))
-ayflz 1²)
J
V (m ,y²)
the (Jacobian) for (Gradient Flow). This completes the proof of Proposition 4.2.
23

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
D.2. Proof of Proposition 4.3
Proof. Recall the continuous- time model for alternating heavy ball method is given by:
((t) = V (ar,yy
i(t) V [((,,)) 2(1 B)2 V v.f(2, (x11))))
(Continuous Alt-HB)
With similar calculation and the of the first-order optimality condition of local equilibrium (x",y") presented in Section D.I, the Jacobian of Continuous Alt-HB at (x*, v²) can be formulated as
h
JA Js (1 B3
V
yx V
V my
ya
(x
E. Proof of Theorem 4.6
Recall from the local convergence condition presented in Proposition 2.1, Continuous Sim-HB has local convergence if and only if maX))S)(Js) (R(A) < 0. To analyze maxxeSp(7s)) (A),, we need the following lemma about the eigenvalues of polynomial matrix.
Lemma E.1. /Graham (2018)) p(z) is polynomial and A _=xn then every eigenvalue of p(A) can be represented by P(A), where E Sp(J).
Proof. The following proof comes from (Graham, 2018). A key point here is that we are considering eigenvalues of matrices over complex number field C, and every n-degree polynomial over has roots.
Let E C be an eigenvalue p(A), and we consider the polynomial p(z) - Over the complex number field C, the polynomial p(x) - i can be factored
p(x) 1
X₂)
(62)
Moreover, since y is an eigenvalue of p(A), we have det(p(A) μT) = 0. Thus, from (62), as least one of - X, not invertible, ie., Eu E Ch, such that (A- - X,I) = 0. This implies = p(>:) and finishes the proof.
In the following, we state a corollary of Assumption 4.5, which is proved (Wang & Chizat, 2024).
Lemma E.2. [Theorem 2.1 Wang Chizat (2024)) Under Assumption 4.5, we have R(A) < 0 for every X E Sp(J).
Note that the definition of Jacobian for (Gradient Flow) in (Wang Chizat, 2024) is different from ours by minus sign. Now present the proof of Theorem 4.6.
Proof of Theorem 4.6. According to Proposition 4.2 and Lemma E.I, every eigenvalue of Jg can be represented by quadratic polynomial
h(1 + 9) 1 1-3 2(1 3)3 })3> >
(63)
where À E Sp(J) an eigenvalue of (Gradient Flow), and any number represented by (63) is an eigenvalue of Js.
Thus, ensure the local convergence of Continuous Sim-HB, we need
h11 +
>
- 3 2(1 - 3)3
1
1(1 ()
1- R((A) 2(1 2(1-8) 3)3 (B(A))-S(()))) <0, VA Sp(J).
(64)
24

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
From Lemma E.2, ((A) negative number, and from Assumption 4.4, the term R(A)² (())² in (64) is negative number. Thus, for some fixed momentum parameter and AA Sp(J), need the step size h in (64) satisfies
2(1 3)2
min AESp(T)
(65)
(1 3) (3(2)² R(A)²)
and this finishes the proof of Theorem 4.6.
F. Heavy Ball Momentum in Minimization Problems
In this section, we present the interaction between step sizes and momentum parameters of heavy ball momentum methods in minimization. We will see the phenomenon in minimization is significantly different from that in min-max games. The materials in this section are based on "O'Donoghue & Candes, 2015) and (Goh, 2017).
In minimization problems
min f(w), wERn
(Minimization)
heavy ball momentum method written as
W+++1 = We aV + B(w, - w
(Heavy Ball in Min.)
where >> 0 is the step size and B (0,1) is the momentum parameter.
Let w" be local minimum of (Minimization), and without loss of generality, assume f(w") 0. From local
viewpoint, (Minimization) can be approximated by the following quadratic problem near w":
2 w Aw b w,
where A fw=" and b Vl(""). Since A symmetric Hessian matrix local minimum point, it has eigenvalue decomposition
Q diag AI, di, An) QT.
where A <... <. An-
Proposition F.1 (O' (O'Donoghut & Candes (2015)). To make (Heavy Ball in Min.) achieve local convergence in the mini- mization problem, we need
0 < adn 28, 3 E (0,1),
and therefore larger momentim in the minimization problem allows the algorithm to achieve local convergence boarder range of step sizes.
Proof. The following proof comes from (O (O'Donoghue & Candes, 2015) and (Goh, 2017).
We introduce an intermediate variable 2₁ as 2k+1 = B2k + w.
fw))). + Then (Heavy Ball in Min.) can be written as 2k Bz4 V Vwf(wx).
Wk-1 = wk 02++1
Let 23 = QTwxx - w²) and yk = QT zk. Then the above update rule can be written as
Vi.++1 = Byr.k + AATikk
2i,4+1 = Ti affi,t+s
where viA and ya represent the i-th component of Iy and yı. respectively. These update rules can be written in matrix iteration form
yi,k
R
Vi.0
[i.k
13,0
25

---

Continuous-Times Analysis of Heavy Ball Momentum in Min-Max Games
3
A;
where R =
To make the matrix iteration converge, we need max([ai), |o2|} < 1, where and d2 are the eigenvalues R. Given this condition and the formulation of R. it turns out that we need
-a,3
ad;
0 < adn < 22 3 E (0,
In the following Figure 7, we present experiments on the dynamical behaviors heavy ball momentum in minimization. We can observe that small momentum makes the algorithm diverge while large momentum makes the algorithm converge, which supplies Proposition F.I.
(a) Dimension 200, 002.
(b) Dimension 4000, 0.01.
(c) Dimension 800, 0.006.
(d) Dimension 1000, 0.0045.
(e) Dimension = 2000, 0.0025.
(f) Dimension -2500, 0.0017..
Figure 7. Experimental results for Proposition F.1.
G. Proof of Theorem 4.8
Recall from Proposition 2.1 and Proposition 4.2, the local convergence rate of Continuous Sim-HB is determined by h(1 + 3) 2(1 - 3)3 (3(A)2 RR(A?))
max XESp(T)
R((A)
(66)
Moreover, recall that if f(x, v) satisfies Assumption 4.4 and 4.5, then from Lemma F.2, have R(A) < 0 and S())² R(A)² > 0 in (66). Now let À Sp(J), the optimal local convergence rate is achieved by momentum parameter / that satisfies the following condition:
h(1 3) R(A)
2(1 - B)3 (3(A)- }
argminsee(L.n)
{ 1 3
In the following, we will explicitly solve this question. Define function
gx (B) 1- R(A)+ + 1(1 + B)
1
2(1 - 333 (S(2)2 R(())),
and then we can calculate the derivative of (33) as:
R((A)
h (3(A)2 RR(A))) (8+2)
gx(3) (1 (1-3)² 3)2
+
(1-
26

---

Continuous-Tinn Time Analysis of Heavy Ball Momentum in Min-Max Games
Thus, have
x((3) 2 + ((A)(1- - 3)² + +h (3(22 - (B 2
(67)
Note that the right-hand side of (67) is quadratic polynomial of 8, which can be written as
Dx(3) BR)) I (3(A)²- -R(A)²) 23R()) 3 + R(A) + 2h -R())))
(68)
When 3 = 1, the above function equals to 3h (3(A)²- - R((A)), which is always positive number from Assumption 4.4, and when 3 = -1, we have
((-1))=40X4 + + (3(A)²- RR(A)))
(69)
Thus, the discussion is decomposed into two cases:
Case I, Dx(11) > 0: In this case, we can conclude that in the whole region E (-1, 1). gx(3) is an increasing function, and therefore the minimum taken at point 1. Thus, this case, the optimal convergence rate is achieved at / -1. This case corresponds to the step size taken in the region
4 R(AA) 3(A22 - R(A)2
h
and is excluded from the step size region stated in Theorem 4.8.
Case 2, Dx(11) < 0: This case covers the step size region
4 ((A) h < 3(A)2 R(A)
(70)
For fixed step size h defined in the region of (70), we denote 3(h) the corresponding momentum parameter to achieve the optimal local convergence rate for Continuous Sim-HB. Note that the function (x is a quadratic function of 3, and the coefficient of ---term is R2A), which is negative number according to Lemma E.2. Thus, this optimal ((h) should satisfy the condition:
(x()()) = 0. and 3(h) E (-1,1).
(71)
From conditions (71), Dx(1)= and Dx(-1) < 0 imply that ((h) is the smaller root of Dx. Using the roots formula of quadratic function and R(A) < O, we obtain
8(h) 29((A) - h (3)) R(A)?) + V (3(A) H((A²) - ( 48(()2 8A3R(A) (3())2 #R(A)P)
2BR(A)
(72)
=1+ h - -R(A)²) (IP R((A2)22 + (3)) R((A)²)
(73)
2(R((A)
2 (()
27

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
From (72), we have
8(h) > 0 = 2 + (3(A)2 RRAA9) V (3(A)2 RRA)S) + (3()3 R(A)3) > 0
1² (S(A)² - RR(A9)2 12RRAJA (3(A)² R((A)) (2 R((A)))2
12 (3(1)²
3R(1))) -
+M -R(()))
8h (3(1)- RR(13) < ((R(
R((A 2 (3(A22 R(A)))
h
Since ((h) is the momentum parameter that achieves the optimal local convergence rate for Continuous Sim-HB under step size h, this is exactly what we want to prove in Theorem 4.8. Thus, the step size region
R(A)I
h < 23(A) R(A}²)
makes the optimal momentum parameter 3(h) be positive number.
H. Proof of Theorem 4.9
In Section H.1, we provide some notations and lemmas that are useful in the proof of Theorem 4.9, In Section H.2, we provide the proof of Theorem 4.9.
H.1. Lemmas from first-order matrix perturbation calculation
In this section, we summarize several useful results from matrix perturbation theory, which are important for the proof of Theorem 4.9. Our main reference in this section is (Bamieh, 2020).
Let be small positive number, consider the behaviors of eigenvalues and eigenvectors of the matrix
A. Ao + cA1 C
(Perturbed Matrix)
vector i; C (w C*) is right (left) eigenvector of matrix A with eigenvalue À Cf Ac; Axu; w A A Here we use w to represent the conjugate transpose of w, i..., w" = T Given that under the Lebesgue measure on C almost all matrices over the complex number field C are diagonalizable, we can use
A1
A
(74)
An_
denote the diagonal matrix consisting of the eigenvalues of A. Moreover, we
[ei.... Un] and W =[W1, ..., wn]
to denote the matrix consisting of the right and left eigenvectors of A. As consequence, we have
AV VA and W AW".
(75)
In (Perturbed Matrix), we assume that the eigenvectors and eigenvalues are analytic functions in a neighborhood 0. We use V(e), (c), and A(e) denote the matrices consisting of the right eigenvectors, left eigenvectors, and eigenvalues
28

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
in (75) and (74). We assume (c), V(e) have asymptotic expansions
Wi(c) W/ cWi
V(e) = Vo + eVi +
and then by definition we have
(Ao + (V + +1 + ...) (Vo + +e2 + ...) (Ao + tAi +..)
(76)
(W/ + +W
+ +A1) (Ao + cλ1 + ...) (Wg +eW +...)
(77)
Moreover, given the potential for infinite number of choices for (c) and V(c), it is necessary impose constraints
these variables. A common choice is the reciprocal basis constraint, which requires that (e) = I. This constraint simplifies certain perturbation calculations. As a consequence of (*(e)V(e) = II we need the matrices Vo and W/ also satisfy the reciprocal basis constraint.
Lemma H.1 (Bamieh (2020)). Let Vo. W denote the matrices consisting of the right and left eigenvectors of Au, and assume they have been normalized according the reciprocal basis constraint, i.e., Wi Vo I. Then the diagonal matrix A1 defined in (76) and (77) can be represented by
A dg dg A.
where dg (M) represents the diagonal elements of matrix M.
From Lemma 1. to calculate the first-order eigenvalues, we need understand the left and right eigenvectors of An satisfy the reciprocal basis constraint.
H.2. Proof of the theorem
Recall from Proposition 4.3, we have
0
h JA Js
(78)
(1- B)²
V V
V yan Vv.VVoan Vayle (0*,9))
Since is small positive number, we will the term
h
(1 1 3)3
V
VVf
V yz fv zyf (x*.
in (78) as a perturbation of the matrix Js. and use the matrix perturbation theory (Bamich, 2020) calculate the eigenvalue of JA.
Denote
0
0
P
Vyz
/V
yar
my
(x*
This matrix P. will play the role of the matrix Aj in Section H.l, and the constant (1- will play the role of e. According to Lemma H.1, we have
Lemma H.2. Let AA denote the diagonal matrix consisting of the eigenvalues of JA, and Ag denote the diagonal matrix consisting of the eigenvalues of Js, then we have
h
AA = Ag (1 (1-3)2 3)2
dg (W*PV) + 0112).
Here V. W are the matrices consisting of the right and left eigenvector of Js. Moreover, they need to satisfy the reciprocal basis constraint, iee, W I.
29

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
From Lemma H.2, the problem of calculating the first-order approximation of the eigenvalues of JA is reduced to finding pair of left and right eigenvectors of Js that satisfy the reciprocal basis constraint.
Lemma H.3. Let
J =a
+
(79)
O
R
V
yx
0
(x*.a")
where aQ Vaf(a' v²) and aR Vaf(a" y"). Let v(a) and W be the right and left eigenvectors of I such that they satisfy the reciprocal basis constraint, ie., (a) V(a) = I. Then the matrices W and V in Lemma H.2 satisfy
W =" W"(,,, v V(a).
Proof. Recall from Proposition 4.2, the Jacobian matrix of Continuous Sim-HB and the Jacobian matrix of (Gradient Flow) satisfies the following quadratic polynomial relation:
I h(1 + 3) ((1-8)33
Is
T) J.
2(1 - B)3
Thus, if e is right eigenvector of J with respect eigenvalue A, then have
Jst (1 (1-
1 2(1 (1- Tu
1(1
1- (1-
1(1 + B) 2(1 3)3 >
Au.
Thus, every right eigenvector of J also a right eigenvector of Js. Similarly, one can prove every left eigenvector of J also left eigenvector of Js.
From Lemma H.3 and Lemma H.2, the problem of calculating the first-order approximation of the eigenvalues of JA is reduced finding pair of left and right eigenvectors of in (79) that satisfies the reciprocal basis constraint. In the following, we will treat the matrix J in (79) as perturbation of the matrix
V
zzy
V y
(x* w")
If Vo and Wh are the matrices consisting of the right and left eigenvectors of J, then from the asymptotic expansion (*) = We + +(a) and ((a) Vo + O(a), we have
W*(a) V(a) = W Vo + O(a) = I,
and this requires Wi V. = I as a is an arbitrary small number. Here we provide a concrete construction of Vi and Wo from the singular value decomposition of 2xf y))).
Lemma H.4. Suppose the matrix V fx" v²) is full-rank and has distinct singular values, and
V fx UEVT
is its singular value decomposition. Then the matrix
0
Vzyf("",""
V ya. (x" y²)
has distinct eigenvalues {+io;). Moreover, the right unit-norm eigenvectors of eigenvalue -io is (-iu] / / and the left unit-norm eigenvectors of eigenvalue ia, is (iu] /22, TV2)T.
/V2)T
30

---

Continuous- Time Analysis of Heavy Ball Momentum in Min-Max Games
Proof. This can be verified through direct calculation.
Tayf("", (y)
ii,//2
V (xff(x")"" ///V2
V S ,0²)
1//v2
vo (x""("""") ,²) iny! /22
- (E )?Maos) uj/v/
(80)
(E ).u.u iuj/ v2
Moreover, since V (xy ,y") UEVT is the SVD of V Vayl(x' yy", we have
1, if =is
1, if j,
0 2/ =
and u u =
0. if $
0, if +
Thus, (80) can continued calculated as
E )ouLv!) u2/
-o,u,/V2
iiy//2
--og--
En ouvuu!) iu//v2 -io,u\/V2
0/\v2
this proves /-iu//V2,0 /V2)T is an eigenvector of -ia We can prove (iu] /V2, through a similar calculation, and we omit it here.
v3 /V2) T is eigenvector of io
Lemma H.5. Denote the matrix
-ius/v2
fuj/v2
Vo= =
ins/v2
Lin///2 j=1
and W Vg- Then we have Wi Vu Izax2us and the matrices W(a) and V(a:) we are looking for in Lemma H.3 satisfies
v(a) Vo + O(a), W(a) Wo + O(a).
Proof. Since the matrices U and V come from the SVD of V fz" v²), uu and VVT are identity matrices, and this implies W3 Vo = I2nx2n- Then this lemma is a direct corollary of Lemma H.3.
Now we can calculate the eigenvalues of JA. From Lemma H.2, Lemma H.3 and H.5, we have
h
AA As
dg (WW O(a)) P. (Vo + O(a)))
(1-
wh.1 P V0.1
h
As (1 - 3)²
+ OOhh +ah).
w Up.2m
From Lemma H.4, the vectors pair (W.T. Vo.) can be chosen as
Wo.j = [in] /22 oJ//D and Ji = (-iu] (-iuu//V2,00 0/ 1///v)
where uy and by come from the singular value decomposition of V [x" (x","1) as defined in Lemma H.4.
31

---

Continuous- Time Analysis of Heavy Ball Momentum in Min-Max Games
Thus, if AA is eigenvalue of Ja, then there exists Äg E Is and pair of (uz, 0y), such that
V "xn((""2"")
-inj/v?
A = As (1- B) (in] //2, v//v2).
yyef(
iu//V2
As (1- B)² (0) vurf(x' v²) Vzuf(x" uz) + O(h² +ah).
(81)
Moreover, as defined Lemma H.4,
V 2x -4" = USVT J
is the singular value decomposition of fxy y*). Thus, the term to yyzf(es fx= vx)) vayf(a", (0)),")"")))))))"""""")))))))))) in (81) is equal Joy [2, and this gives
h R(AA) R(As) (1 3-- 30l0g1+00000 +0 + ha),
(82)
which is exactly the formula that we want to prove in Theorem 4.9.
32

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
I. Additional Experiments on Local Convergence Results
(z") local Nash equilibrium of a payoff function f(x,, y), then the local structure of f(a, y) essentially characterized by the following quadratic games:
1 1/( v²) """""""""""" -²) -xx-xx) V (x","") y²). (a V2l x²) 2
1
(Quadratic Approximation)
Since Lx",y" is a local equilibrium, from its second-order optimality condition, (=" y²) > 0 is a positive semi-definite matrix and (x""", y²) x O a negative semi-definite matrix.
In the following, we will use (Quadratic Approximation) test our theoretical results presented in Section 4. In particular, we will test these results using the discrete time algorithms Sim-HB and Alt-HB. The experimental results show that the theoretical results that we obtain from the continuous- time dynamics can precisely predict the behaviors of these discrete-time algorithms. In the following experiment, we randomly generate f=f(x" y²) ) i 0 E R=**, fzf("" "x""")""" < 0 E mR and V Vx=" y²) E R=xm, Moreover, we allow V= ","", ,y²" and [a (x", .y") to have many zero eigenvalues, so that (Quadratic Approximation) is not a SCSC function. We achieve this by randomly generating matrix A E Raxx' with n' and setting Vzf("",,') = AAT. Thus, V f2f(2" yy" produced in this way is positive semi-definite matrix with n zero cigenvalues. Similarly, can produce fif("", "ee","") negative semi-definite matrix with arbitrary number of zero eigenvalues.
L.. Experiments for Theorem 4.6 and Corollary 4.7
The aim of the experiments in this section is to show that smaller momentum can make an algorithm converge across larger range of step sizes, thus supporting the main results of Theorem 4.6 and Corollary 4.7.
Experiment 1, 20 dimension problems: In this experiment, we randomly generate /
[I",,''"" y²" > 0 E 220x20
(zf("","" < 0 R=0020, and Vayf(='.'' E 220x20 Moreover, we make each of them have 10 zero eigenvalues. The results are presented in the first row of Figure 8. From small to large, the step sizes are chosen as 0.03, 0.08 and 0.16. We can observe that smaller momentum can make the algorithm converge under larger step sizes.
Experiment 2, 200 dimension problems: In this experiment, we randomly generate (2 y²) > E 220xx0 (zf y²* x 0 E 200020 and V (x","""""") e 20000000 Moreover, we make each of them have 100 zero eigenvalues. From small to large, the step sizes are chosen as 0.005, 0.01 and 0.015. The results are presented the second row of Figure 8.
1.2. Experiments for Theorem 4.8
In this section, we present experiments on Theorem 4.9, Our aim is to show that under small step sizes, positive momentum achieve faster convergence rate compared negative momentum. The results presented in the first row of Figure 9. Compared with the experiments in I.1, choose smaller step sizes to guarantee convergence and use larger momentum to compare the convergence rates in the experiments of this section. We can observe that under these small step sizes, there exists certain algorithm with positive momentum that can achieve the best convergence rate.
Experiment 1, 20 dimension problems: In this experiment, we randomly generate V2f(x", v²) 0 E 20 Vif("",'' & 0 E R 20020 and V fzyf(=",ar "iar"""")) 20000 Moreover, we make each of them have 10 zero eigenvalues. The results are presented in the first row in Figure 9, From small to large, the step sizes are chosen as 0.003, 0.005 and 0.008.
Experiment 2, 200 dimension problems: In this experiment, we randomly generate f2 y²) > 200
(x" v²) < 0 E R 200xx00 and V fx", E 200x 200, Moreover, we make each of them have 100 zero eigenvalues. The results are presented in the first row of Figure 9. The results are presented in the second row in Figure 9. From small to large, the step sizes are chosen as 0.003, 0.005 and 0.008.
33

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
I.3. Experiments for Theorem 4.9
In this section, provide experiments to verify our theoretical results in Theorem 4.9. Our aim here is show that for games that satisfy the assumptions in Theorem 4.9, alternating updates can converge faster than simultaneous updates under the same step size and momentum parameter.
Experiment 1, 100 dimension problems: In this experiment, we present three randomly generated 100-dimensional games. For each game, we use the same step size h 0.01 and momentum parameter 3 = 0.4. The imitial conditions are randomly generated. Specifically, we use a small constant number (0.5 here) to scale the matrices V yy) and (zf("" yy" to ensure that the settings satisfy the assumptions Theorem 4.9. In the first row of Figure 10, we present the convergence curves. From these curves, we can observe that alternating updates have a faster convergence rate than simultancous updates. In the second row, present the trajectories of the first coordinate variables of the and y-players.
Experiment 2, 1000 dimension problems: In this experiment, we present three randomly generated 1000-dimensional the same step size h 0.001 and momentum parameter / 0.2. The initial conditions
games. For each game, randomly generated. As in previous experiments, we use small constant number (0.1 here) to scale the diagonal matrices to ensure that the settings satisfy the assumptions in Theorem 4.9. In the first row of Figure 11, we present the convergence curves, From these curves, we can observe that alternating updates have a faster convergence rate than simultaneous updates. In the second row, we present the trajectories of the first coordinate variables of the x- and y-players. Especially, in the second and third experiments in Figure 11 we can observe case where alternating updates can converge, while simultaneous updates diverge.
1.4. Example in Remark 4.10
Example 1.1. Let [xx y) = ax² by² + cry, where a = 2.537, b 0.0003, and 0.801. In this example, a, b, and e correspond to aQ, aR, and P in (3). There is large diagonal element Jacobian, and therefore the effect of a cannot be ignored. With choice of h = 0.4 and 0.2, the evolution of the distance equilibrium for simultaneous and alternating updates is presented in Figure 12, where we can observe simultaneous updates converge faster than alternating updates.
34

---

Continuous- Time Analysis of Heavy Ball Momentum in Min-Max Games
Figure 8. Results for experiments problems with dimension 20 (first row) and dimension 200 (sccond row). In each row, from left right, the step sizes increase from small to large.
Figure 9. Results for experiments on problems with dimension 20 (first row) and dimension 200 (second row). each row, from left to right, the step sizes increase from small to large.
35

---

Continuous- Time Analysis of Heavy Ball Momentum in Min-Max Games
Figure 10. Experimental results on problems with dimension 100 for Theorem 4.9.
Figure Experimental results on problems with dimension 1000 for Theorem
Aarrolig defi
12
0.
(a) Evolution of distances from equilibrium
(b) Evolution of trajectories
Figure 12. Illustration for Example I.1, simultaneous updates converge faster than alternating updates.
36

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
J. Additional Experiments on Implicit Gradient Regularization
J.1. Adam with negative heavy ball momentum
In Algorithm we provide details of Adam algorithm (Kingma & Ba, 2014) with negative momentum used in the GANs training experiments Section 5.2. The main difference from the standard Adam algorithm that the heavy ball momentum parameter 31 is chosen negative number here.
Algorithm I Adam with Negative 31
1: Input:
Parameters 0; Leamingg rate o;
31 < 0 (negative momentum factor; differs from classic Adam);
82 [0, 1); E (a small constant)
2: Output:
Updated parameters 0.
3: Initialize ma < 0, Vo + 0: 4-0. 0.
4: for each iteration do
5: t t 1+1
6:
(0
7:
m, + 8im-- + +11 (1- g: (Key difference: 81 can be negative.}
8:
V: - 32v1-1 + (1- 82) gi
9:
m. f m
I-3
10:
V1 1-92
11:
0, 0-1 -o++s
end for
37

---

Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
J.2. GANs training experiments
Additional results for Wasserstein GANs.
We firstly present the details of our experimental setting in Section 5.
For Figure 4(b), the experimental setting is:
Dataset: CIFAR-10.
Neural network architecture: Both generator and discriminator use the BesNet-32 architecture.
Learning rate: Both generator and discriminator use the learning rate 2e-4, with linearly decreasing step size schedule.
In each training iteration, we update both the discriminator and the generator since in this paper we mainly focus on the setting where both players have the same update steps. Standard Wasserstein GAN training suggests updating the generator every steps (Gulrajani al., 2017).
The gradient penalty coefficient is chosen 10.
In Figure 13, we present the inception scores (Salimans et al., 2016) of the GANs training experiments in the main text. higher IS indicates that the GANs have better performance. We observe that lower momentum results in higher IS. Moreover, compared with simultaneous updates, alternating updates yield higher inception scores. This is consistent with the results reported in the main text and further suggests that the implicit regularization effect is linked to the training quality. Sampled images for alternating training and simultaneous training are presented in Figure 15 and Figure 16. From these pictures, we can observe that the images generated from alternating training look better.
Inception Score
Inception Score
3006
1800
1500X
1300
25003
3000
2000
4008
8000
6908
1803
lterations
Iterations
(a) different
(b) IS, vs. alt
Figure 13. Inception Scores of Wasserstain GANs training. Smaller momentum leads larger inception score, indicating that they have better performance. Moreover, alternating updates lead to better inception score compared to simultancous updates.
38

---

Continuous- Time Analysis of Heavy Ball Momentum in Min-Max Games
Additional results for Vanilla GANs. In this section we present further results for Vanilla GANs training (Goodfellow
al., 2014). The experimental setting is follows:
Dataset: MNIST
Neural network architecture: MLP
Learning rate: Both generator and discriminator use the learning rate 0.001,
In each training iteration, update both the discriminator and the generator.
In Figure 14(a), the corresponding heavy ball momentum parameter in Adam 3 = 0.6, 0.5, 0.3, 0, -0.3, -0.5. In Figure 14(b), both the simultaneous updates and alternating updates use a momentum parameter -0.5.
From Figure 14, in min-max games. Firstly, from Figure 14(a), we can observe that smaller momentum makes the algorithms' trajectories have smaller average slopes. Secondly, from Figure 14(b), we can observe that alternating updates have smaller average slopes compared to simultaneous updates. Since the popular inception score and FID are not suitable for measuring the performance GANs training on MNIST dataset, we present some sampled images of training with alternating updates and simultaneous updates. Figure 17, we present sampled images for alternating updates. In Figure 18, we present sampled images for simultaneous updates, We can observe that alternating updates lead to better training results. Especially, in Figure 18 observe that under certain parameters, the training has already failed.
observe that the experimental results support thesis regarding the implicit regularization effects
Avaraga Stope
Auercag Stope
0
Alternttnng Update
Fs
-03
Stimu Update
Itertions
Iterations
(a) Average slope, different /
(b) Average slope,, sim vs. alt
Figure Average slope Vanilla GANs training.
39

---

Continuous- Time Analysis of Heavy Ball Momentum in Min-Max Games
Figure 15. Sampled images of Wasserstein GANs with CIFAR-10 10 dataset, trained by alternating updates.
Figure 16. Sampled images of Wasserstein GANs with CIFAR-I0 dataset, trained by simultaneous updates.
40

---

Continuous- Time Analysis of Heavy Ball Momentum in Min-Max Games
0- Spern 40
tpoch
7
9
7
&
3
0
1
1
9
0
7
3
43
7
4
7
9
5
1
7
3
6
4
5
7
9
4
8
7
1
/
9
/
7
9
3
9
4
9 g O / 1
5 9
D
3
2
9
9
3
4
7
7
3
7
7
7
3
4
4
8
4
3
/
X
7
2
9
5
3
1
7 1 8
4
7
9
8
6
6
9
7
7
7
9
7
5
3
0
6
3
8
3
5
9 2 1
4
8
3
6
9
7
8
7
9
9
7
4
7
3
8
1
7
5
7
4
4
I
6
9
/
8
d- 0.3 Spech
d-05 Eooch
A- Spoch
3
8
9 7 7
3
7
7
7
1
1
7 2
1
7
3
7
8
7.
%
4
2
4 3
3
8
7
3
0
4
4
8
1
7
/
1
7
0
0
5
0
4
8
4
3
1
5'
6
7
3
3 9
/
7
7
8
0
4
7
7
9
4
4
7
4
5
4
4
6
2
6
/
7 7
3
8
6
1
5
1
2
9
7
8
9
9
12
4 9
/
3
7
5
/
9
8
6
9
4
0
6
8
1
37
7
5
7
1
9
8 17
7
7
3
4
9 T
7
3
7
9
9
7 8
5
7
1
1 9
1
7
2 1
7 / 7
5
8
3
0
5
7
9
4
0
Figure 17. Sampled images of Vanilla GANs with MNIST dataset, trained by alternating updates.
0.5
(Epoch 40)
B
0.3 (Epoch 40)
0 (Epoch 40)
5
7
9
7
7
7
4
3
3
1
5
3
4$
1
9
2
9
!
3
4
}
4
3
1
4
/
/
/
4
1
3
I 9
9 9
4
7
5
7
1
4
7
4
4
1
4
5
5
9
1:7.5
4$
9
1
7
7
9
1
3
48
'6'
}
7
6 a
4
9
/
/
9
9
7
9 4
6
5
7
3
9
|
?
4
5
3
3
B
0.3 (Epoch 40)
B 0.5
(Epoch 40)
B
0.6 (Epoch 40)
43
?
13
8
9
8
9
G
/
9
8
3
49
9
/
1
6
4
1
9
3
3
/
5
2
99
$ 7
6
2
1
9
A
0
0
CA
?) ]
G
|
5
Z. 3
4
4
/
4
6
Q
8
Figure Sampled images of Vanilla GANs with MNIST dataset, trained by simultancous updates.


Reviews:
[{"review_id": "RL16QhxLYX", "reviewer": "Reviewer_thnv", "summary": "This paper investigates the role of Heavy Ball (HB) momentum in min-max games, an area that has been largely unexplored compared to its well-studied application in minimization. In order to analyze Heavy Ball method, the authors follow a continuous dynamics approximation of the algorithm for simultaneous & alternative version.\n\nFor **Sim-HB**, the continuous-time models are given by:\n\n$\n\\dot{x}(t) = -\\nabla_x \\mathcal{F}(x,y), \\quad \\dot{y}(t) = \\nabla_y \\mathcal{F}(x,y).\n$\n\n*(Continuous Sim-HB)*\n\n---\n\nFor **Alt-HB**, the continuous-time models are:\n\n$\n\\dot{y}(t) = \\nabla_y \\left( \\mathcal{F}(x,y) - \\frac{h}{2(1 - \\beta)^2} \\|\\nabla_x f(x,y)\\|^2 \\right),\n$\n\n$\n\\dot{x}(t) = -\\nabla_x \\mathcal{F}(x,y).\n$\n\n*(Continuous Alt-HB)*", "questions": "", "limitations": "", "rating": 2, "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": "We sincerely appreciate the reviewer's valuable comments. Regarding the concern about the practical implications of the results from continuous-time equations (CTEs), we provide a clearer explanation of the importance and relevance of continuous-time analysis:\n\n*Continuous-time analysis is a **widely accepted methodology** for analyzing optimization algorithms. It not only provides **novel insights** into the behaviors of corresponding algorithms but also proves to be **indispensable** in certain contexts.*\n\nWe now turn to a detailed discussion.\n\n>**Widely Accepted Methodology**: We list several papers that have a similar approach to our paper: rather than analyzing the original algorithms, they derive well-designed CTEs for the algorithms and analyze these equations to understand the algorithms' behavior. In minimization, these papers include [1,2,3]. In min-max games setting, papers include [4,5,6]. *Although the results in these papers only obtained rigorous proof for CTEs, they are also crucial for understanding the behavior of the original algorithms and are well accepted by the community.*\n\n>**Novel Insights**: As the reviewer noted, the results in this paper *\"reveals fundamental differences in how HB behaves in min-max games versus standard minimization problems.\"* We sincerely appreciate this observation and would like to emphasize that it is precisely the insights gained through analyzing the CTEs that lead us to discover such novel phenomena. While the reviewer comments that *\" what we have here is merely a continuous dynamical system that aligns with the observed behaviour\"*, we respectfully suggest that this alignment underscores the strength of well designed CTEs in uncovering novel insights into original algorithms.\n\n>**Indispensable**: CTEs are indispensable for studying implicit gradient regularization effects (IGRs), which is the focus of Section 5 in our paper. The foundational work in this area [7] introduced CTEs for gradient descent, demonstrating that these algorithms implicitly favor flat minima, which are referred to as IGRs. *IGRs only become apparent through the analysis of the regularization terms present in the CTEs*. Several subsequent works, including [4,8], have also relied on the same approach.\n\nWe fully agree with the reviewer's point that deriving results for the original algorithms is important, and we will list it as a future work. At the same time, we hope the above discussion demonstrates that results obtained from continuous-time analysis play a crucial role in understanding algorithmic behavior.\n\nBelow, we address additional concerns raised by the reviewer.\n\n1. *\" ...  as there is already a remark suggesting that the existing work of Gidel provides an analysis for the discrete case...\"*\n\nDue to the nature of the proof technique they adopted, the results of Gidel et al. for discrete-time algorithms are **only** applicable to bilinear games, which is a special case of the games considered in our paper.\n\n---\n\n2. *\"... momentum with a different parameter setting is, in essence, a variation of Optimistic Gradient Descent (OGD) ...\"*\n\nWe thank the reviewer for pointing out the omission of the discussion in OGD. OGD and HB methods are based on different approaches. OGD is to *\"incorporate predictions within the gradient oracle framework\"*. In contrast, the mechanism of momentum methods focuses on simulating specific physical processes [9]. These differences are also reflected by the qualitative difference of the two approaches in simple bilinear games, Sim-HB diverge while Sim-OGD converge. \n\nIn the refined version we will incorporate a detailed discussion on the differences between OGD and HB.\n\n---\n\n3. *\"...implicit regularization section, there is no clear mathematical statement ...\"*\n\nDue to the complexity of the optimization dynamics, findings in the research area of implicit gradient regularization are presented as **qualitative descriptions**. For example, in previous work [7] of this direction, the results are formulated as a *Prediction* supported by experimental results. Similarly, we state our results as a *Thesis*, and support with by experimental results.\n \nReference:\n\n[1] Kovachki & Stuart, Continuous-Time Analysis of Momentum Methods, JMLR 2020\n\n[2] Muehlebach & Jordan, Continuous-Time Lower Bounds for Gradient-based Algorithms, ICML 2020\n\n[3] Romero & Benosman, Finite-Time Convergence in Continuous-Time Optimization, ICML 2020\n\n[4] Rosca et al., Discretization Drift in Two-Player Games, ICML 2021\n\n[5] Hsieh et al., The Limits of Min-Max Optimization Algorithms: Convergence to Spurious Non-Critical Sets, ICML 2021\n\n[6] Compagnoni et al, SDEs for Minimax Optimization, AISTATS 2024\n\n[7] Barrett & Dherin, Implicit Gradient Regularization, ICLR 2021\n\n[8] Ghosh et al., Implicit Regularization in Heavy-ball Momentum Accelerated Stochastic Gradient Descent, ICLR 2023\n\n[9] Qian, On the Momentum Term in Gradient Descent Learning Algorithms, Neural Networks 1999", "claims_and_evidence": "•\tLocal Analysis: The study finds that smaller momentum improves algorithmic stability, allowing for convergence across a broader range of step sizes. Alternating updates lead to faster convergence than simultaneous updates.\n\n•\tGlobal Analysis: Smaller momentum implicitly regularizes the optimization process, guiding algorithm trajectories toward shallower slope regions of the loss landscape. Alternating updates further amplify this effect.\n\n•\tKey Insight: These findings contrast with standard minimization, where larger momentum typically improves convergence. This reveals fundamental differences in how HB behaves in min-max games versus standard minimization problems.\n\n\nOne of the primary concerns here is discerning the true value of these results and their broader significance. While this may be discussed in further detail elsewhere, it is imperative to assess what has genuinely been gained.\n\nThe first notable achievement is the avoidance of the classical second-order differential equation. The authors assert that this enhances the approximation of the error rate. However, the more critical issue is the lack of a lemma demonstrating that this analysis yields a clearer proof for the discrete algorithm. This omission is particularly striking, as there is already a remark suggesting that the existing work of Gidel provides an analysis for the discrete case. Consequently, what we have here is merely a continuous dynamical system that aligns with the observed behaviour, rather than offering an avenue to deduce insights about the discrete counterpart. The reverse approach—deriving from the continuous system a clean and direct understanding of the discrete case—would have been of far greater interest.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Exposition of theoretical claims", "relation_to_broader_scientific_literature": "Let me begin with a minor issue: I was unable to find in Bailey 2020 the claim stating that Sim-GDA cycles and does not diverge. In fact, I believe the paper explicitly asserts the opposite—that Sim-GDA diverges, and even Alt-GDA exhibits similar behavior.\n\nHowever, the more pressing concern is that momentum with a different parameter setting is, in essence, a variation of Optimistic Gradient Descent (OGD). Yet, I did not see a clear discussion on this aspect, nor any broader consideration of learning-augmented algorithms that incorporate predictions within the gradient oracle framework. This omission is particularly notable, as it leaves a key conceptual connection unexplored.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I will leave it to the area chair to determine whether this constitutes a strength or a weakness.\n\nThe paper certainly aims to discuss the benefits of the heavy-ball method through the lens of continuous dynamics, employing a modified first-order method to achieve an $h^3$ approximation. However, the most significant shortcoming is that, particularly in the implicit regularization section, there is no clear mathematical statement supporting the claims and did not show the proof-connection between discrete and continuous case.", "other_comments_or_suggestions": "The crucial issue here is to clarify which aspects of the continuous analysis can be transferred in a black-box manner to the discrete case. Without this, the practical implications of the theoretical framework remain uncertain.", "questions_for_authors": "Please respond to my concerns in the multiple sections of my review", "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": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "C9z5SKQENw", "reviewer": "Reviewer_Fszz", "summary": "This work examines the use of momentum in min-max optimization. The authors investigate both simultaneous gradient descent-ascent (GDA) --as well as it alternating form and their local convergence properties-- plus, heavy ball (HB) momentum. They show that, for simultaneous GDA + HB: \n* a positive coefficient achieves optimal convergence,\n* while the smaller the momentum coefficient, the broader the range of stable step-sizes.\n\nFor alternating GDA + HB:\n* they show that there are games with properties around a stationary point such that make alternating GDA + HB converge exponentially faster than GDA + HB.\n\nFurther, they empirically demonstrate that smaller negative momentum coefficients lead to stationary points surrounded by areas with generally smaller gradient norms. I.e., stationary points in \"flatter\" areas of the optimization landscape.\n\nFor the purpose of this study, they develop a continuous-time approximation of the heavy-ball method + simultaneous/alternating GDA. This is an approximation that tracks the trajectories of the discrete-time dynamical system by an error that is $O(h^3)$ where $h$ is the step-size.", "questions": "", "limitations": "", "rating": 4, "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": "We sincerely appreciate reviewer's valuable comments and support. Please see our itemized responses below:\n\n1. *Do you think that you could get better analysis using the framework proposed in Lu 2022?*\n\nWe thank the reviewer for highlighting the potential connection between our current paper and (Lu 2022). We will add (Lu 2022) to the **Related Works** section. We believe that exploring the possibility of combining the $\\mathcal{O}(r^s)$-resolution technique of (Lu 2022) with heavy ball momentum is a highly promising direction. This could potentially lead to continuous-time equations for heavy ball momentum in min-max games with improved accuracy. In particular, the global convergence property of the ODE proposed by (Lu 2022) would be especially interesting if it can be applied to study the heavy ball momentum algorithm, whose global convergence behavior in general min-max games remains unclear.\n\n---\n\n2. *How do you connect the flatness of saddle-points to the flatness of ERM minima in neural nets? Why do you think the GAN gets better FID scores?*\n\nWe thanks the reviewer for raising this important question. As the experiments in the current paper suggest, the superior performance of GANs trained with negative momentum is related to their implicit regularization effect. This effect guides the algorithm's trajectory to explore regions with shallower slopes in the GANs loss landscape. However, we would like to emphasize that training dynamics of min-max games exhibit subtle differences compared to ERM minima in neural networks. One notable distinction is that first-order methods are guaranteed to converge to local minima in ERM problems [1]. In contrast, for min-max games, such methods might lead the algorithms to converge to limited sets, such as cycles, rather than saddle points [2]. Therefore, we believe the relationship between the \"flatness\" of the min-max loss landscape and its machine learning applications could be more complex and multifaceted than in minimization problems. We also highlight building a solid theoretical understanding of this relationship as an important future research direction in the conclusion section of the current paper.\n\nFrom a high-level perspective, we believe that the shallower slope regions of the GANs loss landscape may represent a certain level of \"**robustness**\". In these regions, perturbations to the parameters of the generator and discriminator are less likely to significantly impact the values of their loss functions. This offers a potential explanation for why parameters from the shallower slope regions of the GANs loss landscape tend to perform better. We believe that further exploration in this area could be an interesting direction.\n\n---\n\n3. *Is there any other implication of the flatness of the minima? How would you connect it to (Ozdaglar et al 2022)?*\n\nFrom the experiments presented in the current paper, we observe that shallower slope regions in the GANs loss landscape tend to exhibit better performance when measured by FID and Inception Score. These two metrics evaluate the quality, diversity, and similarity of individual samples between generated and real data. Therefore, we believe that in the context of GANs, flatness can bring benefits in these aspects. We also believe that further exploring the implications of the flatness of the min-max loss landscape in other applications could be an intriguing area for future research.\n\nWe thank the reviewer for pointing out the literature by (Ozdaglar et al 2022). We find the metric of primal gap to study generalization of minimax algorithms purposed by (Ozdaglar et al 2022) is particularly insightful. It would be interesting to explore whether these tools could be connected to the flatness property of the loss landscapes. Additionally, we notice that the theoretical results in (Ozdaglar et al. 2022) are primarily proven for non-convex-concave or convex-concave cases, which differ from the non-convex-non-concave nature of GANs or other pratical applications of min-max games in machine learning, like adversarial training. We believe there is significant potential for further exploration in this area.\n\nReference:\n\n[1] Lee et al., First-order Methods Almost Always Avoid Saddle Points, Mathematical Programming 2019\n\n[2] Hsieh et al., The Limits of Min-Max Optimization Algorithms: Convergence to Spurious Non-Critical Sets, ICML 2021", "claims_and_evidence": "The claims in the paper are overall founded by rigorous mathematical arguments or empirical evidence. The only claim that could benefit from more extensive experimentation is how flatter saddle-points relate to better generalization. Literature has considered minimization and the loss landscapes of NN optimization but the connection to GANs or other min-max objectives would be interesting.", "methods_and_evaluation_criteria": "The methods used make sense for the problem.", "theoretical_claims": "I checked the theoretical claims and their proofs.", "experimental_designs_or_analyses": "The authors train a GAN and compare the FID metric to compare different algorithms and hyper-parameters.", "relation_to_broader_scientific_literature": "The paper relates to optimization theory and specifically min-max optimization. Prior results have have demonstrated scenarios where alternating GDA outperforms simultaneous GDA (Lee 2024).\n\nAlso, this paper hints to some similar properties as better generalization when the saddle-points are located in a generally flatter area.\n\nLee J, Cho H, Yun C. Fundamental benefit of alternating updates in minimax optimization.\nWang, J.-K., Lin, C.-H., Wibisono, A., and Hu, B. Provable acceleration of heavy ball beyond quadratics for a class of Polyak-Lojasiewicz functions when the non-convexity is averaged-out.\nWibisono, A., Tao, M., and Piliouras, G. Alternating mirror descent for constrained min-max games.\nHochreiter, S. and Schmidhuber, J., 1997. Flat minima.", "essential_references_not_discussed": "I do not think that they did not discuss some essential reference. Maybe the authors could mention Lu 2022 where they propose a general framework for continuous time ODEs.\n\nLu, H., 2022. An o (sr)-resolution ode framework for understanding discrete-time algorithms and applications to the linear convergence of minimax problems. Mathematical Programming, 194(1), pp.1061-1112.", "other_strengths_and_weaknesses": "Strengths:\n* The authors carry over an extensive investigation of the local convergence property of the algorithms.\n* They contribute a novel ODE for modelling heavy ball momentum and alternating GDA.\n\nWeaknesses:\n* The generalization claim is not discussed in an extent, although the better FID scores do demonstrate that the claim has some merit. It is interesting but elaboration is needed.", "other_comments_or_suggestions": "See strengths/weaknesses", "questions_for_authors": "* Do you think that you could get better analysis using the framework proposed in Lu 2022?\n* How do you connect the flatness of saddle-points to the flatness of ERM minima in neural nets? Why do you think the GAN gets better FID scores?\n* Is there any other implication of the flatness of the minima? How would you connect it to (Ozdaglar et al 2022)?\n\nLu, H., 2022. An o (sr)-resolution ode framework for understanding discrete-time algorithms and applications to the linear convergence of minimax problems. Mathematical Programming, 194(1), pp.1061-1112.\n\nOzdaglar, A., Pattathil, S., Zhang, J. and Zhang, K., 2022. What is a good metric to study generalization of minimax learners?. Advances in Neural Information Processing Systems, 35, pp.38190-38203.", "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": "", "extra_scores": {}}, {"review_id": "yvV8HvJ0ZX", "reviewer": "Reviewer_HBXK", "summary": "# Summary\n\nThis paper explores the role of heavy ball momentum in minmax games via ODEs. While this has been extensively studied in minimization, its effects in minmax is less understood.\n\n## Key Contributions\n\n### 1. Local Convergence Behavior\n- **Smaller momentum** improves **stability** and allows for **convergence over a wider range of step sizes**.\n- **Alternating updates** generally lead to **faster convergence** than simultaneous updates.\n- **Negative momentum** enables convergence even with larger step sizes, a clear difference w.r.t. minimization, where **positive momentum** is typically more successful.\n\n### 2. Implicit Gradient Regularization\n- The study reveals that **smaller momentum** encourages optimization trajectories to **prefer shallower slope regions** of the loss landscape.\n- Alternating updates **amplify this effect**, stabilizing minmax training.\n- This is **opposite w.r.t. what happens in minimization**, where **larger momentum** is associated with improved regularization effects.\n\n### 3. Theoretical and Empirical Validation\n- The authors derive ODEs for HB momentum with **simultaneous and alternating update schemes**.\n- They establish conditions for **local stability** and **gradient regularization effects**.\n- Numerical experiments confirm these findings.\n\n# Update After Rebuttal\n\nDear Authors,\n\nI am satisfied with your rebuttal, and I am increasing your score to **Accept (4)**: I trust that you will include the enhancements we discussed in the final version of the paper.\n\nOf course, I will follow the discussion with the other Reviewers and AC.", "questions": "", "limitations": "", "rating": 4, "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": "We sincerely appreciate reviewer's valuable comments and support.  We first respond to the suggestions on the conclusion part of the review:\n \n1. *Enhancing the figures*\n\nWe have updated figures according to your suggestions. Examples are provided through the [anonymous link](https://www.dropbox.com/scl/fi/zmwl1n9l8vpadhf3lc682/Experiments1.pdf?rlkey=8tfl0le2h954qwb0kzy2l95ol&st=cze3w60l&dl=0).\n\n---\n\n2. *Expanding the literature review*\n\nWe will add an *extended version* of the following paragraph to the **Related Works**.\n\n> **Differential Equations for Optimization.** Differential equations are powerful tools for studying optimization algorithms. In the following, we present a very brief summary, and future related works can be found in the references therein. For minimization, [1,2] purposed ODEs to investigate momentum in convex minimization. The use of SDEs for the stochastic setting was developed by [3] and future developed by [4] recently. For min-max games, [6] introduced methods for deriving high resolution ODEs to study algorithms' convergence behaviors. [5] purposed mean dynamics for Robbins–Monro algorithms to study algorithms' long-time behaviors. For the stochastic setting, recent work of [7] derived SDEs to model the behaviors of several min-max algorithms under the weak approximation framework.\n\n---\n\n3. *Experimental setup for the GANs*\n\nWe will add the following paragraph into the **Experiments on GANs training** part. \n\n>**Experimental Setup.** The experimental setup generally follows the Wasserstein GANs training framework of (Gulrajani et al., 2017). \n>\n>- Neural network architecture: Both generator and discriminator use the ResNet-32 architecture\n>\n>- Learning rate:  Both generator and discriminator use the learning rate 2e-4, with a linearly decreasing step size schedule\n>\n>- Gradient penalty coefficient: 10\n>\n>- Batch size: 64\n>\n>- During the training, We update both the generator and discriminator in each iteration, which is consistent with the algorithms investigated in this work.\n\n---\n\n4. *Experimental validation that the derived ODEs do track the respective optimizers*\n\nWe provide experiments in all the three examples provided in Figure 1 of (Compagnoni et al., 2024). Results are provided through the [anonymous link](https://www.dropbox.com/scl/fi/0uhumye9cwlwcd8kftb82/experiments2new.pdf?rlkey=v0c5vfgqgnb984xx6i0o1pogj&st=rhahpsg1&dl=0).\n\nOur continuous-time equations can accurately approximate algorithms' trajectories. For exmaple, for test function 1, trajectories of ODEs and algorithms converge to the same limit cycle. Under the step size $h =0.001$, the maximal errors are around $0.01$ after $10^{5}$ iterations. \n\n---\n\n---\n\nIn the following, we will address your concerns in the other parts of the review.\n\n5.  *It is unclear whether they used mini batching while training the GANs or not: If this is the case, the results are even stronger.*\n\nWe used the mini batching with batch size of 64 for the experimental results presented in the GANs training (Figure 4). Please refer to Question 3 for future details.\n\n---\n\n6.  *... that of SEG is very similar to that of HB ...*\n\nWe will add *extended version* of the following discussions in Section 3:\n> It is worth noting that the Hessian-gradient product type of implicit regularization terms in the ODEs for heavy ball momentum is similar to those discovered in the SDEs of Extra-gradient algorithm [7].\n\n---\n\n7. *What stopped you from tackling the stochastic setup?*\n\nWe specifically study momentum in min-max games under a deterministic setting, following the established line of research that examines momentum in minimization problems under deterministic setting [1,2]. This approach allows us to directly compare the role of momentum in min-max games with its role in minimization, thereby emphasizing their fundamentally different behaviors observed in this paper. We believe that integrating the SDE framework from [7] with our current analysis would be a promising direction for future research. We will highlight this point as a future direction in the conclusion part of this paper.\n\n\nReference:\n\n\n[1] Su et al., A differential equation for modeling Nesterov's accelerated gradient method: theory and insights, JMLR 2016\n\n[2] Wibisono et al., A variational perspective on accelerated methods in optimization, PNAS 2016\n\n[3] Li et al., Stochastic modified equations and adaptive stochastic gradient algorithms, ICML 2017\n\n[4] Compagnoni et al., Adaptive Methods through the Lens of SDEs: Theoretical Insights on the Role of Noise, ICLR 2025\n\n[5] Hsieh et al., The Limits of Min-Max Optimization Algorithms: Convergence to Spurious Non-Critical Sets, ICML 2021\n\n[6] Lu, An $\\mathcal{O}(s^r)$-resolution ODE framework for understanding discrete-time algorithms and applications to the linear convergence of minimax problems, Mathematical Programming (2022)\n\n[7] Compagnoni et al., SDEs for Minimax Optimization, AISTATS 2024", "claims_and_evidence": "While the theoretical side is sound, the experimental side needs a little enhancement.\n\nWhen deriving a continuous-time model for an optimizer, I believe it is always crucial to empirically validate that the trajectory of the ODE closely tracks that of the optimizers on a variety of problems. If this is not carefully checked, then one has less guarantee that the theoretical results derived on the ODE actually carry over to the optimizer.\n\nSimilarly to [1,2] that derived SDEs to model some optimizers, I suggest that authors plot the dynamics of the two optimizers studied here together with the trajectories of the corresponding ODEs on a two-dimensional game (see Figure 1 in [1] for example).\n\n[1] SDEs for Minimax Optimization, Compagnoni et al., AISTATS 2024.\n\n[2] Sgd in the large: Average-case analysis, asymptotics, and stepsize criticality, Paquette et al., PMLR 2021.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I only skimmed the proofs at a high level and they look ok.", "experimental_designs_or_analyses": "The experiments are meaningful and verify their insights. It is unclear whether they used mini batching while training the GANs or not: If this is the case, the results are even stronger. Otherwise, please make it clear AND consider verifying your insights while training with minibatch.", "relation_to_broader_scientific_literature": "I believe that the authors should dedicate a paragraph of the related works to the use of ODEs and SDEs in optimizations (see Related Works section in [1], which uses the weak approximation framework as well as [2] which tackles this derivation from the high dimensional perspective).\n\nIn particular, it is interesting that [3] proved that depending on the game, it might be convenient to select the extrastep of Stochastic Extra Gradient (SEG) to be negative: This somehow reminds me of the negative momentum parameter in this paper. Additionally, [3] also discusses the implicit regularization of SEG and Stochastic Hamiltonian GD: That of SEG is very similar to that of HB, and I believe this should be discussed.\n\n[1] Adaptive Methods through the Lens of SDEs: Theoretical Insights on the Role of Noise, Compagnoni et al., ICLR 2025.\n\n[2] Exact Risk Curves of signSGD in High-Dimensions: Quantifying Preconditioning and Noise-Compression Effects, Xiao et al, arXiv 2025.\n\n[3] SDEs for Minimax Optimization, Compagnoni et al., AISTATS 2024.", "essential_references_not_discussed": "As discussed above, it is more about a lack of contextualization in the literature, rather than a lack of a specific paper.\nI suggest taking a look at:\n\n1. Weak Approximation Framework: Related Works AND Additional Related Works of [1] for a comprehensive collection of papers that used CTMs to model optimizers.\n2. High-Dimensional Setting for SDEs: See [2] and related works.\n3. Related Works of [3] focuses on those papers working on CTMs for minimax optimization.", "other_strengths_and_weaknesses": "While I really enjoyed reading this well-written paper, I believe that the biggest weakness is the fact that the setup is deterministic and does not handle stochastic gradients. I am quite sure this can be addressed: If not during the rebuttal, maybe in future works. I believe this would be quite relevant because many insights derived in a deterministic setting do not carry over to the stochastic setting.", "other_comments_or_suggestions": "Based on the weaknesses highlighted above: Studying the stochastic setting is quite crucial in future work because many insights derived in the deterministic setting do not carry over to the stochastic setting. For example, it could be that the negative momentum parameter is detrimental in a stochastic setting, or something along these lines.\n\nThis could be fixed by deriving the SDEs of these methods and using Ito calculus to generalize the convergence results. \n\nRegarding the figures: Please, consider enlarging the legend, using different markers for different lines, using a colorblind palette, and so on. While they are quite illustrative, I suggest spending some more time on enhancing them. \n\n# Conclusion\n\nBased on my assessment, this paper is a **Weak Accept**, but I reserve the right to increase to (maximum) **Accept** based on the feedback from the authors and the interaction with the other reviewers and AC.\n\nNecessary conditions are:\n\n1. Enhancing the figures.\n2. Expanding the literature review w.r.t. other works using CMTs (ODEs or SDEs) for optimization, with special attention to papers using continuous time models for minimax optimization.\n3. Clarifying the experimental setup for the GANs a bit better: I do not want to read the code to figure out the experimental details. \n4. Adding some experimental validation that the derived ODEs do track the respective optimizers AT LEAST on popular two-dimensional games.", "questions_for_authors": "What stopped you from tackling the stochastic setup?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Summary: The paper studies a continuous-time analysis for HB with simultaneous and alternating update schemes in min-max games. Locally, the paper proves that a smaller momentum improves algorithmic stability by enabling local convergence across a wider range of step sizes, with alternating updates generally converging faster. Globally, a smaller momentum guides algorithms' trajectories towards shallower slope regions of the loss landscapes, with alternating updates amplifying this effect. The proposed results of the paper reveal fundamental differences between HB in min-max games and minimization, and numerical experiments further validate our theoretical results.

On reviews: The reviewers agreed that the paper is well written and has clear contributions. They highlight the extensive investigation of the local convergence property of the algorithms and the novel ODE for modelling heavy ball momentum and alternating GDA. 

Recommendation: 
I strongly advise the authors to make all agreed-upon changes in the updated version of their work, in terms of presentation and experiments. In particular,

- Enhancing the figures.
- Expanding the literature review w.r.t. other works using CMTs (ODEs or SDEs) for optimization, with special attention to papers using continuous time models for minimax optimization.
- Clarifying the experimental setup for the GANs a bit better: I do not want to read the code to figure out the experimental details.
- Adding some experimental validation that the derived ODEs do track the respective optimizers AT LEAST on popular two-dimensional games.

It would also be interesting to explore the stochastic regime in future works. 

I suggest acceptance, as I trust the authors will make the necessary updates.
Decision: Accept (poster)