When is Momentum Extragradient Optimal? A Polynomial-Based Analysis
Authors: Junhyung Lyle Kim
Gauthier Gidel
Anastasios Kyrillidis
Fabian Pedregosa
Venue: Accepted by TMLR ()

Abstract: The extragradient method has gained popularity due to its robust convergence properties for differentiable games. Unlike single-objective optimization, game dynamics involve complex interactions reflected by the eigenvalues of the game vector field's Jacobian scattered across the complex plane. This complexity can cause the simple gradient method to diverge, even for bilinear games, while the extragradient method achieves convergence. Building on the recently proven accelerated convergence of the momentum extragradient method for bilinear games \citep{azizian2020accelerating}, we use a polynomial-based analysis to identify three distinct scenarios where this method exhibits further accelerated convergence. These scenarios encompass situations where the eigenvalues reside on the (positive) real line, lie on the real line alongside complex conjugates, or exist solely as complex conjugates. Furthermore, we derive the hyperparameters for each scenario that achieve the fastest convergence rate.

Published in Transactions on Machine Learning Research (01/2024)
When is Momentum Extragradient Optimal? A Polynomial-Based Analysis
Junhyung Lyle Kim*
jlylekim Brice. edu
Rice University, Department of Computer Science
Gauthier Gidel
ggushierr.gidell&ummonntee
Université de Montréal, Department of Computer Science and Operations Research
Mila Quebec AI Institute, Canada CIFAR Al Chair
A Anstaasio Kyrillidis
anastasios@ricce.dd
Rice University, Department of Computer Science
Fabian Pedregosa
pydregosa@@gogge..com
Google DeepMind
Reviewed on OpenReview: https: http:///ppeevveeeeee net/forun id- ZL ZLVOBEuAAb
Abstract
The extragradient method has gained popularity due to its robust convergence properties for differentiable games, Unlike single-objective optimization, game dynamics involve complex interactions reflected by the cigenvalues of the game vector field's Jacobian scattered across the complex plane. This complexity can cause the simple gradient method diverge, even for bilinear games, while the extragradient method achieves convergence. Building the recently proven accelerated convergence of the momentum extragradient method for bilinear games (Azizian et al., 2020b), we use polynomial-baser analysis to identify three distinct scenarios where this method exhibits further accelerated convergence. These scenarios en- compass situations where the eigenvalues reside on the (positive) real line, lie on the real line alongside complex conjugates, or exist solely as complex conjugates. Furthermore, we derive the hyperparameters for each scenario that achieve the fastest convergence rate.
1 Introduction
While most machine learning problems are formulated as minimization problems, a growing number of works rely instead on game formulations that involve multiple players and objectives. Examples of such problems include generative adversarial networks (GANs) (Goodfellow et al., 2014), actor-critic algorithms (Pfau & Vinyals, 2016), sharpness aware minimization (Foret et al., 2021), and fine-tuning language models from human feedback (Munos et al., 2023). This increasing interest in game formulations motivates further theoretical exploration of differentiable games.
Optimizing differentiable games presents challenges absent in minimization problems due to the interplay of multiple players and objectives. Notably, the game Jacobian's eigenvalues are distributed on the complex plane, exhibiting richer dynamics compared to single-objective minimization, where the Hessian eigenvalues are restricted to the real line. Consequently, even for simple bilinear games, standard algorithms like the gradient method fail to converge (Mescheder et al., 2018; Balduzzi et al., 2018; Gidel et al, 2019).
Fortunately, the extragradient method (EG), originally introduced by Korpelevich Korpelevich (1976), offers a solution. Unlike the gradient method, FG demonstrably converges for bilinear games (Tseng, 1995). This
Authors after JLK listed in alphabetical order. This paper extends Kim al. (2022) presented the NeurIPS 2022 Optimization Machine Learning Workshop.

---

Published in Transactions on Machine Learning Research (01/2024)
has sparked extensive research analyzing EG from different perspectives, including variational inequality (Gidel et al., 2018; Gorbunov et al., 2022), stochastic (Li et al., 2021), and distributed (Liu et al., 2020; Beznosikov et al., 2021) settings.
Most existing works, inchuding those mentioned earlier, analyze EG and relevant algorithms by assuming some structure on the objectives, such as (strong) monotonicity or Lipschitaness (Solodov Svaiter, 1999; Tseng, 1995; Daskalakis & Panageas, 2018; Ryu al., 2019; Azizian et al., 2020a). Such assumptions, in the context of differentiable games, confine the distribution of the eigenvalues of the game Jacobian; for instance, strong monotonicity implies lower bound on the real part of the eigenvalues, and the Lipschitz assumption implies an upper bound on the magnitude of the cigenvalues of the Jacobian.
Building upon the limitations of prior assumptions, Azizian et al. (2020b) showed that the key factor for effectively analyzing game dynamics lies in the spectrum of the Jacobian on the complex plane. Through a polynomial-based analysis, they demonstrated that first-order methods can sometimes achieve faster rates using momentum. This is achieved by replacing the smoothness and monotonicity assumptions with more precise assumptions the distribution of the Jacobian eigenvalues, represented by simple shapes like ellipses line segments. Notably, Azizian et al. (2020b) proved that for bilinear games, the extragradient method with momentum achieves an accelerated convergence rate.
In this work, we take a different approach by asking the reverse question: for what shapes of the Jacobian spectrum does the momentun extragradient (MEG) method achieve optimal performance? This reverse analysis allows us study the behavior of MEG in specific settings depending on the hyperparameter setup, encompassing:
Minimization, where all Jacobian eigenvalues lie on the positive real line.
Regularized bilinear games, where all eigenvalues are complex conjugales.
Intermediate case, where eigenvalues are both on the real line and as complex conjugates (illustrated in Figure 1).
Our contributions can be summarized as follows:
Characterizing MEG convergence modes: We derive the residual polynomials of MFG for affine game vector fields and identify three distinct convergence modes based on hyperparameter settings. This analysis can then be applied to different cigenvaluc structures of the Jacobian (sec Theorem 3).
Optimal hyperparameters and convergence rates: For each eigenvalue structure, derive the optimal byperparameters of MEG and its (asymptotic) convergence rates. For minimization, MEG ex- " where constant improvement upon classical lower bound rate is attained,' similarly to the gradient method with momentum (GDM) with cyclical step sizes (Goujaud et al., 2022). For the other two cases involving imaginary eigenvalues, MEG exhibits accelerated convergence rates with the derived optimal hyperparameters.
hibits
Comparison with other methods. We compare MEG's convergence rales with gradient (GD), GDM, and extragradient (EG) methods. For the considered game classes, none of these methods achieve (asymp- totically) accelerated rates (Corollaries 1 and 2), unlike MEG. In Section 7, we validate our findings through numerical experiments, including scenarios with slight deviations from our initial assumptions.
2 Problem Setup and Related Work
Following Letcher et al. (2019); Balduzii et al. (2018), we define the n-player differentiable game as a family of twice continuously differentiable losses & 12d I. for i ... The player controls the parameter w : We denote the concatenated paramcters by = [w(1) ",..,,,,")) w(m] E Rd. where d = Σn d,
Note that achieving this improvement possible by having additional information beyond just the largest (smoothness) and smallest (strong convexity) rigenvalues of the Jacobian.
2

---

Published in Transactions on Machine Learning Research (01/2024)
1: 1.5, y 0.1, m 0.5
h 0.4, y 0.1, 0.5
h
0.01, 7 0.1, 0.5
1.00
10
1.00
1.00
0.98
0.8
40
0.98
0.96 g
0.96
0.96 2
Imag hary
0.94 8
mag ner
0.94
Imag Imaginrg mony
20
0.94 g:
0.92
0.92
0.92 m
0.90
0.90
-00
0.90
0.88
-5
0.88
0.88
0.86
0.86
-40
0.86
-2
0.84
-10
0.84
-60
0.84
10
Real 10
20
Real
Real
Figure Convergence rotes of MEG in terms of the game Jacobian eigenvalues. The step sizes for MEG, h and 7, and the momentun parameter distinet convergence modes of MEG. For each case, the red line indicates the robust region (c.f., Definition 1)
up according to each case of Theorem 3, illustrating three
where MEG achieves the optimal convergence rate.
For this problem, Nash equilibrium satisfies: w((" E arg miRR. (((()), wo(=()) Vi E (I.....m), where the notation ,(-4) denotes all indices except for i. We also define the vector field of the game as the concatenation of the individual gradients: v(w) = V (ww))(w)-... (wwn)n(w)] and denote its associated Jacobian with Ve.
Unfortunately, finding Nash equilibria for general games remains an intractable problem (Shoham & Leyton- Brown, 2008; Letcher et al., 2019).² Therefore, instead of directly searching for Nash equilibria, we focus on finding stationary points of the game's vector field This approach is motivated by the fact that any Nash equilibrium necessarily corresponds to stationary point of the gradient dynamics. In other words, we aim to solve the following problem: Find w² E nd such that v(w")= = 0.
(1)
Notation. R(z) and 3(2) respectively denote the real and the imaginary part of complex number z. The spectrum of matrix M is denoted by Sp(M), and its spectral radius by p(M) := max[[A] X E Sp(M)), M > denotes that M is a positive-definite matrix. C denotes the complex plane with positive real part, and R, denotes positive real numbers.
2.1 Related Work
The extragradient method, originally introduced Korpelevich (1976), is a popular algorithm for solving (unconstrained) variational inequality problems in (1) (Gidel et al., 2018). There are several works that study the convergence rate of FG for (strongly) monotone problems (Tseng, 1995; Solodov & Svaiter, 1999; Nemirovski, 2004; Monteiro & Svaiter, 2010; Mokhtari et al., 2020; Gorbunov et al., 2022). Under similar settings, stochastic variants of EG are studied in Palaniappan & Bach (2016); Hsich et al. (2019; 2020); Li et al. (2021). However, as mentioned earlier, assumptions like (strong) monotonicity or Lipcht may not accurately represent how Jacobian cigenvalues are distributed.
Instead, we make more fine-grained assumptions on these eigenvalues, obtain the optimal hyperparameters and convergence rates for MEG via polynomial-be based analysis. Such analysis dates back the development of the conjugate gradient method (Hestenes & Sticfel, 1952), and is still actively used; for instance, to derive lower bounds (Arjevani & Shamir, 2016), to develop accelerated decentralized algorithms (Berthier el al., 2020), and to analyze average-case performance (Pedregosa & Scieur, 2020; Domingo-Ennin Enrich et al., 2021).
On that end, we use the following lemma (Chihara, 2011), which clucidates the connoction between first- order methods and (residual) polynomials, when the vector field v affine. First-order methods are the ones in which the sequence of iterates w, is in the span of previous gradients: w, wo +san (ww)), .g....... r(w,,))),
2 Formulating Nash equilibrium search as nonlinear complementarity problem makes inherently difficult, classified PPAD-hard (Daskalakis al., 2009; Letcher al., 2019).
3

---

Published in Transactions on Machine Learning Research (01/2024)
Lemma 1 (Chihara (2011)). Let we be the iterate generated by first-order method ofter t iterations, with v(w) Aw + b. Then, there erists real polynomial Pt, of degree al most i, sabisfying:
--=w- = Pi(A)(wo- - ='),
(2)
where Pe(0) = 1, and v(w") )- = Aw +
By taking f2-norms, (2) further implies the following worst-case convergence rate: |/ - w01 [|Pp-
- w')l < Pr(ZAZ")]] 1uwo w"1l < sup |P(A)) - ||wo w"ll, (3)
AES*
where A = ZAZ-1 is the diagonalization of A, and the constant || disappears if A is a normal matrix. Hence, the worst-case convergence rate of a first-order method can be analyzed by studying the associated residual polynomial Pt evaluated at the eigenvalues À of the Jacobian A, distributed over the set S*
Unlocking Faster Rates Through Fine- Grained Spectral Shapes. While Azizian al. (2020b) characterized lower bounds and optimality for certain first-order methods under simple spectral shapes, we posit that more granular understanding of S could unlock even faster convergence rates. By meticulously analyzing the residual polynomials of MEG, we identify specific spectral shapes where MEG exhibits optimal performance. This approach resonates with recent advancements optimization literature (Oymak, 2021; Goujand et al., 2022), which demonstrate that knowledge beyond merely the largest and smallest eigenvalues (i.c., smoothness and strong convexity) can lead accelerated convergence convex smooth minimization.
3 Momentum Extragradient via Chebyshev Polynomials
In this section, we delve into the intricate dynamics of the momentum extragradient method (MEG) by harnessing the power of residual polynomials and Chebyshev polynomials.
MEG iterates according to the following update rule:
(MEG) Wx+1 w. hw(w, yo((:)) + m(w; wy-1),
(4)
where h is the step size, is the extrapolation step size, and m is the momentum parameter.
The extragradient method (EG), which serves as the foundation for MEG, was originally proposed by Korpelevich (1976) for saddle point problems. has garnered renewed interest due to its remarkable ability converge in certain differentiable games, such as bilinear games, where the standard gradient method falters (Gidel et al., 2019; Azizian et al., 2020b;a).
For completeness, remind the gradient method with momentum (GDM):
(GDM) We++
ho(w,) + m(w, w,-1),
(5)
from which the gradient method (GD) can be obtained by setting m = 0.
As a first-order method (Arjevani & Shamir, 2016; Azizian et al., 2020b), MEG's behavior can be elegantly analyzed through the lens of residual polynomials, as established in Lemma The following theorem unveils the specific residual polynomials associated with MEG:
Theorem (Residual polynomials of MFG and their Chebyshev representation). Consider the momentum eatrogradient method (MEG) in (4) with vector field of the form v(w) Aw + b. The residual polynomials associated with MEG can be expressed as follows:
hA(1 - 7A) and Pr+i(A) = (1 (1+m- m- hA(1 - (A) (A).11
Pa(A)= 1, A(A)=1 1
Note that almost all matrices diagonalizahle over the sense that the of non-diagonalizable matrices has Lebesgue measure zero (Hetzel al., 2007).
4

---

Published in Transactions on Machine Learning Research (01/2024)
Remarkably, these polymomials can be elegantly rewritten in terms of Chebyshev polynomials of the first and second kind, denoted by T.(.) and Ue(-); respeclively:
(.ME((A) = mm (1 ( ((((()) + I+m ())))()))) where o(A) = (o; + m hA(1 72)
(6)
2/m
The term o (A), which encapsulates the interplay between step sizes, momentum, and eigenwalues, is referred to as the link function.
The residual polynomials of MEG and GDM, intriguingly, share a similar structure but differ in their link functions. Below are the residual polynomials of GDM, expressed in Chebyshev polynomials (Pedregosa, 2020):
PCDM(A)
= (A)= =m²/2 ( (Pmm (1TT (
where E(A)
1 1+ m Ad
(7)
2 2/m
Notice that the residual polynomials of MEG in (6) and that of GDM in (7) are identical, except for the link functions (A) and E(),, which enter as arguments in T2(-) and Ut())
The differences in these link functions are paramount because the behavior of Chebyshev polynomials hinges decisively on their argument's 's domain:
Lemma (Goujaud & Pedregosa (2022)). Let 2 be a complez number, and let Ti(-) and Uz(-) be the Chebyshen polynomials of the first and second kind, respectively. The sequence { I+m T((2) 1-m Ue(2))
1+m
130
grows exponentially in t for $ [-1, while for E [-1, 1), the following bounds hold: [T{()] < and [U,(=)] 1t+1.
(8)
Therefore, to study the optimal convergence behavior of MEG, we are interested in the case where the set of step sizes and the momentum parameters lead to (o h, m)] & 1 that can use the bounds in (8). We will refer to those sets of eigenvalues and hyperparameters as the robust region, as defined below.
Definition (Robust region of MEG). Consider the MEG method in (4) expressed via Chebyshev poly- nomials, as in (6). We defone the set of eigenvalues and heperparumeterss such that the image of the link function (Ax h, 7.m) lies in the intervol [-1,1] as the robust region, and denote it with o "[-([,,
Although polynomial-based analysis requires the assumption that the vector field is affine, it captures intu- itive insights into how various algorithms behave in different settings, as we remark below.
Remark From the defivition of {(A) in (7), one can infer why negative momentum can help the con- vergence of GDM (Gidel et al., 2019) when X RQ: it forces GDM to stay within the robust region, (E(A)] & 1. One can also infer the divergence of GDM in the presence of complez eigenvalues, unless, for instance, complex momenlum is used (Lorraine el. al., 2022). Similarly, the residual polynomial of GD is ()P = (1- hAy' (Goujaud & Pedregosa, 2022, Ezample 4.2), and can easily diverge in the presence of complex eigenwalues, which can polentially be alleviated by using complex step sizes. On the contrary, thanks to the quadratic link function of MEG in (6), it can converge for much wider subsets of complex eigenvalues.
By analyzing the residual polynomials of MEG, MEG for any combination of hyperparameters, summarized in the next theorem.
also characterize the asymptotic convergence rate of
Theorem (Asymptotic convergence rate of MEG). Suppose v(w) = Aw + b. The asymptotic convergence rate of MEG in (4) is.1
Vm,
if σ < 1 (robust region);
Iww: - I+ 1100
sup to000
mm V02 - 1/2 (no convergence), otherwise,
if o
1,
1+m 2/m
(9)
w+|l
where ō = supxes= (o h 7, m)), and (1; oA) is the link function of MEG defined in (6).
*The reason why we take the 26-th root is to normalize by the number of vector field computations; we compare in Scction the asymptotic rate of MEG in (9) with other gradient methods that use single vector field computation in the recurrences, such as GD and GDM.
5

---

Published in Transactions on Machine Learning Research (01/2024)
Optimal hyperparameters for MEG that we obtain in Section 4 minimize the asymptotic convergence rate above. Note that the optimal hyperparameters vary based on the set S*, which we detail in Section 3.2.
3.1 Three Modes of the Momentum Extragradient
Within the robust region of MEG, we compute its worst-case convergence rate based on (3) follows:
(6)
sup
IMMEG
(A) & m
1/2
1-m
2m
sup XEST
[T(a()))]+
+ 1-m I+m sup [U((o(A)))) XES
xES
(8)
m
1/2
1-m
I+m (t+
m 1/2 1).
(10)
Since the Chebyshev polynomial expressions of MEG in (6) and that of GDM are identical except for the link functions, the convergence rate in (10) applies to both MEG and GDM, as long the link functions (A)] and [E(A)] are bounded by 1. As result, we see that the asymptotic convergence rate in (9) only depends on the momentum parameter m, when the hyperparameters are restricted to the robust region. This fact was utilized in tuning GDM for strongly convex quadratic minimization (Zhang & Mitliagkas, 2019).
The robust region of MEG can be described with the four extreme points below (derivation the appendix):
(-1) 24 + 4.2
(1+mm)² and o ( = + V 4-,2 bey
(11)
hry
The above four points and their intermediate values characterize the of Jacobian eigenvalues À that can be mapped to [-,, The distribution of these cigenvalues can vary in three different modes depending the selected hyperparameters of MEG, as stated in the following theorem.
Theorem 3. Consider the momenlum extragrudient method in (4), expressed with the Chebysher polynomials as in (6). Then, the robust region (c.f., Definition 1) have the following three modes:
Case 1: If h 27 > (1+ m then o (-1) and o (1) are all real numbers;
Case 2: If (1 - mm)² & h क
< (1 + vm) then o (-1) are complex, and (1) are real;
Case 3: If (1- Vm)² +, then o (-1) and o (1) are all complez reubeers
Remark 2. Theorem 3 offers guidance how to set up the hyperparameters for MEG. This depends the Jacobian spectra of the game problem being considered. For instance, if one observes only real eigenwal- ues (i.e., the problem is in fact minimization), the main slep size h should be at least 4x larger than the h. extrppolation step size 7, based on the condition क7 3 (1 + mmm
We illustrate Theorem 3 in Figure 1. We first set the hyperparameters according to each condition in Theorem 3. We then discrctize the interval [-1,1], and plot " 1]) for cach case, represented by rod lines. We can see the quadratic link function induced by MEG allows interesting eigenvalue dynamics to be mapped onto the [-1, 1] segment, such as the cross-shape observed in Case 2. Moreover, although MEG exhibits the best rates within the robust region, it does not necessarily diverge outside of it, as in the second case of Theorem 2. We illustrate the convergence region of MEG measured by V/I)(AA) < 1 from (6) for = 2000, with different colors indicating varying convergence rates, which slow down as one moves away from the robust region. Interestingly, Figure (right) shows that MEG can also converge in the absence of monotonicity (i.e., in the presence of Jacobian eigenvalues with negative real part) (Gorbunov et al., 2023).
3.2 Robust Region-Induced Problem Cases
We classify problem classes into three distinct cases based on Theorem 3, each reflecting a different mode of the robust region (Figure 2):
6 Asympptticaally GDM enjoys / convergence rate instead of the vm of MEC, it uses single vector field computation per iteration instead of the However, these are directly comparable, as the values of that correspond the robust. region are the same.
6

---

Published in Transactions on Machine Learning Research (01/2024)
Case (8)) mization
Case 2 (8,) crcss shaoec spectrum
Case 3 (8 ): sishifted imaginary spectrum
2-
Imagiaay
11
1/2
imagrory
d'
L
Imaghary
0
0
-2
22
bi -4
0
5
Roal
RD0
Real
Figure 2: Illsstatioon of the three spectrum models where MEG achieves accelerated convergence rates.
Case 1: The problem reduces to minimization, where the Jacobian eigenvalues are distributed on the (positive) real line, but as a union of two intervals. We can model such spectrum as:
Sp(Ve) Si [1,, [2] c R..
(12)
Above generalizes the Hessian spectrum that arise in minimizing p-strongly convex and L-smooth functions, i.c. A [n, L]. This spectrum be obtained from (12) by setting μ4 μ4, L2 L, and L1 M2g It was empirically observed that, during DNN training, somelimes few eigenvalues of the Hessian have significantly larger magnitudes (Papyan, 2020). In such cases, (12) can be more precise than single interval [M, L). In particular, Goujand et al. (2022) utilized (12), and showed that the GDM with alternating step sizes can achieve a (constant, factor) improvement over the traditional lower bound for strongly convex and smooth quadratic objectives.
In Section 4, show that MEG enjoys similar improvement. To show that, we define the following quantitics following Goujand et al. (2022), which will be used to obtain the convergence rate of MEG in (18) for this problem class.
L2 + M1
1
and == P2 L1
< :
E [0,
(13)
L2 MI
L2 M4
Here, Ç is the ratio between the center of Si and its radius, and = L2/ μ1 is the inverse condition number. R the relative gap of μ2 L1 and Lę - H1, which becomes if μ22 L1 (i.e., Si becomes [p1, L2]).
Case 2: In this case, the Jacobian eigenvalues are distributed both on the real line and as complex conjugates, exhibiting cross-shaped spectrum. We model this spectrum as:
Sp(Vo) S = L2 O, {(z) [-c,
(14)
The first set (p, T.] denotes segment the real line, reminiscent of the Hessian spectrum for minimizing p-strongly convex and L-smooth functions. The second set has fixed real component (d' > 0), along with imaginary components symmetric across the real line (ie., complex conjugates), as the Jacobian is real.
This is a strict generalization of the purely imaginary interval +[ai, bij commonly considered in the bilinear games literature (Liang & Stokes, 2019; Azizian et al., 2020b; Mokhtari et al., 2020). While many recent papers on bilinear games cite GANs (Goodfellow el. al., 2014) as a motivation, the work in Berard et al. (2020, Figure 4) empirically shows that the spectrum of GANs not contained in the imaginary axis; the cross-shaped spectrum model above might be closcr to some of the observed GAN spectra.
Case 3: In this case, the Jacobain eigenvalues distributed only complex conjugates, with fixed real component, exhibiting a shifted imaginary spectrum. We model this spectrum as:
Sp(Vv) C S = [c ai, c bi] U ai, bi] C C...
(15)
Again, (15) generalizes bilinear games, where the spectrum reduces to +[ai, bi] with 0.

---

Published in Transactions on Machine Learning Research (01/2024)
Examples of Cases 2 and 3 in quadratic games. To understand these spectra better, provide examples using quadratic games. Consider the following two player quadratic game, where E Rd and E 12da are the parameters controlled by each player, whose loss functions respectively are:
(1(,,)) = 2 S₁ + x M22 + x'b and (2(2, z"
S2y + y M2 + y= b2.
(16)
where Si, > O. Then, the vector field can be written as:
Six + M12y + bi]
Si M21
M12
bi by
o(z v)
M21 + S2y ba]
Aw + b, where A
S2
w
y
and
(17)
If 81 = S2 = 0 and M12 = - M2 the game Jacobian Vu A has only purely imaginary cigenvalues (Azizian et al., 2020b, Lemma 7), recovering bilinear games.
As the second and the third spectrum models in (14) and (15) generalize bilinear games, we can consider more complex quadratic games, where and S2 does not have be Specifically, when M12 M and they share common bases with S1 and S2 specified in the below proposition, then Sp(A) has cross-shaped spectrum in (14) of Case 2 and shifted imaginary spectrum in (15) of Case 3.
S1
B S2
Proposition Let be a matrix of the form assume that dim((S)) dim((S2) d. Then,
where S1, > 0. Without loss of generality, -BT
Case 2: Sp(A) has a cross-shape if there erist orthonormal matrices U, V and diagonal matrices D1, D2 such that S = U (liag(a....,444 D.) S2 = V diag(aa.....)) and B = UD2V
Case 3: Sp(A) has a shifted imaginary shape if there exist orthonormal matrices U.V and diagonal and B UD2VT.
matrix D2 such that S = U
S2 = V
We can interpret Case 3 a regularized bilinear game, where S₁ and S2 are diagonal matrices with a constant eigenvalue. This implics that the players cannot control their parameter x and y arbitrarily, which can be seen in the loss functions in (16), where S₁ and S2 appears in terms Syæ and y S2y. Case 2 can be interpreted similarly, but player (without loss of generality) has more flexibility in its parameter choice due to the additional diagonal matrix Dj in the eigenvalue decomposition of Sj.
4 Optimal Parameters and Convergence Rates
In this section, we obtain the optimal hyperparameters of MEG (in the sense that they achieve the fastest asymptotic convergence rate), for each spectrum model discussed in the previous section.
Case 1: minimization. When the condition in Case of Theorem holds (i.e., 4 > (1 + vm)?), both (-1) and =(1 (and their intermediate values), line on the real line, forming union of two intervals (see Figure 1, left). The robust region in this case, denoted Case, ([-1, 1]), is expressed as:
-1
(1+vm)² by
U
(1+vm)²
vm)? hv C R..
+
27
27
For this case, the optimal hyperparameters of MEG in terms of the worst-case asymptotic convergence rate in (9) can be set as below.
Theorem 4 (Case 1). Consider solving (1) for games where the Jacobian has the spectrum in (12). For this problem, the optimal hyperparameters for the momentum extragradient method in (4) are:
AL P and m /uaaii- -i V Vuzlity // -
4(H: +ag)
V +2
8

---

Published in Transactions on Machine Learning Research (01/2024)
Recalling (9), we immediately get the asymptotic convergence rate from Theorem 4. Further, this formula can be simplified in the ill-conditioned regime, where the inverse condition number = 11/L2 - 0:
1/2
Vm V-- R +V-
1
2 VI-R o(vF).
(18)
From (18), we see that MEG achieves an accelerated convergence rate - O(VT), which is known to be "optimal" for this function class, and can be asymptotically achieved by GDM (Polyak, 1987) (see also Theorem with 0 1). Surprisingly, this rate can be further improved by the factor vI vI- R2, exhibiting "super-acceleration" phenomenon enjoyed by GDM with (oplimal) cyclical step sizes (Goujaud el al., 2022). Note that achieving this improvement is possible by having additional information beyond just the largest (I2) and smallest (/1) cigenvalues of the Hessian.
Case 2: cross-shaped spectrum. If the condition in Case of Theorem is satisfied (i.c., (1- vm)² <
< (1 + Vm)²), then a (-1) are complex, while (1) real (c.f., Figure 1, middle). We can write the robust region of Case, (1-1, as:
(lym) by
(1+ym) by
1
(1+mm)
1
1-
27
27
CR+
CC+
Here, the first interval lies on R+, as the square root term is real; conversely, in the second interval, the square root term imaginary, with the fixed real component: 27 We summarize the optimal hyperparameters for this case in the next theorem.
Theorem 5 (Case 2). Consider solving (1) for games where the Jacobian has a cross-shaped spectrum as in (14). For this problem, the optimal haperparameters for the momentum extragradient method in (4) are:
h
16(++ L) +c*+(u++D)) L)3 AuL
P+L and m =
(1c++(p+))2+-- [1c++(u+)))+++++++ /
We get the asymptolic rate from Theorem 5, which simplifies in the ill-conditioned regime == P/L 0 as:
1/2
4pL. 4c
= 1
2VF + o(VT).
(19)
44 /4p..
V(20/1)441 T
We see that MEG achieves accelerated convergence rate 1 1 1-O(V///L as long this rate is optimal in the following sense. The lower bound for the problems with cross-shaped spectrum in (14) must be slower than the existing ones for minimizing p-strongly convex and L-smooth functions, as the former strictly more general. Since we reach the same asymptotic optimal rate, this must be optimal.
O(L). We remark that
Case 3: shifted imaginary spectrum. Lastly, the condition in Case 3 of Theorem 3 is satisfied (i.e., h < (1 - vm)?), then (-1) and o 11)(1) (and the intermediate values) are all complex conjugates (c.f.,
Figure 1, right). We can write the robust region Casse ([-1, 1)) as:
25 4.2
1t 1 + V by 27
4:2
U
U
24
V 47
m
2
4.2
1
(1+.m²
(1+
kny
mp
C C++
We modeled such spectrum in (15), which generalizes bilinear games, where the spectrum reduces to +[ai, bi] (i.c,, with == 0). We summarize the optimal hyperparameters for this case below.
Preciielyy, GDM with optimal step size and momentum asymptatically achieve 1- 2-/F-++(o convergence rate, as (Goujaud & Pedregosa, 2022, Proposition 3.3).
9

---

Published in Transactions on Machine Learning Research (01/2024)
Theorem 6 (Case 3). Consider solving (1) for games where the Jacobian has shifted imaginary spectrum in (15). For this problem, the optimal hyperyarameters for the momentum extrugradient method in (4) are:
(v 7 2e
and m V
Similarly to before, compute the asymptotic convergence rate from Theorem 4 using (9).
1/2
m Vett-va+o = -1-
(20)
Note that by setting 0, the rate in (20) matches the lower bound of bilinear game: 2020b, Proposition 5). Further, with >> 0, the convergence rate in (20) improves, highlighting the contrast between vanilla bilinear games and their regularized counterpart.
(Azizian et al.,
6+a
Remark 3. Notice that the optimal momentum m in both Theorems 5 and 6 are positive. This is in contrast to Gidel et al. (2019), where the gradient method with negative momentum is studied. This difference elucidates distinct dynamies of how momentum interacts with the gradient and the extragradient methods.
5 Comparison with Other Methods
Having established MEG's asymptotic convergence rates for various spectrum models, we now compare it with other first-order methods, including GD, GDM, and EG.
Comparison with GD and EG. Building upon the fixed-point iteration framework established by Polyak (1987), Azizian et al. (2020a) interpret both GD and EG as fixed-point iterations. Within this framework, iterates of method are generated according to:
Wh+1 = F(w)). AL N030 0,
(21)
where F Rd + Rd an operator representing the method. However, analyzing this scheme in general settings poses challenges due to the potential nonlincarity of F.
To address this, under conditions of twice differentiability of F and proximity of to the stationary point w*, the analysis can be simplified by linearizing F around wt:
F(w) R F(w*) + (w w").
Then, for Wo in a neighborhood of w", one can obtain an asymptotic convergence rate of (21) by studying the spectral radius of the Jacobian at the solution: p(VF(w*)) < p < 1. This implics that (21) locally converges linearly to w" at the rate O((p* +z)²) for E > 0. Further, F is linear, E (Polyak, 1987).
The corresponding fixed point operators FGD and FEG of GD and EG? respectively are:
(GD) W1+1 wa hv(wi) FFG((w:), and (EG) W = wi - lulww ho (w:w)) = FFG (we).
(22)
(23)
The local convergence rate can then be obtained by bounding the spectral radius of the Jacobian of the operators under certain assumptions. We summarize the relevant results below.
Theorem 7 (Azizian et al. (2020a); Gidel et al. (2019)). Let w² be stationary point v. Further, assume the eigenvalues of Ve(w") all have positive real parts. Then, denoting S* == Sp(Vu((")),,
1. For the gradient method in (22) with step size h minxes. R(1/A), it satisfies.*
p AVF (w") ))² <
min R (2) min R(A). x
(24)
XES
7 AAiizian al. (2020a) assumes that EG the step size h for both the main and the extrapolation steps. 8 Note that the spectral radius p squared, but asymptotically almost. same as yI- xf
x/2..
10

---

Published in Transactions on Machine Learning Research (01/2024)
2. For the extragradient method in (23) with step size h (4supxes- [2))=1, it satisfies: p V F ( (w )) < - minscs+ R(2)
+ 1 minars 1212 sup [X]=
(25)
sup [A]
We can determine the convergence rate of GD and EG by using Theorem 7 since all three cases of our spectrum models (12), (14), and (15) meet the condition that the eigenvalues of Ve(w*) have positive real parts. The following corollary summarizes this result.
Corollary 1.
With the condilions in Theorem 7, for each case of the Jucobian spectrum St, SA and S3, the gradient method in (22) and the extragradient method in (23) satisfy the following:
-Case 1: Vp(Vv) C Si = [Mn, L1] (u2, L2] R.: pVV ))² < 1 -
and p(VP BG (w*))² (VP""(w")))
< 1 1/
(26)
16L,
-Case 2: Vp(V C S = (0, U E R(z) = d' > 0, {22) E -c.
2p ((((1())
c 1ス
P(VF.D ( (w)))²
42/(LL-
(27)
1 5
olherwise.
+ 16(22+(1L-)22)
ff>
312 422+2L 22
PVF EG (w*) (o=)) ))²
1 $
1
H +
2²
otherwise.
T61."
Case 3: Sp(Vv) C C = |c + ai, c bi] U Ic - bi] E C+:
PVV (w))) < 22 and P(VF (w*) <1 ( 10(02462)
(Vo4o 2+a2
(28)
In Case 1, we see from (26) that both GD and FG have convergence rates O(n 11 0(p1/1a)=1-((r) 0(T). MEG. on the other hand, has an accelerated convergence rate of 1 - O(F)), as well as an additional constant improvement. by a factor of v1 - R22 as we showed in (18). Moving on to Case 2, we showed in (19) that MEG enjoys an accelerated convergence rate of (1 (/) as long as c= OL). However, both GD and EG in (27) have non-accelerated convergence under the same condition. Lastly, for Case 3, we showed (20) that MEG achieves an asymptotic rate that matches the known lower bound for bilincar games: V btta with 0; further, the rate of MEG improves if c > 0. On the contrary, GD and EG suffer from slower rates, as shown in (28).
/b-a
Comparison with GDM. We now compare the convergence rate of MEG with that of GDM, which iterates as in (5). In Azizian et al. (2020b), was shown that GD is the optimal method for games where the Jacobian cigenvalues are within a disc in the complex planc. This suggests that acceleration not possible for this type of problem. 9 On the other hand, it is well-known that GDM achieves an accelerated convergence rale for strongly-convex (quadratic) minimization, where the eigenvalues of the Hessian lie the (strictly positive) real line segment (Polyak, 1987). Hence, Azizian et al. (2020b) studies the intermediate case, where the Jacobian cigenvalues are within an ellipse, which can be thought of as the real segment ju, L) perturbed with an elliptic way. That is, they consider the spectral shape:10
K. k-= === (ZzZ4t112 + (2=) <1)
Similarly to GD and EG above, in Azizian et al. (2020b), GDM is interpreted as fixed point iteration:" !I
Wi+1
he(w:) + m(w; - w1 = F GDM (wi, wt-1).
(29)
To study the convergence rate of GDM, we use the following thcorem from Azizian et al. (2020b):
cousider the where, e-g. cross- is contained in disc. Then, by knowing more fine-grained structure of the Jacobian spectrum, MEG can have faster convergence in (19).
YYet,
A visual illustration of this cllipse be found in Azizian et al. (2020b, Figure 2).
11 As GDM updates w1+1 using both wy and wt-1, Azizian et al. (2020h) uses augmented fixed point operator; Lemma in that work for details.
11

---

Published in Transactions on Machine Learning Research (01/2024)
Theorem 8 (Azizian et al. (2020b)). Define c(u, as L)LL (m/L)² 7" min(a, b). If Sp(V (OVVFDDM(w'' (w*, ; w*)) )) C Ke, and when - 0, it satisfies:
with 0 > 0 and A
+ OF
if 8 >
p FGG ",0",,"")" &
1 - 2(V2 -
if 0 =
(30)
71-0 + +0 +0(1122-30)
if 0 < 2'
where the hyperporametes h and m are functions of μ. L, and e only.
from the above), which is always slower than the rate of MEG in (18) by the factor of vI R2. For Case 2, we see from Theorem that GDM achieves an accelerated rate, i.e., 1 O(VF), until 0 = 1 In other words, the biggest elliptic perturbation where GDM permits the accelerated rate is c vpI. We interpret Theorem 8 for games with cross-shaped Jacobian spectrum in (14) and shifted imaginary spectrum in (15) in the following corollary.
For Case 1, GDM converges at the rate 1 - -2VF + (T) (i.c., with
Corollary 2. Consider the gradient method with momentum, interpreted fized point iteration in (29). For games with cross-shaped Jacobian spectrum in (14) with c= L GDM canmol achieve an accelerated rate when 2 L-p c > c= vpL. Since L > μ. this further implies > V5. That is, when the condition number exceeds V5 = 2.236, GDM cannot achieve an accelerated convergence rate. On the contrary, as showed in (19), MEG can converge at an accelerated rate in the ill-conditioned regime.
The convergence rate of GDM for Case 3 cannot be determined from Theorem 8, as this theorem assumes the spectrum model of the real line segment [n, L.] with perturbation (along the imaginary axis), while Sj in (15) has a fixed real component. Instead, we utilize the link function of GDM in (7) to show that it is unlikely for GDM to stay in the robust region: g ([-,,_
Proposition 2. Consider solving (1) for games where the Jacobian has a shifted imaginary spectrum in (15), using the gradient method with momentum in (5). For any compler ramberr z = p + qi E C+, if 2(1+m) < then GDM cannol slay in the robust region, i.e., (E()) 1.
Note that the condition 2(1+m) < is hard to avoid even for small considering h is usually a small value.
h
6 Local Convergence for Non-affine Vector Fields
The optimal hyperparameters of MEG for each spectrum model and the associated convergence rate we obtained in Section 4 are attainable when the vector field is affine. A natural question is, then, what can we say about the convergence rate of MEG when the vector field is not affine? To that end, we provide the local convergence of MEG by restarting the momentum, as detailed below.
Let us consider the operator G representing the MFG in (4) such that:
[we+1, w/] G[(u, ([[w,,)-1)) and G(w"" w=') [w=, ,w").
In addition, we assume that w1 wo T+m v(wo ru(wo)), in order to induce the residual polynomials from Theorem 1; see also its proof and Algorithm 1 in the appendix. Now let us consider the following algorithm:
h
[Wi+++11, W G[[we+ii w(++-1l) for 1 I 1, and then
(31)
W(++))++1 = W(e+1Jk T+m o(u(4114 7o(w
In other words, we repeat MEG for & steps, and then restart the momentum at [w(-1))+1 wotyyl The local convergence of the restarted MEG is established in the next theorem.
Theorem 9 (Local convergence). Let G Id2d + R2d be the continuously differentiable operator representing the momentum extragradient method (MEG) in (4). Let w be a stationary point. Let we denote the output of MEG, which enjoys convergence rate of the form l|w, w'll C(1 - (t) + 1)llwo w" || for some
12 QbSseev that 1p/T)//2 T)/T = <(p, L.) = VOL.
12

---

Published in Transactions on Machine Learning Research (01/2024)
0 x < 1 when the vector field is offine. Further, consider restarting the momentum of MEG after running k steps, in (31). Then, for each e >> 0, there evists k >> 0 and 8 >> 0 such that, for all initializations wo satisfying |ww0- w01l 1| & 8, the restorted MEG satisfies:
||wx w01 = O(1 - + + 8) - w=11.
7 Experiments
Vp(Vu)
CXOCO
Distance to w
exact
Sp(Ve) - Inexact
Distance to w²
inexact
100
102
100
Iriggnu
10a
10"4
0-
10-1
-50
-50
10"2
10
100
-100
100)
220
1D00
1500
2300
150
5001
1000
1900
2000
Real
Number of iteraaioon
Real
Number terations
MBC toctimat
GD (meoo)
GD igrid search)
GDM search)
5G (theory)
EC (grid searcho
Illustaaioon of the game Jacobian spectra and the performance of different algoritlems considered. Jacobian spectrum in the first plot matches S in (14) precisely, while that in the third plot inexactly follows S3.- The second (fourth) plot shows the performance of different algorithms for solving quadratic games in (16) with the Jacobian spectrum following the first (third) plot.
Figure 3:
In this section, we perform numerical experiments to optimize a game when the Jacobian has cross-shaped spectrum in (14). We focus on this spectrum as it may be the most challenging case, involving both real and complex eigenvalues (c.f., Theorem 3). To test the robustness, we consider two cases where the Jacobian spectrum exactly follows St in (14), as well as the inexact case. We illustrate them in Figure 3.
We focus on two-player quadratic games, where player controls æ e Rd and player controls y E 1dd with loss functions in (16). In our setting, the corresponding vector field in (17) satisfies M12 M but St and S2 can be nonzero symmetric matrices. Further, the Jacobian Vo A has the cross-shaped cigenvalue structure in (14), with
use / 1, and L = 200. The optimum [r" y- = w* E =2200 is generated using the standard normal distribution. For simplicity, we assume = [b, by] = j0 ooT. For the algorithms, we compare GD in (22), GDM in (5), EG in (23), and MEG in (4). All algorithms are initialized with 0. We plot the experimental results in Figure 3.
-
L- (c.f., Proposition 1, Case 2). For the problem constants,
For MEG (optimal), we set the hyperparameters using Theorem 5. For GD (theory) and EG (theory), we set the hyperparameters using Thcorem 7, both for the exact and the incxact settings. For GDM (grid scarch), perform grid search of GGDM and m GDM and choose the best pest-performing ones, Theorem 8 does not give specific form for hyperparameter setup. Specifically, we consider 0.005 < GGDM & 0.015 with 10-3 increment, and 0.01 < m GDM < 0.99 with 10-2 increment. In addition, as Theorem 7 might be conservative, we conduct grid searches for GD and EG as well. For GD (grid search), we use the same setup as h GDM For FG (grid search), we use 0.001 & EG < 0.05 with 10-1 increment.
There are several remarks make. First, although the third plot in Figure does not exactly follow the spectrum model in (14), MEG still works well with the optimal hyperparameters from Theorem 5. As expected, MEG (optimal) required more iterations in the inexact case compared to the exact case. Second, compared to other algorithms, MEG (optimal) indeed exhibits a significantly faster rate of convergence, even when compared to other methods that use grid-search hyperparameler luning, supporting our theoretical findings in Section 4. Third, while EG (theory) is slower than GD (theory), which confirms Corrolary 1, EG (grid scarch) can be tuned to converge faster via grid scarch. Lastly, even though the best performance of GDM (grid search) is obtained through grid search, one can see the GD (grid search) obtains a slightly faster convergence rate than GDM (grid search), confirming Corollay 2.
13

---

Published in Transactions on Machine Learning Research (01/2024)
8 Conclusion
In the study of differentiable games, finding stationary points efficiently is crucial. This work analyzes the momentum extragradient method, revealing three distinct convergence modes dependent on the Jacobian eigenvalue distribution. Through polynomial-baset analysis, we derive optimal hyperparameters for each mode, achicving accelerated asymptotic convergence rates. We compared the obtained rates with other first- order methods and showed that the considered methods not achieve the accelerated convergence rale. Notably, our initial analysis for affine vector fields extends to guarantee local convergence rates on twice- differentiable vector fields. Numerical experiments on quadratic games validate our theoretical findings.
Acknowledgments
The authors would like to thank Fangshuo Liao, Baptiste Goujaud, Damien Scieur, Miri Son, and Giorgio Young for their useful discussions and feedback.
This work is supported by NSF FET: Small No. 1907936, NSF MIWINS CNS No. 2003137 (in collaboration with Intel), NSF CMMI No. 2037545, NSF CAREER award No. 2145629, NSF CIF No. 2008555, Rice InterDisciplinary Excellence Award (IDEA), and the Canada CIFAR AI Chairs program.
References
Yossi Arjevani and Ohad Shamir. On the iteration complexity of oblivious first-order optimization algorithms. In International Conference on Machine Learning. PMLR, 2016.
Waïss Azizian, loannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. A tight and unified analysis gradient-based methods for a whole spectrum of differentiable games. In International Conference on Arlificial Intelligence and Statislies. PMLR, 2020a.
Waiss Azizian, Damien Scieur, Toannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. Accelerating smooth games by manipulating spectral shapes. In International Conference on Artificial Intelligence and Statistics. PMLR, 2020b.
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The mechanics of n-player differentiable games. In International Conference on Machine Learning. PMIR, 2018.
Hugo Berard, Gauthier Gidel, Amjad Almahairi, Pascal Vincent, and Simon Lacoste-Julien. A closer look at the optimization landscapes of generative adversarial networks. In International Conference on Learning Representations, 2020.
Raphaäl Berthier, Francis Bach, and Pierre Gaillard. Acceleratod gossip networks of given dimension using Jacobi polynomial iterations. SIAM Journal on Mathemolics of Dala Science, 2020.
Aleksandr Beznosikov, Pavel Dvurechensky, Anastasia Koloskova, Valentin Samokhin, Sebastian U Stich, and Alexander Gasnikov. Decentralized local stochastic extra-gradient for variational inequalities. anXiv preprint ar XrX:::2006.0 08315, 2021.
Theodore S Chihara. An introduction to orthogonal polymomials. Courier Corporation, 2011.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. Advances in neural information processing systems, 31, 2018.
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash cquilibrium. SIAM Journal on Computing, 2009.
Carles Camingo-Enriche Fabian Pedregosa, and Damien Scieur. Average-case acceleration for bilincar games and normal matrices. In International Conference Learning Represenlations, 2021.
14

---

Published in Transactions on Machine Learning Research (01/2024)
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-awarre minimization for efficiently improving generalization. In International Conference on Learning Represenlations, 2021.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on gencrative adversarial networks. arXiv preprint arXiu:1802.1055) 2018.
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Simon Lacoste-Julien, and Ioannis Mitliagkas. Negative momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Stalistics. PMI.R, 2019.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, volume 27, 2014.
Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient method: O (1/k) last-iterate conver- gence for monotone variational inequalities and connections with cocoercivity. In International Conference on Artificial Intelligence and Statistics. PMLR, 2022.
Eduard Gorbunov, Adrien Taylor, Samuel Horváth, and Gauthier Gidel. Convergence of proximal point and extragrradientbaased based methods beyond monotonicity: the case of negative comonotonicity. In International Conference on Machine Learning. PMLR, 2023.
Baptiste Goujand and Fabian Pedregosa. Cyclical step-sizes, 2022. URL http://wa..iaan..ettbbo/o/////// cyclical/.
Baptiste Goujaud, Damien Scieur, Aymeric Dieuleveut, Adrien B Taylor, and Fabian Pedregosa. Super- acceleration with cyclical step-sizes. In International Conference on Artificial Intelligence and Statistics. PMLR, 2022.
Magnus R Hestenes and Eduard Stiefel. Methods of conjugate gradients for solving. Journal of research of the National Bureau of Slandards, 49(6):409, 1952.
Andrew J Hetzel, Jay Liew, and Kent E Morrison. The probability that a matrix of integers is diagonal- izable. The American Mathematical Monthly, 114(6):491-499) 2007.
Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single- call stochastic extra-gradient methods. Advances in Neural Information Processing Systems, 32, 2019.
Yu-Guan Hsieh, Franck Tutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively, up- date conservatively: Stochastic extragradient methods with variable stepsize scaling. Advonces in Newral Information Processing Systems, 33, 2020.
Junhyung Lyle Kim, Gauthier Gidel, Anastasios Kyrillidis, and Fabian Pedregosa. Momentum extragradient is optimal for games with cross-shaped spectrum. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 1976.
Peter Lancaster and Hanafi K Farahat. Norms on direct sums and tensor products. mathematics of compu- lalion, 1972.
Alistair Letcher, David Balduzzi, Sébastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. Differentiable game mechanics. The Journal of Machine Learning Research, 2019.
Chris Junchi Li, Yaodong Yu, Nicolas Loizou, Gauthier Gidel, Yi Ma, Nicolas Le Roux, and Michael I Jordan. On the convergence stochastic extragradient for bilinear games with restarted iteration averaging. arXiv preprint ar xrXi::2177.00444 2021.
15

---

Published in Transactions on Machine Learning Research (01/2024)
Tengyuan Liang and James Stokes. Interaction matters: A note non-asymptotic local convergence of generative adversarial networks. In The 22nd International Conference on Artāficial Intelligence and Statistics, pp. 907 915. PMLR, 2019.
Mingrui Liu, Wei Zhang, Youssef Mrouch, Xiaodong Cui, Jarret Ross, Tianbao Yang, and Payel Das. A docentralizod parallel algorithm for training generative adversarial nets. Advances in Neural Information Processing Systems, 2020.
Jonathan P. Lorraine, David Acuna, Paul Vicol, and David Duvenaud. Complex momentum for optimization in games. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, 2022.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for gans do actually converge? In International conference machine learning. PMLR, 2018
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil, A unified analysis of extra extra- gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics. PMLR, 2020.
Renato DC Monteiro and Benar Fux Svaiter. On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean. SIAM Journal on Optimization, 20(6):2755-2P7) 27877, 2010.
Rémi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhao- han Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Andrea Michi, et al. Nash learning from human feedback. arXiv preprint arXiv:2312. 00886, 2023.
Arkadi Nemirovski. Prox-method with rate of convergence (1/t) for variational incqualitics with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal Optimization, 2004.
Samet. Oymak. Provable super-convergence with a large cyclical learning rate. IEFF Signal Processing Letters, 28, 2021.
Balamurugan Palaniappan and Francis Bach. Stochastic variance reduction methods for saddle-point prob- lems. Advances in Neural Information Processing Systems, 2016.
Vardan Papyan. Traces of class/cross-class structure pervade deep learning spectra. The Journal of Machine Learning Research, 21, 2020.
Fabian Pedregosa. Momentum: when Chebyshev meets Chebyshev, 2020. URL http://fa.bian net/ blog/2020 20020//mmmetum//
Fabian Pedregosa and Damien Scieur. Acceleration through spectral density estimation. In Proceedings of the 37th International Conference on Machine Learning. PMLR, November 2020.
David Pfau and Oriol Vinyals. Connecting generative adversarial networks and actor-critic methods. arXiv preprint arXte:1610.01945, 2016.
Boris T Polyak. Introduction to optimization. optimization software. Inc., Publications Division, New York, 1:32, 1987.
Ernest K Ryu, Kun Yuan, and Wotao Yin. ODE analysis of stochastic gradient methods with optimism and anchoring for minimax problems. arXiv preprint arXim:1905.. 10899, 2019.
Yoav Shoham and Kevin Leyton-Brown. Multiagent systems: Algorithmic, name-theoretig and logical foun- dations. Cambridge University Press, 2008
Mikhail V Solodov and Benar Svaiter. hybrid approximate sstragradient-proxinee point algorithm using the enlargement. of maximal monotone operator. Set- Valued Analysis, 7(4):323 345, 1999.
16

---

Published in Transactions on Machine Learning Research (01/2024)
Paul Tseng. On linear convergence of iterative methods for the variational inequality problem. Journal of Compulational and Applied Mathemalics, 1995.
Jian Zhang and Ioannis Mitliagkas. Yellowfin and the art of momentum tuning. Proceedings of Machine Learning and Systems, 1, 2019.
17

---

Published in Transactions on Machine Learning Research (01/2024)
A Missing Proofs in Section 3
A.1 Proof of Lemma 1
Proof of Lemma can be found for example in Azizian et al. (2020b, Section B).
A.2 Proof of Theorem 1
To obtain the residual polynomials of MEG, W) has to be set slightly differently from the rest of the iterates, as we write in the pseudocode below:
Algorithm 1: Momentum extragradient (MEG) method
Input: Initialization wo, hyperparameters h, y, m.
Set: W1 = Wp 1+m u(wlo yy((w)))
for t 1.2.... do
Wt+1 = W/ hu(we - ro(w))) + m(w; wi-1)
end
Derivation of the first part
Proof. We want to find the residual polynomial P((A) of the extragradient with momentum (MEG) in (4).
That is, we want to find
Wr . P:(())wo - w"),
(32)
where two is the iterates generated by MEG, which is possible by Lemma 1, as MEG is a first-order method (Arjevani & Shamir, 2016; Azizian et al., 2020b). We now prove this is by induction. To do so, we will use the following properties. First, note that as we are looking for a stationary point, holds that u(w") = O. Further, as v is linear by the assumption of Lemma 1, it holds that v(w) A(w w*).
Base case. For 0, (A( is degree-zero polynomial, and hence equals Ta, which denotes the identity matrix. Thus, wo w² la(wo w*) holds true.
For completeness, we also prove when t 1. In that case, observe that MEG in proceeds as w0 I+m v(wn- - yu(wp)). Subtracting wt on both sides, we have:
h
h
W1 w
WD
w
1 o(wo yo(wo))
h
WO w
v(wa 7A(wo w=")
1 + m
h
wp
A(wo
7A(wn ww*) w²)
1 + m
h
hy A (wo w*)
Wy
A(wo w²) +
1 + m
+ m
h
by
Ia
A +
A2
(wo w²)
1 +
1 +
h
Ia
I A(La 7A4)
(w) w²)
(A) w=')
18

---

Published in Transactions on Machine Learning Research (01/2024)
Induction step. As the induction hypothesis, assume Pa satisfies (32). We want to prove this holds for + 1. We have:
Wi+1 ho(w: (w(w)) + m(w, wt-1)
www 7A(w, (er w²)) + m(we - w
W0 h.Aw w2 7A(we - w²) - w²) + m(we wi-1) h.(w: w²) + hyy 1 w²) m(w: wi-
w. hA(Ia 7A)(wr - w²) + --m(r w)-1).
Subtracting w* on both sides, we have:
W++1 w² = = w² - hA(Aa 7A) w²) m(wi w₁-1)
= -Ia--hah - 11A(1a 7A)) (we -=) + m(we - w² - (w+ w²1)
(32)
(Is hA(La -A)) Pc(A)(wo - -²) + m m(P((A)(u) - w²) P2-1(A)(wo w*))
= (Ia + -lda - hA(la - A)) P.(A)(wo w²) mPp:-1A)(uu) - -w")
Piti(A)(us)) w²),
where in the third equality, we used the induction hypothesis in (32).
Derivation of the second part in (6)
Proof. We show P. = Pe for all via induction.
Base case. For 0, by the definition of Chebyshev polynomials of the first and the second kinds, we have (A(A) (A( = 1. Thus,
Po(A) m ( 2m To(o(())
1 1 m
"h vo(o(a))) 1+ m
[+ m
2m
+
m
=1 = Po(2).
1 m
1 + m
Again, for completeness, we prove when t= as well. In that case, by the definition of Chebyshev polyno- mials of the first and the second kinds, we have Ti(A) = and (A) = 2X. Therefore,
(A = 1/2
2m
Ti (o(()))
+ 1- m Ui(o(() 1 m
I+m m
m/2
2m
o(A) +
1-m 2 o(a)
1+m m
1 m
(A)
= m/2
1 m
hA(1 - 72)
=1
P((A).
+
19

---

Published in Transactions on Machine Learning Research (01/2024)
Induction step. As the induction hypothesis, assume that Pt Pt for t. In this step, show that the same holds for 1 ++1 1.
Pt+ m
2m
1- (())(((A))
U ve
+ m
1 1+
mm(++)/22
2m
(0())I((O(A)) -T--)((())
+ m
(2(())U(((()) (()())))U--(( (0-10
+ + m
-20 1/2 1/2 m²/2
2m
Ti(o(A))
1 1-m U((((A)
I m
1
P2(A)
m m (t-1)/2
2m TT- (o-1(((())
1 m
(o
1t m
1+ m
Pt 1(A)
= - Pa(A) m P(-1(A)
1a1--hhA11100 -1(1-77))PPCM m)P--1M)
where in the second to last equality we use the induction hypothesis.
A.3 Proof of Lemma 2
Proof of Lemma can be found in Goujand & Pedregosa (2022).
A.4 Proof of Theorem 2
Proof. We first recall that using (3), we can upper bound the worst-case convergence rate as:
sup XES
IP((A)
sup XES
m²
I+m
(a()
1/2
sup [T](o
1-m sup (((((())))) I+m XES
(33)
1+m
AES*
Now, denote supxes (a h y, m))
For the first case, if < 1, both Tx(x) and U+(x) behave nicely,
per Lemma 2. Thus, have
(33)
m/
2m
+
1 (t (1+1)) & (t
-
lim (t+ $ t-000
Vm.
1 m
For the second case, we use the following expressions of Chebyshev polynomials:
x v--V"' V== + +
Vx=²
-
Tz(x)
and
2
xx+ -
I-
v
Un(x))
2 nd
Therefore, in the second case where ō 1, we have both Ta(x) and U, (x) growing at rate (x + +x2 -17 Hence, we have:
(33) & 0 m2/
00m!² (5 (B+/2(++Va)) 12+vo2-1)3
lim sup m22 (ō+ v 02 vo2- -1) ))} -Vm (5 (o+ 0 1- 1/2
t-000
20

---

Published in Transactions on Machine Learning Research (01/2024)
Finally, in order for MEG to converge in the second case, need:
mm (a+ V02 -1) '2 <1
which is equivalent to
Vm(m + +1)
m +
2m
2/m
A.5
Derivation of extreme points of robust region in (11)
We first write general formula for inverting a quadratic function. For f(x) ax² bu + C, its inverse is given by:
f(x) ax.² + her c== y
(x) -b vb2 4a(c - y)
2a
with some abuse of notation (i.e., f above is not function).
Applying the above to the link function of MEG in (6), we get
1
1
1 1+ m
2/m
o (3)
+
+
by y.
2-y
4,2
by
With this formula, we can plug in and -1 to get:
1 + 27
1
(1+ m2)
1
1
(1 - m2)
(-1)
and
σ (1)
+ V
472
br
2
412
hv
A.6 Proof of Theorem 3
Proof. We analyze each case separately.
Case 1: There are two square roots:
(1 (1-vm)" by
and V 17²
(1+ym)² by
The second one is real if:
(1 + mm)
hy
> (1 + vm)
422
172
47
which implies the first is real, as (1 + mm) > (1 - 2
Case 3: There are two square roots:
1-ymm ho
and
1
[1+mm)²
The first one is complex
4-7
477
by
mm) 2
by
< (1 - vm)
=
4
by
472
47
which implies the second is complex, as (1 + 2 > (1 2
Case 2: This case follows automatically from the above two cases.
21

---

Published in Transactions on Machine Learning Research (01/2024)
A.7 Proof of Proposition 1
Proof. Define D3 diag(a,...., a) of dimensions d x d. Let us prove that if there exists U, V orthonormal
matrices and D1, D2 matrices with non-zeros coefficients only on the diagonal such that (with slight abuse of notation)
S = Udiag(Da D3, DI)UT, , VDVV and B B-UDV
then the spectrum of A is crossed shaped. In that case, we have
DiJUT UD2VT A
-U VD&VT
T 0
[D3: Di)
D2 D3
V 0
v
- D
0
V]
Now by considering the basis W = ((U1, 0), (0, V1), (Ua,, 0), (0, Va. ), (Ud,+1, (U,,)..(UU..))) we have that A can be block diagonalized in that basis
A =
W Wdiag
(1-1De)a
[D2]u
D2ldu.du IDil.....,Pilaa, dods -du (Dilan-ddd-dd
WT.
(34)
D2ld..d.
a
Now, notice that
Sp aa - {a + bi),
(35)
since the associated characteristic polynomial of the above matrix is:
(a + = a a tbi = a
Hence, using (35) in the formulation of A in (34), have that the spectrum of A is cross-shaped.
B Missing Proofs in Section 4
B.1 Proof of Theorem 4
Proof. We write the conditions required for Theorem below:
(1
mm)
(36)
24
4-2
11y
(1 + vm)²
In.
(37)
2y
472
(1 + mm)
27
472
by
112
and
(38)
1
(1
m
n2
(39)
27
472
by
By adding (37) and (38) (or equivalently by ading (36) and (39)); we get
1
1
==
(40)
11
+
L2
#2 + L
22

---

Published in Transactions on Machine Learning Research (01/2024)
From (36), we have:
v /m) 2
+
11l
2-
472
hry
(1 vm)²
27 - 14
4-2
hry
(1 /m)
#1 (1 711)
h
(1 vmm²
(1 (m))((ur + L2)
h
(41)
11
(1 7/411
M2h2
Similarly, from (38), have:
(1 vm)
+
= 122
27
412
hyy
(1 + vmm2
1/2 [n
472
hry
2
1/2 + L1
2
112
L1
2
(1 + mm)
(42)
2
2
Combining (41) and (42), and solving for m, we gel
p2L1 2m)² 11 vm)
- (13)
V/2 - Re V ( -1
(43)
VpzLi+ VHIL2
(/22 R² + 1(2
Finally, plugging (43) back to (41), we get:
h = (1 /m) (21 + L2)
M1L2
4401 L2
PI L2
(V122 + Iij + v/1 + 1.2) 2
11L2
4(m + Iz2)
(Vi22 L + vPI + L2)
B.2 Proof of Theorem 5
Proof. We write the conditions required for Theorem 5 below:
1
1
mm)²
μ.
(44)
2-
412
hy
1
1
/m)
+
I.,
and
(45)
27
412
hy
vm)²
by
472
c.
(46)
First, by adding (44) and (45), we get:
+
= 7
(47)
4 L
23

---

Published in Transactions on Machine Learning Research (01/2024)
Plugging (47) back into (44), we have:
1
(1
mm)
/1
27
422
by
11 + T
1+ L
2
(1- 2 I.)
11
2
h
L 14
T.
2
vm) 2 (u+ + T.)
2
(1 vm) 2 + L)
+ L
P.
h
/m)² (H + L)
h
(48)
μL
Plugging (47) and (48) into (46), we have:
/
(1 /m)
1
by
472
+ vmm μll
(u+1)
2
(1 mm
2
=c c
+ v mm)² 2 u.l
11 [1+ [1+1. I,
2
4e2 + (μ + T)
e +
(1 m2
2
=
4
(1 + m
4e
+
(μ+ + L)²
(1 mm)
4ut,
(1 (m) V 4u4
(1 vm) v 4c (μ + L)2
Vmlv4e2 + +)+ L)2 4uL)
= / + (1 + 1) 44pL
m V40² + (1 + L)2 VApL
(49)
4422 (ut L)3 + AApL.
Finally, to simplify (48) further, from (49), we have:
4V/L V4c² + (11 1.3 + 44pL
vm
Hence, from (48),
16 Lx+L(
(n + L)(1 /m)²
4o L) / /nb)2
16( I.)
(50)
4L
nL
(v 46 + (u + L)2 + /4pL)²
24

---

Published in Transactions on Machine Learning Research (01/2024)
B.3 Proof of Theorem 6
Proof. We write the conditions required for (6) below:
1
1
- bi, (1 mm)²
+
(51)
27
472
loy
1
1
(1 vm)² c ai.
(52)
27
4y2
by
1
1
(1 + vm)² =c ai, and
+
(53)
2
472
hy
1
1
(1
mm) bi.
+
(54)
2y
4-2
by
First, we can see from all cases that the optimal y is
7 =
(55)
2c
(51) and (54) equivalently imply
m) hyy
= b
422
hi6² b2)
(1 v vm)² hryb²
47
2c
2c(1 + vm)
h
(56)
c² 62
Similarly, (52) and (53) imply
v mm
472 a
h?
(1
/m)
2²
a² 2
hr
472
(1 (c2 + +b²
22 2
(1 +1+ mm)
² + 12 (1 + / 20
Vm= Ve + 0
2/ + 0
(57)
V0 - B Vc +
V0
+
Plugging (57) (56), we get
2c(1 + vm)
8c
h
2 b2
(V + 12
V c 2
C Missing Proofs in Sections 5
C.1 Proof of Corollary
Proof. To compute the convergence rates of GD and EG from Theorem applicd each spectrum model in (12), (14), and (15), we need to compute minxes- R(1/X) and minxes- R()) for GD. Similarly for EG, need to compute additionally minxeA- [A], minxes. AAP2 and suPXea 1
25

---

Published in Transactions on Machine Learning Research (01/2024)
Case 1: It's straightforward to compute
min (R1/A) = 1/12, A
and
min R(A) na xEs;
Thus, GD for Case
has the rate
M4
T.
L2
For EG, it's also simple to obtain
min
|| L2,
minl
|A|2
and
sup AES;
SES
XESi
Thus, EG for Case 1 has the rate
2
41
4
L
16
L
Case 2: For complex number = qi E C, we compute R(122) as:
p- qi p² qa
p² +
p²
p² q2
The lour extreme points of the cross-shaped spectrum model in (14) are:
L r 1 ci.
# = Oi, == Oi, and
Hence, R(1/2) for each of the above points is:
1
9
11
112
1
1
R
and
L
1
L'
L-
H
2
L-p + ci
2
T-
+ c²
2( - 11)
2 + (L -1)²
Therefore, minxes; Ri (+)) +. As p < L, we only need to compare the last two values. Observe that::
L2 11
46 (L - (L + 11)
46 > (T 11) - (T. 11)2
1
2 - 11)
i > 46 (L 11)2
Therefore,
1
2(L-H) 1)) 12+(L-1)
if 12-
min R
xES;
otherwise.
26

---

Published in Transactions on Machine Learning Research (01/2024)
For minxes; R(A), it's straightforward from the definition that
min XES
R(A) =
Thus, GD for Case has the rate
2p(L-n) +LL-1))
if C> L2
otherwise.
Similarly for EG, we need to compute minxes; R(), which was computed above; additionally, we need to compute minxes; [Al, minxes; [a|2, and supxes; [Ap.. For = p C, |||=
p2 + 9². Hence, we have
L - p 2
L - p 2
1l 1 0il== =M, 0i| L, and
02 +
Observe that:
3L2 + +2L 112
C
L 2L + 12
c² >> L
4
2
²² +
1
> 1
Thus, for supxes; [A], we have
62 +
L-μ ?
if C> 3L242LH-
sup |^|
=
AES;
L
otherwise,
from which supxes; 2 can also be obtained. Lastly, minxes; 2x/2 = n2 as we know < L, and (L p)/2 is the center of [M, L].
Combining all three, we get the rate of FG for Case 3 is
"² if
31 322
10(2++(72)4))
i + I61
otherwise.
Case 3: Since (15) has fixed real component, minxes; R(A) =c For minxes; R(1/A) compute compare
1
R
D4
c ai c² 0
c +
c bi
since from (15). Thus, GD for Case has the rate
c 122
For EG, it's also simple to obtain
min
| = V +2,
min XES;
|사| 2² + a² and
|2| = c² + 62. xES;
sup
XES;
Thus, EG has the rate
1
1 (c + a²)
+
4
V
+ 11
16 (c 12)
27

---

Published in Transactions on Machine Learning Research (01/2024)
C.2 Proof of Corollary 2
Proof. Per Theorem 8, the largest that permits acceleration for GDM i VLl. Therefore, in the special case of (14) we consider, i.e., when I- GDM cannot achieve acceleration if L- > vuL. Hence, we have:
2
2
L P1 > VuL
2
L 4 > 2VpL
L + 1²² > 6pp > up² (. L p))
L > v5μ.
C.3 Proof of Proposition
Proof- For arbitrary complex number qi with 0, and using the link function of GDM from (7);
have
[(p qi)l -
m hppp
hy
2
+
<
2/m
2 m
(1 + hppp² + h2-92
<
4m
(1 + m - hppp2 + h2²2² < 4m
(1 - m)² + hp(hp 2(1 + m)) + l1²1²² <0
(1 m)² 2 + h2q²
2(1 + m) hp
hp
Notice that the LHS is positive. Therefore, if the RHS is negative, the above incquality cannot hold. In other words, if 2(1+m) p, GDM cannot stay in the robust region. This is very hard to satisfy, even with small
D Missing Proofs in Section 6
Let us consider an affine vector field v(w) Aw + b and its associated augmented MEG linear operator J:
Wi+1 w²' Wr w² Wr-1 w*
Wi w²
with J (1 + Ba
-hA(Ta 7A)
-BTa 0a
(58)
La
where La and 0g respectively stand for the identity and the null matrices. To show the local convergence of (restarted) MEG for non-affine vector fields in Theorem 9, we first establish the following lemma, which connects the augmented state and the non-angmented one.
Lemma 3. Let PMEG be the residual polynomial associated with updates of MEG (c.f., Theorem 1). Let J be defined (58). If w1 wo I+m v(wo (o(w))), we then have
n [w w*1 Wo w"
(.M. (A) w²) (OMEG(())(r w²)
(59)
Consequently, if denote 2411 [we+1, wi]
and = [w* w have
| 2.1l & C(1 + 1)(1 =1 -2al-
(60)
28

---

Published in Transactions on Machine Learning Research (01/2024)
Proof. Let us express Jr such that
J (A) (A)] Pp (A) P(a and
J [w] w²
(A) w²) + P.l (A) w*) P? (A)(wo w²) + P? (A)(wu w*)
(61)
wo w²
By writing J = JJ and using the block-matrix form of J in (58), we get that for any 1 > 0,
P+ (A) ((1 3)Ta hA(Ia PH (A) 3P
Pit (A) (A)
(62)
Pit (A) = -(11 + (11+8)Ia+ - hh(Ta - (A)) - 3P7
Pft (A) (A).
(63)
Hence, we have that,
P411 (A) (62)
((1 +1++ B)T hA(Ta - pA (A) - (P
(64)
(A)
(63)
((1+ 3)4a - -hAlla - -7))) - (A)
(65)
We claim that
P! + (A) (MMB((A) for all 1>
(66)
We prove this via induction.
For the base case, using the fact that wh w/g 1+m (wo vo(w))), we have that
(P + (A) - w²) = w1 - w² = =(1 A (la - 7A)) w²) = P. PMEE (A) (wn =w),
La(wo w²) P.E (A)(wD w²). (P (A) + P) - w²) (PP (A) + p? (A))(( w²)
To show the induction step, by adding (64) and (65), we get.
P4 (A) + ( = ((1 + B) hA(la (P) (A) + (A)) ((P/ P,1
(66) ((1 + 8) - hA(la (aa((a->Aii) 7 P.) (A) - 3PMEG (A),
where in the last step we used the induction hypothesis. lent-hand side.
Also notice PM (A) Pit (A)
PMMG the
Hence we have for any t t 0,
(A) + P.!((A) w²) P.MGG()
(A)(wo w²).
(67)
Therfore, going back to (61), we have:
Wi+1 w²
W1 w"
(PP + (A)) -w w-)
= jt
W: - w²
W0 w*
(A) + (A)) -
(G3)
(P. (A4 w*)
(?) -w))
(66)
PMEG) w²) ) PMEG (A)(wo w*)
PMEG (A)(wo w*)
Thm.
PMEG (A)(w-1 w²)
MMG (A)
0 PMBG (A)
Wu w
O
w-1 w
PMG (A) & Tz
Wi w
w-1
w
29

---

Published in Transactions on Machine Learning Research (01/2024)
where we use the convention that w-11 Finally, using the fact that ||@ B || for éz-operator norm (Tancaster & Farahat, 1972), we have
(10)
Fz41 z. < || (A)Ill= 2.ll < C((+1)(11 - -
D.1 Proof of Theorem 9
Proof. We first recall the restarted MEG algorithm we consider in (31):
[1++++1: W = G[[wi++ w(x+--1l) for 1 1 1, and then
h T+m u( (((((+1))))
((+1))++1 = W(++1jk
In other words, repeat MEG for steps, and then re-start the momentum at [wa+ W 11++
We can analyze this method as follows, where we denote 2n == [w,, w[-1] and z, [w*, w
|=(+1] z.
(2(s) 2+
(68)
(Exx) - -2.)1l
(2.) 2=)1l [I (2(() 2x)1
(60)
C(k + 1)(1 - k0)* 1| - 2.11 + ||VG ( (2+ 2=)
where in the second line we use the Mean Value Theorem:
32e E [Eeke z=] such that (zu) = (z.) + (G -2a) 2
=z. =Z++VG() (C (Zik 2.) (since z. is the fixed point). (68)
In the fourth line we used the fact that (z.) - 24) exactly correspond to k updates of MEG when the vector field is affine, as well as Lemma to account for the augmented state.
Now let us consider > and large enough such that C(k + 1)(1 - 50 < - 4 + 5) Since VG is assumedd to continuous, (G() is continuous too. Therefore, there exists > such that ||
2. <
implies (|VG()) - (k) (2+) < e'. In particular, choose E' = (1 - 4 + z) (1 - to + = 2(1-p)
Then, we have
|| - 2x < C(k 1)(1 - 5)*h - 2. + [I (2ex) - ( 2+11
(1 4 + ||<k =.1l + 2.11
(1 + 5) | 2+11 < || - 2 < 1120 2-11-
From the above, we can conclude that for all s > 0, there exists k > 0 and such that, for all initialization satisfying |lwo w" || & 5, the restarted MEG described above satisfies:
| w1 = O(11 - - + - w*1l.
30


Reviews:
[{"review_id": "Offl2hHyXy", "reviewer": "Reviewer_4b8x", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Motivation and contribution are well explained.\n- The research topic of this paper, convergence analysis of dynamics for games, would be of interest to ML communities.\n- The paper contains practical results, such as guidelines for optimal parameter settings.\n\nWeaknesses:\n\n- The main results of this paper are natural extensions of the results by Azizian et al. (2020a, 2020b) and do not appear to be a major breakthrough.\n- It was not clear to me that the main theoretical results regarding convergence rates (Theorems 1 and 2) were applicable to the general games with non-affine vector fields.\n\nReference:\n- Waïss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. A tight and unified analysis\nof gradient-based methods for a whole spectrum of differentiable games. In International Conference on\nArtificial Intelligence and Statistics, pp. 2863–2873. PMLR, 2020a.\n- Waïss Azizian, Damien Scieur, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. Accelerating\nsmooth games by manipulating spectral shapes. In International Conference on Artificial Intelligence and\nStatistics, pp. 1705–1715. PMLR, 2020b", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper analyzes the momentum extragradient (MEG) method for differentiable games using residual polynomial.\nIt is shown that the convergence rate of the MAG can be characterized by the residual polynomial (Theorem 1),\nunder the assumption that the vector field is given by an affine function.\nBased on this theorem,\nthe paper provides sufficient conditions for convergence and a guide to setting optimal parameters.\nThe usefulness of this analysis is confirmed by numerical experiments as well.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- It would be better to mention to what extent the analytical results given for an affine problem (Theorems 1 and 2) can be extended to non-affine problems. Even if there is no clear theoretical argument and the application to non-affine settings is heuristics, that in itself is fine in my opinion. However, in that case, I think it is necessary to clarify that it is heuristics.\n- I would prefer to see a clear statement of how this paper defines \"optimal parameters\" before theorems on optimal parameters given in Section 4.\n- There are several places (e.g., (12), (14) and (15), ...) where the symbol of $\\in$ is used in the sense of inclusion, i.e., in situations where the symbols $\\subset$ or $\\subseteq$ would normally be used. I would appreciate it if you could check them.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nDECD48omz", "reviewer": "Reviewer_uZGK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) The problem considered here is important and the authors have made a significant contribution in this work. \n2) The paper is easy to read and follow. The mathematical explanations are quite easy to follow as well. \n3) The 3 case convergence analysis based on the spectra of the game Jacobian is rigorous. I did not find any mistakes in the derivation. \n\nWeakness:\n1) In my opinion, the assumption of the game vector field to be an affine function is too restrictive which makes this analysis valid for only quadratic games. I did not see the authors commenting about this in a more general setting where the game vector field is not affine and the polynomial based analysis will no longer be valid. \n\n2) Is it possible to extend the setup of the experiments to explore beyond quadratic games and analyze the convergence of these 4 methods (GD,EG,MEG,GDM)?\n\n3) Can the authors comment on how the convergence is affected with stochasticity in the gradients with all these cases? Currently only the deterministic setting is considered. \n\n4) Although EG methods are known to perform better than GD, the use of finite small step-size has an implicit effect of discretization drift [1] , where the implicit regularization is exactly the norm of the gradient. Infact applying a first order taylor expansion on the extra-gradient term would also have this term ( the norm of the gradient). In this context, how important is having the explicit regularization (as extra gradient term) compare with the implcit regularization due to the finite step size? Morevoer, in this context, implicit regularization for momentum (due to finite step-size and momentum parameter) is already explored in [2] and whether this can be compared with MEG (momentum extragradient). \n\n\n[1] Rosca, Mihaela C., et al. \"Discretization drift in two-player games.\" International Conference on Machine Learning. PMLR, 2021.\n\n\n[2] Ghosh, Avrajit, et al. \"Implicit regularization in Heavy-ball momentum accelerated stochastic gradient descent.\" The Eleventh International Conference on Learning Representations. 2022.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work, the authors demonstrate the benefit of momentum extragradient (MEG) in terms of convergence for bilinear games over gradient descent (GD), extragradient (EG) and GDM (Gradient descent with momentum) methods. The authors assume the game vector field to be an affine function and analyses the convergence of these algorithms in 3 sub-cases where the game Jacobian takes only 1) real eigenvalues, 2) cross spectrum and 3) shifted imaginary spectrum. They showcase the accelaration of MEG by considering the optimal hyperparameters (step-size, extragradient parameter and momentum parameter) that result in the best convergence.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to see some comments on the 4 weakness points i mentioned. For point 4, the implicit regualrization won't affect convergence on a quadratic games but can have a different effect for more complex games. \n\nI feel addressing point number 1 and 2 are critical in securing my recommendation for acceptance.", "broader_impact_concerns": "No ethical concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "USJY2r43z4", "reviewer": "Reviewer_h1nW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I will be very brief because I do not have huge expertise in the extra gradient method. In general, I think that the work is solid and considered an interesting problem. The authors carefully explored different spectrum regimes when MEG converges and outperforms GD and EG. \n\nSome weaknesses:\n1. As far as I understand, the whole provided theory only works with *affine functions*. The authors should more clearly emphasize it in the abstract and in the introduction. \n2. Moreover, the authors show that MEG enjoys acceleration in Theorem 4 and compare this result to GDM. While I agree with this result, I think that this comparison is not fair because GDM can obtain acceleration even with *non-affine gradients*. I believe that this should be explained. The same comment should be addressed when the authors compare MEG with other previous methods.\n\nI think the paper is good and deserves acceptance, but the authors should more clearly explain that they consider the setup where the objective is an *affine function*.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider the extra gradient method with momentum (MEG). They investigate how the spectrum of a Jacobian has an effect on the method. A detailed analysis and the choice of hyperparameters to get acceleration are provided.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "-", "broader_impact_concerns": "-", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The primary concerns raised by the reviewers were (i) the difference from the previous result [Azizian et al. (2020a, 2020b)] and (ii) the restriction of the problem that assumes the affine vector field. The authors have addressed these concerns well in the rebuttal and the revision. Specifically, the authors clearly described the originality of the work and extended the theory into the non-affine case with the local convergence analysis. Therefore, the paper meets the acceptance criteria.
Decision: Accept (poster)