Local convergence of simultaneous min-max algorithms to differential equilibrium on Riemannian manifold
Authors: Sixin Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: min-max algorithm
differential game
Riemannian manifold
Wasserstein GAN
Primary area: optimization

Abstract: We study min-max algorithms to solve zero-sum differential games on
Riemannian manifold.
Based on the notions of
differential Stackelberg equilibrium
and differential Nash equilibrium on Riemannian manifold,
we analyze the local convergence of 
two representative deterministic simultaneous algorithms $\tau$-GDA and $\tau$-SGA
to such equilibria.
Sufficient conditions are obtained to establish the linear convergence rate
of $\tau$-GDA based on the Ostrowski theorem on manifold and spectral analysis. 
To avoid strong rotational dynamics in $\tau$-GDA, 
$\tau$-SGA is extended from
the symplectic gradient-adjustment method in Euclidean space.
We analyze an 
asymptotic approximation of $\tau$-SGA 
when the learning rate ratio $\tau$ is big. 
In some cases, it can achieve a faster convergence rate 
to differential Stackelberg equilibrium compared to $\tau$-GDA. 
We show numerically how the insights obtained from the
convergence analysis may improve
the training of orthogonal Wasserstein GANs using 
stochastic $\tau$-GDA and $\tau$-SGA on simple benchmarks.

Published as a conference paper at ICLR 2025
LOCAL CONVERGENCE OF SIMULTANEOUS MIN-MAX ALGORITHMS TO DIFFERENTIAL EQUILIBRIUM ON RIE-
MANNIAN MANIFOLD
Sixin Zhang
Université de Toulouse. INP, IRIT rue Camichel, BP 7122, 31071 Toulouse Cedex 7, France sixin. zhang@irit....
ABSTRACT
We study min-max algorithms to solve zero-sum differential games on Riemannian manifold. Based on the notions of differential Stackelberg equilibrium and differen- tial Nash equilibrium on Riemannian manifold, we analyze the local convergence of two representative deterministic simultaneous algorithms r-GDA and 7-SGA such equilibria. Sufficient conditions are obtained to establish the linear conver- gence rate of 7-GDA based on the Ostrowski theorem on manifold and spectral analysis. To avoid strong rotational dynamics in r-GDA, 7-SGA is extended from the symplectic
method in Euclidean space. We analyze an asymptotic approximation of r-SGA when the learning rate ratio T is big. In some cases, it can achieve a faster convergence rate differential Stackelberg equilibrium compared to 7-GDA. We show numerically how the insights obtained from the convergence analysis may improve the training of orthogonal Wasserstein GANs using stochastic 7-GDA and 7-SGA on simple benchmarks.
INTRODUCTION
Riemannian min-max problem has attracted a lot of research attention in recent years, with various machine learning applications including robust PCA (Jordan et al.) (022), robust neural network training (Huang& & Gao 2023) and generative adversarial network (GAN) (Han et al. 2023). This problem formalized as two-player zero-sum game, where the variables of each player are constrained on the Riemannian manifold Mi and M2.
min max f(x, y). ZEMi NEM2
When M₁ and M2 are Fuclidean, gradient- gradient-based methods such as gradient-descent-ascene (GDA) (Daskalakis & Panageas| 2018:Linn Lin et al., 2020), extra-gradient (Gidel et al., 2019 Mahdavinia et al.
2022), optimistic mirror descent (Mertikopoulos et al., 2019), Hamiltonian-graiien
descent (Loizou 2020) and symplectic gradient-adjustmen (SGA) (Balduzzi et al.) 2018) are often considered
et al. solve this problem. When Mi and M2 Riemannian, how to extend existing algorithms from Euclidean space to Riemannian manifold and how to analyze their convergence become an interesting topic in recent years. In Table I summarize some related works the Riemannian min-max problem. In particular, we observe that under suitable assumptions of the game, one can obtain the global convergence of a suitable algorithm towards Nash equilibrium. One major issue that these assumptions typically do not hold in applications such as GAN (Razaviyayn et al.) 2020). However, when a min-max problem non-convex and non-concave, even in the Euclidean case, the global convergence of existing algorithms can be complicated (Hsieh et al. 2021]. To achieve this, suitable notion solution set and novel algorithmic development and analysis are needed (Jin et al.)
2020 Benaim & Miclo, 2024). In this article, we focus on the following solutions sets: differential Stackelberg equilibrium (DSE) and differential Nash equilibrium (DNE), which are known to be generic among local Stackelberg equilibrium (resp. local Nash equilibrium) in Euclidean smooth non-convex non-concave min-max max problems (Fiez et al. 2020). We then develop local convergence analysis of min-max algorithms and show its relevance to the training of GAN.

---

Published as a conference paper at ICLR 2025
Table Related works of Riemannian min-max problem. These works study the global convergence of min-max algorithms to different solution sets. However, they make assumptions on the game M2, f) which typically do not hold in the practice of GANs.
Reference
Class of problem
Solution set Algorithm
Zhang et 2023
Geodesically convex (compact) M1,M2
Nash equilibrium Extra-gradient semi-continuous (lower/upper)
f is geodesically convex/concave (quasi),
Jordan al. 2022
+Bounded M1.M2
Nash equilibrium Extra-gradient
f is geodesically convex/concave, smooth Euclidean M2
Huang& & Gao
2023
Stationary point of max, f GDA
f is strongly concave in
Han al.
2023
Complete MI.MM
Stationary point of f Hamiltonian
(z, v) + llgrad, + Ilgra,, is Polyak-Lojasiewicz
This work
f twice continuously differentiable
differential equilibrium / GDA,SGA
Section reviews the definition of DSE on Riemannian manifold, which includes DNE as a special case. We then analyze the local convergence of simultancous min-max algorithms to DSE and DNE, in which the variables (z, 3) are updated simultancously at each iteration. In Section we adopt the classical Ostrowski theorem simultaneous algorithms to a fixed point. The problem is reduced to analyze the eigenvalues of a Jacobian matrix Euclidean local coordinate, which is at the heart of analyzing various Euclidean
manifold analyze the local convergence of deterministic
min-max algorithms (Daskalakis & Panageas 2018: Azizian et al. 2020 Fiez & Ratlifi [022] [] Zhang
al., 2022]] Li et al., 2022]]de de Montbrun & Renault 2022). In Section 3.2 sufficient conditions on are given to ensure the local convergence of T-GDA to DSE or DNE, where the learning rate ratio
used to adjust x and y at two different learning rates.
One issue of F-GDA is its slow convergence rate when there are strong rotational dynamics (Li et al. 2022). This well-known phenomenon near a Nash equilibrium in bilinear games due to the competitive nature between two players. To improve the convergence, first-order methods such as extra-gradient and optimistic mirror descent are often used to correct the gradient direction of GDAA. Recently, these methods have been extended to Riemannian manifold (Zhang et al. 2023 Hu et al.
2023 Wang et al. 2023). However, their computations rely on exponential map and parallel transport which can be costly (Absil et al. 2008 In Section 3.3
develop algorithm 7 7-G to address the same rotational problem based on auto-differentiation. naturally extends the SGA algorithm
(Gemp& & Mahadevan] 2018 Balduzzi al. 2018 Letcher et al.) 2019) Riemannian manifold by using a learning rate ratio r as in GDAA. We then analyze the convergence of an asymptotic variant of the deterministic 7-SG which is an approximation of 7SGG when large.
In Section we apply 7-GDA and 7-SGA to train orthogonal Wasserstein GANs (üüller et al. 2019). The underlying min-max problem is Riemannian since we shall impose Stiefel manifold constraints to construct seacciitz-omtinuuuss discriminators. This allows one to compute a lower bound of Wasserstein distance which can generalize high dimension with polynomial number of training samples (Arora et al.) 2017 Biau et al. 2021 Section concludes with some discussions. In summary, our main contributions are:
Based on the notions of DSE and DNE on Riemannian manifold, we derive sufficient conditions in terms of the range of T and the learning rate of æ to obtain linear convergence rate of deterministic 7-GDA to DSE and DNE, They rely on intrinsic quantities of Riemannian manifold.
We develop an algorithm 7-SGA to improve the convergence of 7-GDA. In some cases, the asymptotic variant of deterministic 7-SGA allows for broader range of to be chosen to ensure its convergence to DSE with a faster rate. This indicates that SSG can achieve a faster local convergence compared to --GDA.
We apply the insights from the local convergence analysis to improve the training of orthogonal Wasserstein GANs. We find numerically that an improved convergence of stochastic 7-GDA and SGA may also improve the generator quality on simple benchmarks. Results can be reproduced from pytorch software ht //g: tlg...tlbb........oo com/ s x weeiinnhhhhhee / memannii a mi x_ go
2

---

Published as a conference paper at ICLR 2025
2 DIFFERENTIAL EQUILIBRIUM ON RIEMANNIAN MANIFOLD
The notion of DNE on manifold was given in Rathiff 2013). This section reviews the notions of DSE and DNE through their intrinsic and local coordinate definitions on Riemannian manifold. We then provide some simple examples illustrate their difference. Additional mathematical notations used in this article are summarized in Appendix A
2.1 DIFFERENTIAL STACKELBERG EQUILIBRIUM (DSE)
We write E C2 if it is twice continuously differentiable the product manifold Mi M2- When M1 and M2 are Euclidean, the notion of DSE is defined based on the first and second order derivatives of at this equilibrium (Fiez al. (020). The definition of DSE is natural extension of this concept to Riemannian manifold.
Definition 2.1. We say that (x" v²) is a DSE of
gradzI(æ* -1" = D, "r"" - -Hessy fx= (x=,,²) ,²² p.d (abbrev. of positive definite), [ess, - - -Hess,HH) gradzy f)("",""))) p.d.
(1)
(2)
In this definition, we rely on the following intrinsic quantities the literature of Riemannian
optimization (see/Absil et al. 2008 Section 3.6.Definition 5.5.1) and Han et al. 2023 Section 2.1)):
Riemannian gradient: grad (x. y) E M, ..r.d, y) E M,
Riemannian Hessian: Hess, (z. y) T&M1 + T,.M, Hess, TyM2 MyM
Riemannian cross- gooss-gradient: grad? yy (I, T2M1 My,2,, ( T2M22 T.M1.
Here we denote the tangent space of MM at E M1 by Ty (resp. M2aty E M2 by T2,M2). The condition ① means that (xr", y²) is a critical point of f. Note that the eigenvalues of Hess, f'" y²) and Hess, I' [x"", yy) depend on the Riemannian metric on Mi x M2. However, the notion of DSE does not depend the choice of Riemannian metric, due the following known fact.
Fact: The notion of DSE in Definition 2. can be equivalently defined in a local coordinate chart which does not depend on the choice of Riemannian metric.
To make this point clear, we take a local coordinate chart (0) x O2, 9 x p2) around (x* "","") E Mj M2 (see Absil et al. (2008 Section 3.1.3.2)). We the rewrite the function f(x,,) y) O₃ O2 using this chart by
f(u1, u2) = ((z))
In Appendix we verify the equivalence between and the following conditions
6
Ou, Flui, ug) = O, fun u5) =0,
(4)
02 - (uū p.d,
(5)
[0 02 J (02 ()
0² ue (ui, p.d.
(6)
We see that the conditions 4 do not depend on the choice of Riemannian metric, therefore Definition 2.J still holds if the Riemannian metric is changed Mi x M2.
imply that (uj, u²) (1)(2 (2(())) )) is local minimax point of f. Furthermore, from the implicit function
is known that a DSE a local minimax point (Jin et al. 2020). The conditions
theorem on Riemannian manifold given in Appendix C (a "y"))) a local minimax point of f in the following sense: there exists an open subset Un U2 of Mi M2, which includes (x" vy" and on which there is a unique function U, - U2, such that the following holds
1(x v) S f(x", .y") S max (wx v/) ((,,h())) V(z, v) x U2.
y'EU2
The set ((x, h())) E U.} is sometimes called the ridge near DSE WWag et al. 2020
3

---

Published as a conference paper at ICLR 2025
2.2 DIFFERENTIAL NASH EQUILIBRIUM (DNE) AND EXAMPLES
In game theory, one is often interested in finding a Nash equilibrium since it maintains a symmetry between the role of the players. When Mi and M2 are Euclidean, it is also called "strongly local Definition 1.6).
min-max point" (Daskalakis & Panageas 2018
The notion of DNE was introduced in Ratliff et al. (2013) 3] through a local coordinate chart. This is equivalent to the following intrinsic definition:
Definition 2.2. We say that (x", ,y") is DNE of f E if
gradzf(x" ,3"" = 0, "r"d""""""""" =0; 0,
(7)
- y (x= ,V) p.d, Hess=f(z", .v") p.d.
(8)
From the definition, it is clear that DNE DSE. We remark that this concept is defined locally, and therefore it is different to the global Nash-type equilibria on manifold in Kristály (2014).
2.2.1 EXAMPLE 1: DSE
Consider f(x, y) = (y, Ax b). with I E M₁ = R and y E MM = Sth, The manifold S is the unit sphere embedded in Rd endowed with the Euclidean metric (---) 12+, Let A+ denote the pseudo-inverse of A E [g x)x We next construct scenario where DSE exists.
Proposition 2.1. Assume b & Range(A), Ker(A) = {0]. Letx" A+b, y" = T (a", ,e" a DSE of the f Example
-r" then
The proof is given in Appendix DJ Since M₁ is Euclidean, it is clear that fl= y²) = 0. This implies that the (x* y²) is not DNE. But each eigenvalue of A -Hess, o f( ,y²) equals to ||Ar* bll > O, since from the proof (A( ||Ax* b|ll|n 2|2 for any 17" M2.
2.2.2 EXAMPLE 2: DSE
Consider f(x, y) = (y, Ax b) 5 Ax|
with x E MM Rd and E M2 = S Compared add quadratic function of Ar with curvature parameter O. We next
the in Example show that if k is close to zero, we can still find a DSE near the DSE in Proposition 2.1
Proposition 2.2. Assume b of Range(A), Ker(A) {0}. There exists 0 < No, there is a number close to 1, x" cA+b and y² DSE of the f in Example
0 such that for any
Az" TA- so that (x", ,2"") ) is
The proof is given in Appendix From the proof, we have C = az f y) = - A. The spectral radius of C equals its operator norm ||C|| = x xi|ATA]] Al 0. As in Example all the eigenvalues of A f y²) equal to ||Ar" - bll IcAA+bb - bll. These quantities will be used in Section analyze the local convergence of min-max algorithms.
2.2.3 EXAMPLE 3: DNE
Consider f(z, y) 1 |r + y b1l2 with E Mi Rd and y M2 Sda, M2 is the same embedded sub- manifold of d22+1 above. We next provide sufficient condition the existence of DNE. The proof is given in Appendix [F]
Range(A) A), Ker(A) = {0). Let xx A+b, n² (a" .v") is a DNE of the f in Example 3.
Proposition 2.3. Assume
Az" Ma bi
then
3 SIMULTANEOUS MIN-MAX ALGORITHMS FOR DIFFERENTIAL EQUILIBRIUM
Simultancous gradient- min-max algorithms such as GDA and SGA are often used to find local Nash equilibrium when Mi and M2 are Euclidean (Daskalakis & Panageas 201 8 Letcher et al.) 2019). Similar to GDA, we extend the SGA algorithm to Riemannian manifold with two-tin -io-time scale update (Heusel et al. 2017) using either deterministic or stochastic gradients. Section 3.1 reviews a classical result of fixed point theorem. Based on this theorem, we then focus on a deterministic analysis of the local convergence of these algorithms DSE and DNE.
4

---

Published as a conference paper at ICLR 2025
3.1 LOCAL CONVERGENCE OF DETERMINISTIC SIMULTANEOUS ALGORITHMS
We use the classical Ostrowski theorem to analyze the local convergence of simultaneous deterministic algorithms on manifold. Each algorithm is defined by an update rule which does not change over iteration. This theorem provides a sufficient condition for the linear convergence rate of an algorithm fixed point, based on the spectral radius of the update rule's 's Jacobian matrix at the fixed point.
A deterministic simultancous algorithm is defined by two vector fields (æ, y) + (i y) E TrM (z, y)
(2 y) E yy on M₁ and M2, and a suitable choice of manifold retractions (see Absil et al. 2008 Section 4.1)). Initialized at point (z(0), v(0) on M2 x MM2, the algorithm generates a sequence (a + 1), v(t++)) = ((x(t), vt)), through an update rule T M1 M2 + M1 M2 of the following form,
T(x, = (R1, (Ei, v)), (Ea v))), where R1, : Mi + Mi (resp. R2, : TTyM2 + M2) denotes the restriction of a retraction R at x E MM (resp. retraction of R2 at E MM2) For example, on the MI = R4 and MM = Sd2 in Section 2.2 we will take (6)= = x + 8 for d Rd, and R2 (17) to be the projection of the vector y + 1) gd++1 to the sphere M2-
We say that (x",y") E MI x M2 is fixed point of T if is a critical point of the vector fields & and E2. We next define what it means for an update rule T be locally convergent to (x*, ,,"'"'' yy"). implies that it is also point of attraction of T (Ortega & Rheinboldt, 1970, Definition 10.1.1).
Definition 3.1 (Locally convergent with (linear) rate p (0, 1)). Let (x* .y") be a fixed point T. For any e E (0, p). there exists a local stable region Ss C CM1 x M2, which con- tains a geodesically convex open set (and homeomorphic
a ball) containing (z",y"), such that started from (z(0), v(0) Ss. we have (x(t), E Ss. Vt 2 1. Furthermore, let d(t) be the Riemannian distance between (a((), v(t)) and (x", ,y),, then there exists constant C s.J. d(t) S Cpp d(0), Vt O.
We next give a sufficient condition of T to achieve the local linear convergence. It is based on the spectral radius of the following linear transformation on Tx. Mi T2-M2,
DT T' ,0" ( 1+ VoEilat v") DyEi(o",y)) I+ VyEe(1"
D2E2(x" vV))
Here D2 and Vv (resp. Dy and V Vy) denote the differential operator and the Riemannian connection on M1 (resp. on M2). Note that DT equals to the tangent map of T at (x", y"), ), no matter how one chooses the retraction R, and R2 (c.f. Appendix G.I). When Mi and M2 are Euclidean, is the Jacobian matrix of T at (x*,y"))
Theorem 3.1 (Ostrowski Theorem on manifold), Let (x* , y²) be a fixed point Tf Assume that E and &2 are continuous on Mi x M2, and they are differentiable at (x", such such that p(DT*) < 1,
then T is locally convergent to (x* .y") with rate p(DT").
This result is proved in Ortega & Rheinboldt (1770, Section 10.1.3) when Mi and MM are Euclidean. The proof idea can be readily extended the manifold case. In the statement of Theorem 3.1 we add an assumption on the continuity to E and & to ensure a non-empty local stable region S To make the article self-contained, we provide proof of this theorem Appendix G This proof does not give an explicit way to construct the local stable region Sg. Therefore it is unclear what a good initialization entails. To obtain precise size of Sa, extra assumptions on f would be needed.
Theorem 3.1 has local nature as the convergence rate p p(DT*) does not depend on any global manifold property. One can also use the stronger operator norm assumption |TT in Boumal (2023 Theorem 4. 19) to obtain similar local convergence result.
3.2
SIMULTANEOUS PRADIENT-DESCENT-ASCOE ALGORITHM (T-GDA)
The GGDA algorithm uses the Riemannian gradients grad, y) and grad, f(, (z. 1) to update x and y simultancously. The local convergence of deterministic -DGD to DSE and DNE is well-studied
in Euclidean space (Daskalakis & Panageas 2018 Jin et al. 2020 Fiez & Ratlifi 2021 Li et al.
2022). This section extends these results to Riemannian manifold. We obtain sharp lower-boun of
7 for T-GDA to be locally convergent to DSE. It is based on a refinement of the spectral analysis in Fuclidean space (Li et al. 2022).
5

---

Published as a conference paper at ICLR 2025
7-GDA algorithm In the deterministic setting, the update rule T of 7-GDA is determined by
E (I, y) = -Ygrad (z: y), (z(2, y) = f
(10)
Note that >> O and we use a ratio т > 0 to adjust the learning rate (step size) of the Riemannian gradients. The deterministic r-GDA can be readily extended to stochastic r-GDA by using an
unbiased estimation of the Riemannian gradients (Jordan et al. 2022: Huang & Gao 2023).
Local convergence of deterministic r-GDA Based on Theorem 3.1 we are ready to study the local convergence of T-GDA (defined by (10) to DSE and DNE. From the definition of Riemannian Hessian and cross-gradient, rewrite DT + 7Mg using the following linear transform
Mg
C -BA) 7 BBT
)
f(" ( f ((",)"")))))))))) H (x",,")
fa"",
(11)
-TA
For Hurwitz-stable linear transform M whose eigenvalues all have strictly negative real part, we write ? (M) = -2 max;
Re(Ax(M) It computes an upper bound of y such that p(1 + 7M) 1. (M)
Let gg max All. |BI,, [Cl) and My min(Ly. Amin (C + BA BA-
Theorem 3.2. Assume (x" .y") is a DSE of C², IfT [C] and y E (0.7 F-GDA 2h, and 7 3rL,'' locally convergent to (x*, v²) with rute p(1 + M)g) Farthermore, if Amin(A) the rate is most 1
Amin(A)
16r LG
The proof is given in Appendix H This result is extension of the Euclidean space result in Li et al. [2022 Theorem 4.2) (without assuming Mg being diagonalizable). When M1 and M2 are Euclidean, range (r E |T > ||02, f(x", "0lma//m)"/llmm yg. fxx", .y"))""" } in Theorem 3.2 is sharp as one construct counter-example (Li et al., 2022, Theorem 4. to show that if r is outside this
range, the spectral radius of the Jacobian matrix stricctyyy larger than one for any y >> 0 (see also discussion in Li et al. 2022
Remark 2)).
Theorem 3.2 can be readily applied to analyze the local convergence of G-GDA to DNE. However, we can obtain broader range of r. The next result generalizes local convergence properties of 7-GDA to DNE from Fuclidean space to Riemannian manifold.
Theorem 3.3 (Jin et al. (2020); Zhang et al. (2022). ). Assume (x",y") is a DNE of f E C² and Fg min (Amin (A), Amin ()). If and 7 (0, 7 (M,)) T-GDA locally convergent to
(x*, .."")) with rate p(I + M,). Furthermore, if r = and Bgg the rate at most AL2
The proof is given in Appendix ! The common reason that we can obtain such extensions in Theorem 3.2 and 3.3 that the spectral analysis of the matrix Mg reduced a similar matrix My in local coordinate (see (42) and the spectral properties of each intrinsic term (A, B, C) in M, are the same as those in Mg. We can therefore use existing Euclidean results to derive a sufficient condition to control the spectral radius of Mg. and then identify equivalent condition in terms of M,.
3.3 SYMPLECTIC GRADIENT-ADIUSTMEN METHOD (r-SGA)
In Euclidean space, SGA modifies the update rule of GDA avoid strong rotational dynamics near a fixed point (Gemp& & Mahadevan, 2018). We apply this idea to 7-GDA and extend it to Riemannian manifold. We then study its local convergence to DSE when 7 is large.
S-SA algorithm SGA adjusts a vector field & using orthogonal vector field which is constructed from the ayti-symmetrie part of the Jacobian matrix of &. 7GDA, E(x, y) = (-8(a, y), TT)(r, y))
where 6(x, y) = grad_ [ (z. y) and n(.,,) v) =grad, y f(x y). Based on this idea, the adjustment of 7-SG depends on the Riemannian cross cross-grades -ooss-gradsents B(z, y) = ff gradz f f(x y), which is summarized in the following update rule (with hyper-parameter IR),
f(z y) and BT y)
(T+ B (...))
(xx = =-> ((z v) +
(12)
7 (2 7 (m](s.))
+ -1
B (x,,)\((x,,
(13)

---

Published as a conference paper at ICLR 2025
In Appendix D we provide the derivation of this update rule. The next proposition shows that the adjusted direction (-rB(r). [ō]] is orthogonal to & (-6,Tn).
Proposition 3.1. For any vz E M, x M2. we have (a, y)n(( w)), ((11)))))))))))
v)1, -rn y)), O.
The proof is given in Appendix J.1 In the original SGA method, the orthogonality is essential to make it compatible to potential and Hamiltonian game dynamics. This proposition implies that such compatibility still makes sense for 7-GGA In Appendix D we discuss how perform deterministic and stochastic gradient adjustment using auto auto-differentiation when M1 and M2 are Euclidean embedded sub-manifolds (Absil et al. 2008 Chapter 3.3).
Local convergence of deterministic --SGA to DSE: asymptotic analysis We study the local convergence of r-SGA with deterministic gradients in an asymptotic regime where r + 00. In this regime, to make the term B(r) comparable to the term 5 in (12) we re-parameterize μ = r(7+1) ~
77. As a consequence, 1r 1 ~ 7 and the update rule
13 can be approximated by the &2 in (T0).
The next theorem analyzes the local convergence of Asymptotic r-SGA, which is an approximation of TSGA, whose { (resp. {2) defined by (12) (resp. (10). In order to apply Theorem [3.1 is necessary to verify that the corresponding & is differentiable at (x","") This is indeed true since Bix, y) is continuous at (x*, y²) and n(2*, y²) O. The following linear transform plays key role in the asymptotic analysis since it gives an approximation of the DT in T-SGA by I + yM,
-C -B rBT
+ (
- -BB BA
M. =
-TA
0
(14)
Let L,, max (I B|I. BIC.IICC+ OBBT]] []) and μ min(Tis, Amin(C 1--B--BB
Theorem 3.4. Assume (x", is DSE of f E C². If min CCIl [C-
Amin (A)' Amin(A) ). μ
[[T+I] with 0 S 0 Aman (AT and 7 E (0, 7 (M,)), Asymptotic r-SGA is locally convergent to 2h,
the rate is at most (x", .V") with rate plI + M.). Furthermore, if 2 Amin (A) and y 4rL. H4
1
T6r
The proof is given in Appendix K Contrary to Theorem 3.2 the valid range of T depends also on the choice of 0. Indeed, if the spectral radius of C is larger than that of C 0BBT with suitable choice of 6, a broader range of r could be used in 7-GG compared to T GDAA. For a DSE (a", y²) which not DNE (i.e. C is not p.d.). such a choice of 0 can be possible. Furthermore. we obtain a non-trivial improvement on the convergence rate in theory as it significantly improves the rate of the extra- stra--gradient method in Euclidean space (Li et al., 2022 Theorem 5.4) when 21, Lg us ||C OBBT| < Lg = Hg |C]]. this case, we could choose a smaller T, X. (A)
and larger 7/- = 47,
1
Amin (A) in Asymptotic --GG to achieve a faster rate 167, compared 812
to the rate 1 - 167, using a larger Tg
1
Amns and smaller % = 1
21.
45, in G-DA.
We next illustrate the convergence results using numerical example, to show that 7-SGA can indeed converge much faster than 7-GDA to DSE when there are strong rotational forces in its dynamics. In Figure [ compare the local convergence rate of 7-GDA and 7-GGA in Example of Section 2.2 where A = [1; E IR 3x1 b = [1: 1; 0.99) E R and Λ = 0.1. In this case, we find numerically that xx 0.9975. The corresponding optimal y² (Ar" b) /) Ar: bl. The initial point of each algorithm is set to be x = b = 0.9967, y = (Ar - b)/ll x - bl]. which is close to the DSE (x" 3²)) In Figure a). we study the range of for the convergence of 7-GDA with 0.001 / According to Theorem 3.2 and Proposition 2.2 a valid range of 7 should be larger than max: (C) AT A|]/||=>" bll R 36.18. Figure a) shows that when
30, 7-GDA can slowly diverge. When 7 = 50, 7-GDA converges slowly to the value f(=".y) = 14. This is a convergence dilemma of 7-GDA: to achieve the local convergence, needs to be large, but the rate can be very slow. In Figure (T) and (c), we study 7-SGA with 0 = 0.15, using the same learning rate rry for y as GDGA. Figure b)) shows that the gap between Asymptotic 7-GG and 7-GGA is not so
Amin(A)
7

---

Published as a conference paper at ICLR 2025
(a)
(b)
20000
B0000 23000
Figure 1: Evolution of far(t), and approximate geodesic distance between (a(t), (t)) to (x" "o"""") as function of the iteration / using deterministic 7-GDA and 7-SGA for Example 2. (a): 50. (b): 7SGG vs. Asymptotic 7-SGA with 10 and r 50. (c): T-GDA at T = 50 vs. 7 T-GGA at 7 E (10,30, 503.
7-GDA with 30
big even if r = 10. Therefore in this specific example, Theorem 3.4 provides a valid picture on the behavior of r-SGA when T is large enough. We find numerically that maxe [Ax(C++BBT)I) 2 16.7,
Amii (A)
which suggests that 7-SGA can be locally convergent with smaller 7 compared T-GDA. Figure Tec) confirms this analysis and it also shows that a faster linear rate can be achieved by r-SGA.
Surprisingly, the approximate geodesic distance (ar(t) x=1 + arccos(y(t)Ty) (an approximation of the Riemmanian distance d(t)) quickly converges towards 0) even if 10.
The local convergence of r-SGA DNE in Euclidean space is analyzed in Letcher et al. (2019 Theorem 10) when r = 1. Using the same proof idea as Theorem [33] one can extend this result Riemmanian manifold. However, when o 1, a DNE is necessarily stable fixed point of the vector field ę = (-6, TW), c. Letcher et al. (019 Definition 4). It is thus unclear if there is a
non-trivial range of μı such that for any 7 SGA locally convergent to DNE.
4 APPLICATION TO WASSERSTEIN GAN
The local convergence analysis in Section 3 shows that a larger 7 is sometimes needed to ensure the local convergence of r-GDA to DSE compared to r-SGA However, in practice, is numerically hard to validate this theory in GAN. In this section, we study the training of orthogonal Wasserstein GAN using stochastic 7-GD and F-SGA. We construct two non-standard examples with the following goals: (1) Illustrate a similar local convergence dilemma near DSE faced by 7-GDA
varies on both synthetic and real datasets. (2) Show that the correction term in -SGA plays a key role to improve 7-GDA when T is small, leading local convergence. (3) Propose simple and clean benchmarks such that theoretical study of smooth Riemannian non-convex non-concave games from GAN could be further developed.
4.1 SETUP OF ORTHIOGNNAL WASSERSTEIN GAN
In Wasserstein GAN, we are interested the following min-max problem
f(z. v) E((D( - (oz))
such that f e C², The idea of GAN is to approximate the probability distribution of ddate E RRd using generator Gz parameterized by E _M The parameter is optimized so that the distribution of de approximates that of ddtta through the feedback of a discriminator D,, IR + R parameterized by E M2. The expectations in f are taken with respect to the random variables Daata and Φ... To build orthogonal Wasserstein GAN Müller et al. 2019), we assume that M₁ is Euclidean and M2 is Riemannian. The manifold constraint subset of i-Liischiiz continuous functions, up to a constant scaling.
restricts the discriminator family (DylueM, to be
We next study examples of Odtta built upon unconditional generator Gz. transforms random noise E R to Φv E RRd from a lower dimension p < d. Further details about Φdata Gr and D,
are given in Appendix M
Gaussian distribution by linear generator We want to model Odata ~ A Σ) on dimension d = 5 using PCA-like model with dimension p 4. The covariance matrix E is diagonal
8

---

Published as a conference paper at ICLR 2025
with small eigenvalue, i.e. (1,22,3?,4* 44, 0.01). We choose the generator (Z) = A.Z, where Ag E 12 and Z is isotropic normal. For the discriminator, we use the Stiefel mamifold St(k, d) of orthogonal vectors Ie to construct (Ø( (Un o (W, ( ,0);, where W,, E St d), by E kt) and a is a smooth non-linearity. We set = d = 5. As Ar is the only generator parameter, 2 = (Ax) M1 = Rdxp. The discriminator parameter y == (W y. myy E M2 St(k; d) S1 k:)
Image modeling by DCGAN generator We aim to model images from the MNIST and Fashion- MNIST datasets (d 28 x 28) using DCGAN generator (p = 128). The space M1 is Euclidean with dimension d1 = 1556673. To simplify the CNN discriminators in WGAN-GP, we consider hybrid Scattering CNN discriminator build upon the wavelet scattering transform to capture discriminative information in natural images (Bruna & Mallat 2013 Oyallon et al. 2017). It has only one trainable layer and therefore is more amenable to thcoretical study,
DØ( (Vy, Juy * P(o) + by)).
The scattering transform P : Rd + IR | is I-Lipschitz and it has no trainable parameter. The scattering features P(ò) E I are computed from an image Φ of size v x vd. We then apply orthogonal convolutional layer to P(ø) (Cisse et al. 2017). It has the kernel orthogonality (Achour al. 2022). by reshaping wy (size x k) into a matrix W, E ( such that Wy E St,J, I.2). The bias parameter by E R' and the output of the convolutional layer is reshaped into a vector in R RJN² As in the Gaussian case, we further assume by E St(1, In summary, == (W,, by: vy) E M2 = SUJJ, TI2) x TR x JI
Initialization of algorithms To study the local convergence of stochastic r-GDA and 7-SGA, we first obtain a reasonable solution of (x. 1) in terms of model quality using (alternating) 7-GDA (see Appendix M..6). We then evaluate 7- 7-GDA and 7-SGA initialized from this solution.
4.2 RESULTS ON GAUSSIAN DISTRIBUTION BY LINEAR GENERATOR
We study the local convergence of stochastic GDGA across various T E {1, 10, 100). In Figure 2 a). we show how the function value f (x((), y(t) (estimated from 1000 training samples) changes over iteration. We observe that when т 1. [x(((), y()) has huge oscillation, but when 100, it has a much smaller oscillation amplitude. To investigate the underlying reason, we compute in Figure b). the evolution of an "angle" quantity every one thousand iterations. The angle at (I. y) is (vv.6(ar.g))) where 5(x, y) = (o (Wyodaaa)))) - ([a(W, (W,dk.) is estimated from the same
10 and
defined as [[ batch of samples during the training. When the angle is close to 1, it indicates that 'y is solved to be optimal. We observe that when r 1, the angle oscillates between positive and negative values, suggesting that Uy(() is detached from 5 (zz(t), vt))) Therefore the minimization of f over æ does not get a good feedback to improve the model. This is confirmed in Figure where we compute the EMD distance (Rubner et al. (2000) every one thousand iterations, between the empirical measure of édata and )z((t) (using 2000 validation samples). We observe that the EMD distance increases over t when 1. On the contrary, it stays close to when 10 and 100. When 100. find that the covariance error || - Au(e) AT [+(ss] stays around 0.2 over all iterations. This error is between the smallest eigenvalue of Σ (which is 0.01, the PCA error) and the second smallest eigenvalue of Σ. Therefore to use a large enough 7 is crucial reduce model error, as can ensure a positive angle to measure meaningful distance between &h and Aatta This phenomenon is consistent with the local convergence of 7DGD to DSE Figure
Table 2:
Last iteration measures of stochastic G-DA and -SGA on the Wasserstein GAN of MNIST, We report the f. angle, and FID scores computed at (xxT"), v(T)). Only significant digits are reported with respect to the standard deviation (shown in (=)) (see Appendix M.7
-DA
T-GGA
angle
FID (train)
FID (val)
T(10))
angle
FID (train)
FID (val)
5
0.13
0.5
13.38 (z0.02)
16
1
0.013
0.4
6.65 (20.04)
8.7 (10.1)
10
0.013
0.47 (20.02)
7.0
9.1ga.
3
0.012
0.3
6.2
8.3 (40.09)
20
0.0136
0.70 c+0.02)
7.0
9.1 (+0.1)
5
0.010
0.36 (2:002))
5.76 (20-030)
7.6 (20.08)

---

Published as a conference paper at ICLR 2025
(a) f(x(t), v(t))
(b) angle(æ(t)) v(t))
(c) (MD(x(())
100
0.3
-03
14-
08
-.8
83
-4.3
2008
200 T9E TOS
Figure 2: Evolution of f=x(t), v()), angle(x(t), v()), and the (M)( distance function of the iteration using stochastic 7-GDA for the Wasserstein GAN of Gaussian distribution. Top: 100, > 0.0002. Middle: T 10, ? 0.002, Bottom: T 7 0.02.
4.3 RESULTS ON MNIST AND FASHION-MNIST BY DCGAN GENERATOR
We apply the insights from theoretical analysis improve the convergence of both 7-GDA and T 7-SGA, so as to obtain a good generative model 6r (measured by the FID scores (Seitzer 20200).
In Table 2 we first report the performance of T-GDA by varying the choice of It is for = 2 x 10s iterations with y = 0.1/T. We find that at r = 5 even though the angle is positive, the value of and FID scores much larger than their initial values. By investigating the evolution of f over the iteration t, we indeed observe unstable dynamics with much stronger oscillation starting from 5000. This suggests that 7-GDA does not have local convergence. This instability is improved when T = 10 or t = 20. We find that
10 can still result in some instability (see Figure in Appendix N if 7 is made about ten times larger. When convergence. We next study the performance of --SGA by varying the total training iterations T. using a fixed y 0.02,
20, 7-GDA has more stable
5, 0 = 0.075. Table 2 we observe that T is increased, the value of and FID scores are decreased. This suggests converging behavior of 7-SGA which is not the case in 7-GDA at 7 = It shows that the correction term in --SGA plays key role to improve the local convergence of r-GD. We also perform similar study on other datasets, which shows consistent conclusions (see Appendix N.2 N.3 and N.4).
In terms of computational efficiency, we find that --GDA and 7-SGA can reach similar FID (test) scores after a similar or smaller amount of training time (see Figure and / in Appendix NN. But sometimes 7-SGA can be slower (see Figure 6 in Appendix Nj. In these cases, find that the computational time of TSG per iteration t is roughly 3-4 times that of r-GDA. This implics that in terms of the number of iteration f, 7-SGA is faster than 7-GDA.
5 CONCLUSION
In this article, we analyze the local convergence of 7-GDA and r-SGA two differential equilibria on Riemannian manifold, hased on a classical fixed point theorem and spectral analysis. This method allows one to reduce the problem into Euclidean space using local coordinate chart. We obtain a linear local convergence of 7-GDA to DSE and DNE where the linear rate is upper bounded by the spectral radius of an intrinsic Jacobian matrix. To improve the local convergence, 7-SGA is developed and extended to Riemannian manifold for the first time. Based on the asymptotic analysis where tends to infinity, we find that sometimes an improved rate of SSGA DSE can be reached. The methodology could be served as a basis to analyze other simultaneous algorithms such as the Riemannian Hamiltonian method (Han al. 2023).
To show the relevance of our results to GAN, we study the behavior of stochastic r-GDA and T-SGA on simple benchmarks of orthogonal Wasserstein GANs. Even though our current theory does not apply to analyze these stochastic algorithms, we observe consistent behavior similar to their deterministic convergence to DSE. This suggests that DSE could be a suitable solution set towards which our chosen initialization algorithms (alternating) 7-GDA converge. This phenomenon is also observed in non-zero sum games such as NS-GAN and WGAN-GP using Adam-baser algorithms (Berard et al. 2020
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank all the anonymous reviewers for their valuable feedback. Sixin Zhang acknowledges very helpful discussions with Shengyuan Zhao, Yuxin Ge, Jérôme Renault and Yijia Wang. This work was partially supported by a grant from AAP EMERGENCE under the Project HERMES. It was also supported by the computing resources in the OCCIDATA and CALMIP platforms.
REFERENCES
P.-. Absil, R Mahony, and Rodolphe Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton, 2008
El Mehdi Achour, François Malgouyres, and Franck Mamalet. Existence, stability and scalability of orthogonal convolutional neural networks. Journal of Machine Learning Research, 23:1-56, jan 2022.
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (GANs). In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 224-23222222222 PMLR, 06-11 Aug 2017.
Waiss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. A Tight and Unified Analysis of Gradient- -ased Methods for Whole Spectrum of Differentiable Games. In Interna- tional Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 2863-2873, Virtual Event, 2020.
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, volume 80, pp. 354-363, Stockholmsmässan, Stockholm Sweden, 2018.
Michel Benaim and Laurent Miclo. The asymptotic behavior of fraudulent algorithms. arXiv preprint arX1v:2401.12605. 2024.
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, Addis Ababa, Ethiopia, 2020.
Gérard Biau, Maxime Sangnier, and Ugo Tanielian. Some theoretical insights into Wasserstein GANs. Journal of Machine Learning Research, 22:1-45, 2021.
Koushik Biswas, Sandeep Kumar, Shilpak Banerjee, and Ashish Kumar Pandey. Smooth Maximum Unit: Smooth Activation Function for Deep Networks using Smoothing Maximum Technique. In Conference on Computer Vision and Puttern Recognition, pp. 784-793, New Orleans, LA, USA, 2022.
Nicolas Boumal. An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, 2023.
J Bruna and S Mallat, Invariant Scattering Convolution Networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8):1872-1885 2013.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: improving robustness to adversarial examples. In International Conference on Machine Learning, pp. 854-863, Sydney, Australia, 2017.
Constantinos Daskalakis and Ioannis Panageas. The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization. In Advances in neural information processing systems, pp. 9256-9266, Red Hook, NY, USA, 2018.
Étienne de Montbrun and Jérôme Renault. Optimistic Gradient Descent Ascent in Zero-Sum and General-Sum Bilinear Games, arXiv preprint arXiv:2208. 20X0022008.0085, 2022.
Tanner Fiez and Lillian J Ratliff. Local convergence analysis of gradient descent ascent with finite timescale separation. In International Conference Learning Representation, 2021.
11

---

Published as a conference paper at ICLR 2025
Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Implicit learning dynamics in stackelberg games: Equilibria characterization, convergence analysis, and empirical study. In International Conference on Machine Learning. pp- 3133-3144, Virtual Event, 2020. PMLR.
lan Gemp and Sridhar Mahadevan. Global Convergence to the Equilibrium of GANs using Variational Inequalities. arXiv preprint arXiv: 1003::8880.0111,, 2018.
Gauthier Gidel, Hugo Berard, Gaětan Vignoud, Pascal Vincent, and Simon I Lacoste-Julien. A Varia- tional Incquality Perspective on Generative Adversarial Networks. In International Conference on Learning Representations, New Orleans, LA, USA, 2019.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. In Advances in neural information processing systems, volume 30, pp. 5767-5777, Long Beach, CA, USA, 2017.
Andi Han, Bamdev Mishra, Pratik Jawanpuria, Pawan Kumar, and Junbin Gao. Riemannian Hamil- tonian methods for min-max optimization on manifolds. SIAM Journal Optimization, 33(3): 1797-1827, 2023.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium. In Advances in Neural Information Processing Systems, pp. 6629-6640, Long Beach, CA, USA. 2017.
Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. The Limits of Min-Max Optimization Algorithms: Convergence Spurious Non-Critical Sets. In International Conference on Machine Learning, volume 139, pp. 4337-4348 Virtual Event, 2021.
S.T. Hu. Differentiable Manifolds. Springer Nature Book Archives Millennium. Holt, Rinehart and Winston, 1969.
Zihao Hu, Guanghui Wang, Xi Wang, Andre Wibisono, Jacob Abemetty, and Molei Tao. Ex- tragradient Type Methods for Riemannian Variational Inequality Problems. arXiv preprint arXiv:2309. 14155, 2023.
Feihu Huang and Shangqian Gao. Gradient Descent Ascent for Minimax Problems on Riemannian Manifolds. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1(7):8466 - 8476, 2023.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-nonconcavs minimax optimization? International Conference on Machine Learning, pp. 4880-4889, Virtual Event, 2020.
Michael Jordan, Tianyi Lin, and Emmanouil-Vasileion Vlatakis GaaaakiiGGG First-Order Algo- rithms for Min-Max Optimization in Geodesic Metrie Spaces. In Advances Neural Information Processing Systems, volume 35, 6557-6574, New Orleans, Louisiana, USA, 2022.
Alexandru Kristály. Nash-type equilibria on riemannian manifolds: variational approach. Journal de Mathématiques Pures et Appliquées, 101655:660-688, 2014. ISSN 0021-7824.
Alistair Letcher, David Balduzzi, Sébastien Racanière, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. Differentiable Game Mechanics. Journal of Machine Learning Research, 20 (84):1-40, 2019.
Haochuan Li, Farzan Farnia, Subhro Das, and Ali Jadbabaie. On convergence of gradient descent ascent: A tight local analysis. In International Conference on Machine Learning, pp. 12717-12740, Baltimore, Maryland USA, 2022, PMLR.
Tianyi Lin, Chi Jin, and Michael I Jordan. On Gradient Descent Ascent for Mannconeex-Coecaa Minimax Problems. In International Conference on Machine Learning, pp. 6083-6093, Virtual Event, 2020.
12

---

Published as a conference paper at ICLR 2025
Nicolas Loizou, Hugo Berard, Alexia Malcoeur-Martineau Pascal Vincent, Simon Lacoste-Julien, and Ioannis Mitliagkas. Stochastic Hamiltonian Gradient Methods for Smooth Games. In International Conference Machine Learning, volume 119, pp. 6370-6381, Virtual Event, 2020.
Pouria Mahdavinia, Yuyang Deng, Haochuan Li, and Mehrdad Mahdavi. Tight analysis of extra- gradient and optimistic gradient methods for nonconvex minimax problems. Advances in Neural Information Processing Systems, 35:31213-311 2022.
Jonathan H Manton. Optimization algorithms exploiting unitary constraints. IEEE Transactions Signal Processing, 50(3):635-650, 2002.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-poing problems: Going the extra (gradient) mile. In International Conference Learning Representations, New Orleans, LA, USA, 2019.
Jan Müller, Reinhard Klein, and Michael Weinmann. Orthogonal wasserstein gans. arXiv preprint 1rXiv:191..13066 2019.
J M Ortega and W C Rheinboldt. Iterative Solution of Nonlinear Equations in Several Variables. New York: : Academic Press, 1970.
Edouard Oyallon, Eugene Belilovsky, and Sergey Zagoruyko. Scaling the Scattering Transform: Deep Hybrid Networks. In International Conference on Computer Vision, Venice, Italy, 2017.
Lillian J Ratliff, Samuel A Burden, and S Shankar Sastry. Characterization and computation of local Nash equilibria in continuous games. Conference on Communication, Control, and Computing, pp. 917-991799 177-924, Allerton, USA, 2013.
Meisam Razaviyayn, Tianjian Huang, Songtao Lu, Maher Nouiehed, Maziar Sanjabi, and Mingyi Hong. Nonconvex min-max optimization: Applications, challenges, and recent theoretical advances. IEEE Signal Processing Magazine, 37(5):55-66, 2020.
Yossi Rubner, Carlo Tomasi, and Leonidas J Guibas. The earth mover's distance metric for image retrieval. International journal of computer vision, 40:99-1211 121, 2000.
W Rudin. Principles of Mathematical Analysis. McGraw-Hill Publishing Company, 3rd edition, 1976.
Maximilian Seitzer. pytorch-fid fid:: FID Score for PyTorch. ortorch-fid] 2020.
Xi Wang. Deming Yuan, Yiguang Hong. Zihao Hu, Lei Wang, and Guodong Shi. Riemannian Optimistic Algorithms. arXiv preprint arXiv:2308. 16004, 2023.
Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On Solving Minimax Optimization Locally: A Follow-the- Ridge Approach. In International Conference on Learning Representations, Addis Ababa, Ethiopia, 2020.
Xingzhi Zhan. Matrix Inequalities. Springer Berlin, Heidelberg, 2002.
Guodong Zhang, Yuanhao Wang, Laurent Lessard, and Roger B Grosse. Near-optimal local conver- gence of alternating gradient descent-ascent for minimax optimization. International Conference on Artificial Intelligence and Statistics, pp. 7659-76799 Virtual Event, 2022.
Peiyuan Zhang, Jingzhao Zhang, and Suvrit Sra. Sion's Minimax Theorem in Geodesic Metric Spaces and Riemannian Extragradient Algorithm. SIAM Journal Optimization, 33(4), 2023.
13

---

Published as a conference paper at ICLR 2025
A NOTATIONS
Let dj and d2 denote the dimension of M1 and M2. Let (M1) (resp. X(M2)) be the set of con- tinuously differentiable vector fields on Mi (resp. M2). Since f twice continuously differentiable, we have for any y E M2 (resp. E M1), wrad,f(ss E (M1 (resp. grad, (T, E (MM))). We write 91 and 92 to denote the Riemannian metric on M1 and M2.
Let @ and 0 denote the first-order and second-orde partial derivatives of a function on Euclidean space. For real symmetric matrix A, Amaz(A) (A) denotes the maximal eigenvalue of A, Amin (A) denotes the minimal eigenvalue of A, and As (AA denotes its k-th smallest eigenvalue. For linear transform B, p (B) denotes its spectral radius and []]]| denotes its operator norm.
B DEFINITION OF DSE
The main idea is to use the local coordinate chart (O₁ x O2: F1 x (22) to represent the smooth vector fields (x, w) grad, (z, y) and (z. v) + grad, (z, v) around the point (z", ,y"), so as to show the equivalence between 4466) and
3p.
For each Or (resp. O2). let (z), (resp. (2))())) be the canonical basis of the tangent space T,M1 (resp. MyM22, defined by the tangent map Dup (pr (x))[e1,s) of the canonical basis fei,) Rdi (resp. Dup²" (pp (va(())) (e2,l of (easlisa, R2)).
Let the local coordinate of (x, v) E O1 O2 be (u1, u2) = (x1((x), (2(1)) E O O2 (0)) (p2( C Rdi x RRds We can represent
( y) grad, (x,
Σ
(1, y) (x))
(15)
isdi
62 y) = grad f(, = Σ
E2 8) E2,(y)
(16)
3Sda
From 15 and (16). the local coordinates of the Riemannian gradients on O₁ O2 are
(1(1,
Σ E1,(111 12 (12)))))
(17)
i5d;
(2 U2)
Σ
E (v) (())))))))
(18)
SSda
Equivalence between and T
Let the local Riemannian metric matrix at x = up
E
and y = =5= (u2) E Oz
(u,) (g) (x), E (s)) (=(2))
(1), (1)))
(19)
From (bbiil et al. 2008 chap. 3.6), we have for (u1, u2) E Ō, O2, (11, u2) = ğn ((1) -1 0u, f(u1, u2), (u u2) = g2(u2) 00, f(uj, u2).
(20)
(21)
The equivalence between the DSE condition 44) and (I) follows from 20 and 21 as E (uf, u5)
0
i.f.f. (if and only if) grad, (x= y²) (similarly for the relationship between & and grad, f).
Equivalence between (5) and Let E M2, with its local coordinate π = D22 In""). To show that the positive definiteness of - [x",,"""" v²) ) is equivalent to the positive definiteness
of - -i [(n uz), it sufficient verify that
0 Su uz)m"") ,ess,, (x", "n""))
(22)
where (..)) denotes the inner product on Euclidean space, and (,, >) denotes the Riemannian inner product T M.
14

---

Published as a conference paper at ICLR 2025
Recall that the Riemannian Hessian M2 is defined by the Riemannian connection Vy ((M2) x x(M2) + x(M2) with Hessy,((x; y) = Vy52(z, y). By the R-linearity and Leibniz law of the
connection, we have
Vota(x", "n)=== V. Σ fa,( ,y' (('(""""")))"" E2) M)("
Σ VolEz,(0* B25 Mr*1
Σ (DDyEaa ,9 Mb)") Bas"))
(23)
dbes (ui, ui)n") Fz,((")) Ouz
Σ
(24)
We have obtained (4 from 23 because any DSE (x", is critical point of f, therefore (2, 1/" = 0 for each j < d2. Moreover, the tangent map D v")[n" by definition (Absil et al. 2008 chap. 3.5.4).
dead duz
(ui, u²)m"
Therefore the local coordinate of the tangent vector Vo yz" (n7] E M2 is Suy
8E2
(u us fj" E
Rdda It follows from 21..2 and the Riemannian inner product (Absil et al.
2008 chap. 3.6) that
(n Hess, ((xxx=""""""))""""""""" "n)nn>>>> = (1. - (20))))))))
052 (ui, u²)n7*
(25)
Ouz
= -mi uu [u ug)
Therefore 22 holds. This verifies the equivalence between and
Equivalence between (6) and 3 Assume (x". 1/") is DSE of f. from the equivalence between (5) and (2). we deduce that (a* yy) (resp. (ui, uz)) a critical point f (resp. f). Moreover, Hess, (x* yy" and & J [wi,, uz) are negative definite.
To simplify the notation, let
A Eng ug), B = - oignn ff f(ui, u5), C= f( uz)-
(26)
The condition (6) is equivalent to the positive definiteness of the matrix BA-
Let 8" E Te. M₁, with its local coordinate 5* Dipi Dip((x")("') As in 22 it suffices to verify that
(C, + BA BT) [ - grad f (Hess,, grad 112" v²) 18"))a
Based on the proof of 22 we also have ( C Hess, yy) (5*1)a- remains to y f( 18
verify that
BA 8*) = I-rrddd
- yo! (Hess, grad? f(("",
(27)
Let vy* [esss, grad [ yy [5*), compute the local coordinate 17" of 1j" by converting the following equation
H 4 [n" gy ((="."")) '')[1",
(28)
24 we have frs = E, ( (ui, (ui, uz)m") (v*).
into local coordinate. From
By I6 and
we obtain
2 J (x", ,," "=' Dagrad (1=",
lu",,v [,") Σ D'"essle"."""'"" (2,)0"")
HE2.i (u uz)=" E2,(1*).
Σ
(29)
Oug
15

---

Published as a conference paper at ICLR 2025
It follows that 28 is equivalent to
2
0E
(uj "))
(u], uz)o".
(30)
Ouz
Oun
We can compute the right hand side of (7 in the local coordinate in 29 and 25
(6" grad f (x", )0" a)
(8", oograd_(xx" (x=", In ba
01 (ui, u2)
8" Σ
E1,(0²)
Ou2
061
8" 01 (x,))
(ui uz)n")
Ouz
The left hand side of 27 can computed based
20 and
21
which result in
2 (ui u²),
A = -92(us)
(31)
Ou2
051 (ui, u&),
B (u()
(32)
Ouz
C' (1())
(ui, ui).
Ous
Furthermore, the symmetry of the Hessian matrix implies that
86 B 0 un f(u) un)) (2(25)
(u) ug).
(33)
Ou,
As consequence, (30 implies that 17* A 1 BT8 and
(8", (T"" = ( (1
(ui uz)n
Ouz
Therefore 27 holds.
C IMPLICIT FUNCTION THEOREM ON RIEMANNIAN MANIFOLD
We shall state an implicit function theorem which allows one to understand why (x", y²) is local minimax point in the manifold case. This theorem implies the existence of solution (x, h(x)) sufficiently close to (x" (=")"") ) s.t. grad,, (z, h(z)) = O. Moreover, due to the continuity of Hess, on Mi x .M2 and the continuity of h near x², - (x. h(x))) is positive definite, provided that is close enough to x². As a consequence, h(x) is the unique strict local maximum of y + f(x y) in this neighbor of DSE.
Recall that the set of continuously differentiable vector fields on M2 is denoted by (MM)). The Riemannian connection on M2 is denoted by V,,
Consider a parameterized vector field & defined at each x Mi with ((x,)) E X(M2). By definition, for each (I, E M1 x M2. {(x,v) E MyM22 and V,E(s, v) is a linear map from M2 to M2.
Theorem C.1. Assume & is continuously differentiable (x",8") E E be solution of
open E C Mi M2. Let E(x, 0, (x. F.
If VyE(=",00 ,y) ) is invertible on TT- M2 there exists an open set U1 x U2 C. E and an open set
Wi C Uj such that
Vx E Wi, Fl E U2 s.1. E(x,y) = 0.
Let the unique h(x),, i.e. h: W1 + U2. such that
y" h(x)), h(x,)(=)))= =0, Va Wi.
16

---

Published as a conference paper at ICLR 2025
then h is continuously differentiable on W1. Let 8 E M1, and denote the tangent map of h at x² by Dzh(x"), we have
-V "-)=""""">-__-"" DzE(<" " ([)]
We can prove this result by using a local coordinate chart around the point (x", y²) to represent a smooth vector field, and then adopt the proof technique of the implicit function theorem in Euclidean space (Rudin 1976 Theorem 9.28).
D PROOF OF PROPOSITION 2.
We verify the intrinsic definition DSE for (x",""). For the first-order condition we compute based on Boumal (2023 Proposition 3.61),
(rf(r.y) ATy. grad g v) (T (Ar b).
(34)
From the identity involving the pseudo-inverss ATAA* AT, we deduce that ATy As b & Range(A) A), we have Ax* - b & 0 and therefore y" is parallel to the (non-zero) vector Ax* - b. From above, the first-order condition holds, i.e. 0,ʃ(2z, (x" .y"" 0. grad, [( .y"" =
From
34 we first verify the second-order condition compute for MyM2.
From Boumal 2023 Corollary 5.16), we
Hessy (x, v)[n]
(I yy ('_'a( v), n))
(I y- + nu (Ax b))
(y, Ax Ax b)
We verify that -Hessy/ (x=", :y") is d.p, because for non-zero 1i¹ Ty- M2, have || > 0. Moreover, Ar b + 0, therefore
(-Hess, fx=", , )rr",,n">>> (v",xx" b)(ln> |Ax b |||171112 0.
We now check the second-order condition 33. It is clear that sx, v) = 0. We next show 5* - grad fx= ","",""")) [5*]]] is an injection from T..M. 1 to Ty We compute from
grad f(x ; yf 15
Σ $dd.
0z, grad f ) = -T- -
8" * O, then A8 * 0 because Ker(A) = {0}. But Ab is not parallel to y", since y² is along the direction Ax which is not in the range of A. This proves that grad fa" y [88] * 0 8* * 0.
The above injection property implies that for + 0, 17" = grad? fa" y [8*) * 0. As
f y²) is d.p, we use the symmetry of the Riemannian cross cross-gradients (see Proposition 3.1 obtain: If 8" * 0, then
88* [ - -gradd (Hess, grad?
gradey//lx* [((" "/=l"(""))))))"" (5(()) (1)"; Hesss (x= "-n"~"(())) 0.
Therefore 3 holds.
E PROOF OF PROPOSITION 2.2
As in the proof of Proposition 2.1 in Appendix D we have
(Ax f y) AT K.T Ax, grady v) (1 yy )Axx -b). 6).
(35)
To show the existence of DSE, we shall construct solution of the form (x, vi). where fr, v.) 0.
We consider 3/2 = (Ax - b)/ Ar bll so that grad,, f v²)) O. We verify that Ker( (A) = (0)
implies that AT is p.d. It follows that A+ = (ATA) AT, and that the condition d. (z, vit) = 0 is equivalent to
AT (Ar b)
KATAr
+
(1- xe| Ax b1]) A+b.
Ar bll
17

---

Published as a conference paper at ICLR 2025
For (2","* (x Vz-) to be DSE, assume x² = cb and want find a R such that F(K, c) = c(1 - xi KiIcAA b() - O.
We next apply the implicit function theorem (c.f. Theorem C.1 show the existence of с close to 1 if is close to O. It suffices to verify that dc (0, 1) based on
From Proposition 2.1 we have F(O, 1)
OF dc (n, c) = (1- [1-xk]caad [1-k]]cAA+o bll) + c (AAto, (AAtb,cAAT) CAA-- b)
|cAA+b bl
This suggests that there is an implicit function defined on an open neighbor W1 of 0 (0 E Wi) such that F(xs, h(k)) 0. Moreover, h()) 1. We next check that if hhxx) for some range O K < Ko. then (x", y²) defined in the statement a DSE of f. Since (35) holds at (a* yy" suffices verify the second-order condition DSE.
We verify the second-order condition (2) by using the same proof as Proposition second-order condition (3). first compute from 35
2.1
To check the
= grad 2 sy f fa=" "00 = 3e. f (""),""0;;" = (1 - y" AA8"
idd
By following the proof of Proposition 2.1 then compute S(x) = (8", |esss grad (Hess,f) grad grad., fl(==1"")""0""""",," {8"]))
A6 1 (n' Hess, [ - "=²")²(²")))
1
= --||A0 +
||A bll |7,1
It is clear that S(k) is continuous function of k because x² = h(k).Abb and y² = (Ax" Ar - bll are continuous with respect s. Moreover, S(0) from the proof of Proposition
2.1 (due the injection property of 8* f y² [8*)). Therefore there exists Kig so that (i)) for < K < Ko (i.e. holds).
F
PROOF OF PROPOSITION 2.3
We verify the intrinsic definition of DNE for (x",y") For the first-order condition 7 we compute
0z y) = AT AT (Ax+y= + b), grad [ y) = (7 yy + y b). b)-
(36)
From the identity involving the pseudo-inverse ATAA+ AT, we deduce that AT +1² -b) 0. As & Range(A), we have Ax" of 0 and therefore y" is parallel to the vector Ax" - b. From above, the first-order condition in holds.
From (36). we next verify the second-order condition 8 It clear that 02 fz, = AT A p.d.
From Boumal 2023 Corollary 5.16), compute for 17 M2.
Hess,, far y) [n] = (1 - (00.grad,,
= (I - ( (un + ny (Ax
)Ax + y b))
1,(1 - (y. Ax + 1 b))
= (v. Ar - b)) (-n).
We verify that Hesss, fx" y is d.p, because for non-zero 17º M2, we have || > 0. Moreover, Ar - b + O, therefore
(-Hessy """.""") "n7"">">>>>> (v", Az" b)]ln" ||A= b| 0.
Therefore 8 holds.
G PROOF OF THEOREM 3.1
The proof is illustrated in Figure 3 which contains three main steps: (1) identify a set S where the local update rule T is well-defined. (2) adapt the proof technique of the classical Ostrowski Theorem to identity a local stable region S, and pull it back to the manifold (i.e. S&). (3) relate a Euclidean distance in the local coordinate to the Riemannian distance S establish the linear convergence.
18

---

Published as a conference paper at ICLR 2025
(a)
(b)
O1 x O2
F1 x
tof,
8
O1 x O2
O, x
Figure 3: Local convergence of a deterministic simultaneous algorithm. (a): The update rule T on the manifold Mi x Ma induces local update rule T in the local coordinate system, defined by a chart (O2 x O2, P1 x p22) around (x", y²). (b): The induced update rule T is defined in the local coordinate on the set S around (uf, uz) = P x p2 o (x", y*). It contains a local stable region Sz.
Preliminary Let x 92. Let us consider the set S = (O, x O2) (0, x 02) and its local coordinate domain $ = (9) (5) C O x Og. By definition, (ær, y) ES 02 x O2 and T(æ, v) E O, x O2. Therefore the induced dynamics T is well-defined on S, i.c. V(u1, u2) E S,
T(u1, u2) (T (u1), (wz)))
Note that S and S are non-empty open sets since T is continuous (by the continuity of the vector fields E1. E and the retractions R₁ and R2) and (x" v²) is fixed point of T.
Local stable region We aim identify local stable region Sg C S around (u u.) (the local coordinate of (x", y² D), so that if (#1, u2) Ss. then T(u u2) E Ss C 1 Let Sg 9 (S,). and assume (z()), (0)) Ss, then by recursion (())(((t)), (2((()))) is always well defined since the sequence (zr(4,, v()) E Ss C S.
To construct such a region, the key to verify that the spectral radius p of the Jacobian matrix ('u",, u²) is strictly smaller than one. In Appendix G.1 we verify that the eigenvalues of T'xx", yy) are the same as ('( uz). Therefore according to our assumption, P = p(T (-".'"""" < 1. From the proof of Ostrowski Theorem (Ortega & Rheinboldt there exists norm
1970, Section 10.1.3), for an arbitrary > 0,
lle on Rd X 12 such that
[T' ut)lle p
Furthermore, due to the differentiability of at the fixed point, there exists 5 > 0, and S3 = ((ui, [l,,,, u2) (2), < 83 S. such that
[T(i,, w2) (ui, mlllle (" mallle e/2) u2) (ui. uillle (p ( u2) - (ui, ug)ller V(ui. u2) Ss.
(37)
Let's choose so that + < 1. It follows that the open set S. = (Ss is a local stable region. Furthermore, we can identify an open geodesically convex subset of Sg, on which Riemannian dis- lance equals to geodesic distance. This set is written as Sg. It contains (x", y and is homeomorphic ball, i.e. without any hole.
Locally convergent with linear rate p From 37 if (2,(0), (2)) E S,, the sequence (un (2), u2)) stays in S and converges to (ui, ug) as > 00. As 4 p1 x 42 is a con- tinuous bijection (homeomorphism) from O X O2 to O x Oz, we have equivalently that if (z(0), y()) E S3 = p --10--s)) (Sx), the sequence (z(t), v()) will stay in S, and converges to (x*, y²).
The linear convergence rate in the local coordinate system in (37 can be used to control the Rieman- nian distance d(l) between p()) = (x((),,(() E Sg and p = (=") E S%. Since p()) converges to p as t oc, it suffices analyze large enough for the convergence rate. Without loss of generality, we assume next that p(t) E S for any t 2 0.
Let (t) be the set of piece- wise smooth curves restricted on Ss with an initial point p(t) (at time 0) and a last point p" (at time 1). Each curve y E (t(()) is composed of a finite number smooth curves, indexed by k. The k-th smooth curve " is defined on some time interval [sk, sk+1] [0. Then we have
E 1+++
d(t) = inf
(s
(=(7))eETa(1) &
19

---

Published as a conference paper at ICLR 2025
where || -Ip is the Riemmanian metric p M. As Sy is geodesically convex, the Riemannian distance d((t) can be attained at certain geodesic curve E [t(
As the closure of the set Ss is compact and Sş is convex, there are two positive constants 0 < A S Be, such that
A..llp(((()) - =(p")ll S d(1)
-
(38)
relevant proof on how to obtain A,,5 and Be, is given in Hu 1969 1969) (Chapter 3, Lemma 3.3].
From 37 we have
(p(p(()) - ((p")l I ( (((((()))))))))))))))))))))))))) <(p")
(39)
Combining (38) and 39 we obtain the constant C = Be,8/Ae such that
d(t) <
We remark that in general, this constant can also depend on the initial point p(0).
G.1 SPECTRAL RADIUS OF JACOBIAN MATRIX IN THE LOCAL COORIDATE
We next compute the matrix (u wz), and then relate it to Tx ,y"). This computation also tells us that the tangent map of T at (x", ,y") equals T' ,y²".
First of all, we specify the induced dynamics T of T by using the local coordinate representation of the retractions R, and R2 near the fixed point (x: y²) Let (O) O2, 91 (22) be the local chart. Since a retraction (Absil et al., 2008 Section 4.1) is a smooth function from the tangent bundle of manifold to the manifold itself, we can identify (similarly on B2 for M2) such that I E O2 and (11+(f1) E O1 if &1) ) E B1 This set B₁ can then be mapped to an open set B1 C Rd x Rd,, using the local chart of the tangent bundle (Absil et al. 2008 Section 3.5.3). On this subset B1, we can define the local representation of R2 as follows
open subset B₁ of the tangent bundle of M1
R1 Bi + Oi, Ri(w1, =P L. (PrT"
(un)()))
Similarly for R2, we can define R₂ B2 + O2 on an open set Ba R2d2 Rgd2 From the above definition of R2 and R2, as well as the local coordinate of &1 (x, and (2 y) (as in 17 18 obtain the induced dynamics
we
R (u R2 E2(u1, w2)) )
T(u1, U2) =
(40)
which is well defined on the non-empty open set (2) E Ô, x Óz Ei uz)) E
B1, (u2, (u u2)) B2).
From 40)) we can compute the Jacobian matrix T'( uz) using the chain rule. As Ei ug) = 0 and (2 ug) O. we have
Ia, dot (u², uz)
8E1 (u), uz)
(ui uz) aE, Id, + auz
DE1
T'uui, wg)
Tus
(41)
8E, ou;
(u uz)
since the retraction by definition satisfies
0R1 Su,
(u 0) Lai
2R (uj, 0) La (similarly for R2). dee
We next verify that eigenvalues of the matrix (I are the same as Tx y²). Let 8*
Σ, 5t Fx,((") Mr, 1f" =E, ni F2r(v") E Ty My, then following the same argument
20

---

Published as a conference paper at ICLR 2025
in 24
and 29
have
d1
Vafi(2', 12100=1
(u uz)ō" Ei,(
Oui
d1
d5i. (u1, ug) F(,(("),
Ouz
==1
de
@E2. (ui, u2)8" E2,((²).
(2f2("",'"'100
Σ
Oul
j=1
du
@Ee. Ouz
Vuf2(2" 1 [n =
Σ
(u) u2 u2)r7* (v))
From the definition of eigenvalue and eigenvector pairs, these four equations indicate that their eigenvalues are indeed the same. They also indicate that the tangent map of T at (x" y²) equals to (9). which means that the tangent map of T at the fixed point does not depend on the choice of retraction.
H PROOF OF THEOREM 3
We first rewrite (x 5* + M, local coordinate chart with T' ("G (() Idu+da + YMM
From the definition of Mg
and the connection between T and T in (I) we have
(ui)) C
- B -rō2(u;)
M
where the matrices A,B,C are defined in 26 Furthermore, Mg and My have the same eigenvalues.
We next show that the real part of each eigenvalue of My is strictly smaller than zero. From this, y (M,) > (M,) O. We first check that if < 7 > (MG)) the spectral radius of T' u²) is strictly smaller than one. general,
= Ag + iλ is a complex eigenvalue of a matrix
with Ao < then 1 + 7d is eigenvalue of the matrix / + Y. To ensure 11 >l 1, it is
sufficient that O < 7 < 7 (M). This is because [1 + 7/
+ 2 + 7 228 + + x < 1 holds
0< 22o/ + A2)-
To analyze Mg we could not apply Li al. and ÿ2 (u²) ) are not identity matrices. We consider a matrix which similar to M so that they have the same eigenvalues,
2022
Lemma 5.2) directly since the local metric Ø (ui)
C -B
-rA ).
Mg
(42)
7BT
where
C (11))-1/22 g1 (11)-1112
= (1(w)) B (2((()))-11
Ā (2(1))-112 A (2(U5)-111
Under the assumptions of Theorem 3.2
we check that the following conditions hold:
is p.d because A is p.d.
+ BB- is p.d because C - -B- is p.d.
* 7 > CC]l/Ammn(AA)
Indeed, we can relate these conditions to the following intrinsic quantities on the manifold Mj x XM2 by following the proof in Appendix
21

---

Published as a conference paper at ICLR 2025
Let A Hf yy", then A and A have the same eigenvalues.
Let B grad fx= ff 1²), BT gy f (a" y²), then C+ +BA DA-'BT and C BA 'B have the same eigenvalues.
Let C = Hess. ((=", y²), then C and C have the same eigenvalues. As C and C are symmetric, ||C|| max; ( [C) ||C|]- Therefore, the condition |||| Ammn (A) is equivalent to 7 CCI/ Amin (mss(A)).)) (A).
H.1 SPECTRAL ANALYSIS OF Mg
To analyze the eigenvalues of Mg. we use the next proposition which adapted from Li al. (002 Lemma 5.2) with refined range of r. For two real symmetric matrices A and B, we write A 2 B
B is semi-p.d. We write > B if B p.d.
Let us first introduce working assumption which will be needed several times. Assumption H.1. Let A E Rmxm, B E Raxm, C E R such that A and C' + BA- B are positive definite.
Proposition H.1. Under Assumption H.I and v > [[C]I/mmin (A), any eigenvalue X A + iA (with A E R, X1 E R) of the following matrix,
-C -B TBT
-TA )
M
satisfies An < O.
Proof. We show that Ao 2 0 will lead to a contradiction, by following the proof of Li al. (2022
Lemma 5.2). Assume that À is an eigenvalue of M, i.e. det(AT - .M = 0. To compute det \/ M),
note that \/ + A is invertible since Ao + T positive definite (r A is positive definite and À 2 0). By the Schur complement, have
C+
B TA+
det(Al - MM det
-TBT
det(AT + T A)det( H
where H()) = AI B A)- BT. As AI + 7A invertible, det(AI M) implies that (A)(H(()) = 0.
Let the spectral decomposition of be UA with orthogonal U E Rmxm and diagonal A^ diag( (aag(A1(A)) (A), Am E T Rmxm Then
M+++
with B BU and D = diag(d1,
ddm) where
Ao/T + (x(A) - iAs/T dj A/T + (A) (No/T >x (A1/7)2²
1 15 <.m. m.
follows that do |C the real-part of H()) is
Re(H(A)) Aol + C (R p.d.
(43)
This is contradictory to the fact that det (2)) = 0 (i et al. 2022 Corollary 10.2).
On the other hand, if < Ao 5 ||C]| and \ + O, we consider 3 E R.
TB Im (m(H(A)) Nol + BRe(D) + + (A1 Blm X
TB
(e)H
X
(No +C
(44)
where = diag(Si, ... fm) with
20/T + (A(A) -
f (Au/T du (A)) (>1/7)2
1
(45)
22

---

Published as a conference paper at ICLR 2025
Take 3 = Amin (A), then fo 2 0 for each & S m. The condition (Amin(A) ||C'| implies that (Ao + +r3) + p.d. and together with (45). we have (44) is p.d., so it is contradictory to the fact
that det( (A)) = 0 (Li et al. 2022 Lemma 10.1).
Lastly, 0 - À - ||C|| and x = 0, we have from
H(N Aol +C+ -C+ BDBT
(46)
20/T with dk \0/T+An(A) AE(A) (Ae/TAA((A)AAAA)
It follows that (A)Ae()
Do/T
Xe(A)
H(A) Aot +C+ (
20/T
BA-+BT
"man (A)
=(1 Amin(A)
Xo/T
(C BA BA) + 2o/T
C AoT.
Amin (A)
As r > ||C]]/Ams (A). S Ao S ||C||| we have that <
Aa/7 Amj < and that / + FAmin C is p.d. i.e. we find that again (A) is p.d which is contradictory. In conclusion, do < 0. L
H.2 LOCAL CONVERGENCE RATE OF 7-GA
We the next result obtained in Li al. (002 Lemma 5.3) control the local convergence rate of T-GDA. It controls the spectral radius of the matrix + yMg on a specific range and 7.
Recall that Ig = max [1 A II, [B] [[C]] and By = minn [.g. Amin BA BA-1B))).
Proposition H.2. Assume (x", ,y) DSE of C². IfT p(I + +M,) <
2hg
and y 4rl.g
we have
Amain (A)
Ag
16
Proof. Let L max AII. BI| [[]] and Ps = min(L, L,, Amin ( C BA BT)). ). We verify that Amin (A) = Amin (A), L Ly and Hy Maz From the proof of Li et (2022) Lemma 5.3), obtain directly the upper bound of the spectral radius of I + yMg. related to I. and flz.
I PROOF OF THEOREM 3.3
The proof is based on Jin et al. 2020 Proposition 26) and Zhang et al. (2022 Theorem 4). To show the valid range of T, consider matrix M, which similar M, (defined in (42)
M,
0
- C -B
) (
T
7BT
-
0
VTB
-VTĀ
)
( ! )) -VBB -
I
-TÀ
VTB
)
C
B
0
-C
We verify that for any - >> 0, the eigenvalues of M, are strictly negative, therefore one compute 7 (M, to set the convergence range for 7
7 >MM)) 7 (M₂)
As in Daskalakis & Panageas (0188 Lemma 2.7), the Ky Fan inequality implies that the real part of each eigenvalue À of M, is upper bounded by the maximal eigenvalue of (M, + M2)/2. We verify that indeed Amar + .MT)22 /2) < 0 because A and C are p.d., and > 0. Therefore, the real part of X is strictly smaller than O.
To analyze the convergence rate of 7-GD at T = 1. It suffies to analyze the spectral radius of Mg. We next apply the proof of Zhang et al. (0022 Theorem 4) to the matrix Mg- It implies
that if 7 = (2(2L2) with = min( Amin A) Amin
C)) and L = max(]] A|J | [| [[]]), then /22 (..( The eigenvalues of A, BBT and C are the same as A, BBT and C.
p(I + >M,)
thus μ Py and I. I.g. Therefore obtain the spectral radius upper bound P (4T.2)
23

---

Published as a conference paper at ICLR 2025
J DERIVATION OF DETERMINISTIC 7-SGA ALGORITHM
The 7-SGA algorithm modifies the vector field E(x, y) = (-ô(z, rn( y) T-GD using the anti-symmetric part of the Jacobian matrix of {(r,y). As 6(.,v) fxr, y) and nf grad f y), the Jacobian matrix is the following linear transform on T.Mı x My (which is natural extension from the Euclidean case),
C(a,g) v) (x, -
-B(x, v)
)
Hess, (z. y) rgrad"
yz far THess, (z, y)
grad
J(r v)
(47)
Here we introduce the notation Á, B, C in 47 to simplify the equation. The T-GGA update rule is obtained from ||
[ y)
(T
5(x,8) v) +
((x,8)
T ++1 1
0
BB(
= =((,,)) v) +
E(x,, v)
2
BT(x,
(( - )
7 +
-TB(n]
)} (u..v).
+
2
BBT
J.1 PROOF OF PROPOSITION 3.1
We aim to show that the correction term, which is proportional to (rB(r) [T]))), is orthogonal to the 7-GDA direction (-6, each (æ, y). under the Riemannian metric on the tangent space
T,M1 x T2M
follow the proof in Appendix B by using local coordinate chart (O₃ x O2 11 x (P2) around the point (z, y) rather than "²)" As in (17) and (18). this coordinate chart maps ò 0zz y) and 17( v) to their local coordinates 8(u1, U2) and f711 uz). It also induces a canonical basis {Ei,(()) lisa, on
T TrM1 and {E2.j (y))isd hidd, on M2 By the definition of cross goos-ggaadents,
B(x,,)ln(r, y)l = Dygrad_fft v)ln(z, v)]
Dyy(0, ()(n(
= -E ( 08;
(u1, (2) uz) Eia(z).
Duz
Using the Riemannian metric ÿ1 represented in the local coordinate as in 19). it turns out that
w)] 0(z, v))= ((
5(u1, ()
05
(u1, u2 u2) wa)
(48)
Ous
Similarly we have
θî
(BT (1, v(,,
7(1,, u2) T2 (2())
(w1, (2)
(49)
Oug
We conclude that (48) equals to (49
because as in 32
33
05
Onj
T1 (u1)
(u1, (2) = (2((22) Dui
(u1, Uz)
Ouz
K PROOF OF THEOREM 3.4
Since f is twice continuously differentiable, we apply Theorem 3.1 to analyze the induced dynamics
T. (where T is the update rule of Asymptotic S-GA). Following 40), we obtain
R1 U1, - 5 11 (T+1)r
r (u1, u2)
T(u,, U2)
Bug
(50)
R₂ (u2, 7T u1, wz))
Note that in the original SGA rule [Letcher et al. 2019 Proposition 5) the transpose of J(x.))-JT is considered since their definition of has sign difference compared to the J in 47
24

---

Published as a conference paper at ICLR 2025
From 50
compute the Jacobian matrix T (ui ub) = I ?MM where
as
(ui, u2) 06
[ui: un) (u,, uz)
(T + 1IT 1)T
06 an
(u7, uz)
8n 18g Bug
[u uz)
)
M
T Dui
dui
29
(2f, U2)
Shez Bn
11
This can be reduced to the analysis of the eigenvalues similar matrix M, as in
C
-B -TÀ
1)T - -BBT
BA
M, = BBT
+
2
0
As in the proof of Theorem 3.2 we verify that M, and the M, in 14
have the same eigenvalues.
From the assumption of Theorem 3.4 we verify that min [| + /BBT [) m//mm (A), and
0 < 0 < 1/Amaz (A). We can therefore apply Proposition K.1 (see next) to conclude that the
real-part each eigenvalue of M, is strictly negative. Therefore for 0 < 7 < (M,). Asymptotic 7-SGA is locally convergent to DSE with rate p(T + +,,)
Before we proceed analyze Mg. we remark that the non-asymptotic analysis of r-SGA remains an interesting open question. Indeed, if we want to analyze r-SGA beyond the asymptotic regime (e.g.
r is small), one needs to consider this induced dynamics R2 U227 7 TÝ) 14 =+1 an 8) (uz, for Bus
the variable U2. The analysis of the spectral radius of the Jacobian matrix T' uz) is harder as one could easily adapt the proof of Proposition K. to this case.
K.1 SPECTRAL ANALYSIS OF Mg
The following proposition is adapted from Proposition H.1 to analyze the eigenvalues of Mg.
Proposition K.1. Under Assumption H.1 min( C
BBB C
and μ 0 न with 0 S 0 z
Amina (A)
1/ 1/Amaz (A), any eigenvalue D + ii (where do E R A E IR) of the the following matrix
M = ( -C -B
) TBT -TA
(T+
1)T
-BB
BAT )
+
2
satisfies Ao < O.
Proof. We show that An 2 0 will lead to contradiction. det(Al .M) O. By following the proof of Proposition H.I
Assume that À is an eigenvalue of M, i.e. we have
C OBBT + +
B - OBA +A+AI AI
det(AV - M) det
-TBT
det + + Addett((H()))
(51)
where (()) Al C OBBT + (B (BA))A/TT BT, As XI A is invertible. det(Al - M) = 0 implies that det(H( = O.
Let the spectral decomposition of A be U'AU', with orthogonal U E pmxm and diagonal AA diag(A (A), ... Am (A)) E mm Then
11 = M BDBT,
(52)
with B = BU and D = diag(d1 (1. -.. ,dm) where
1 - (A) (1-0)c(A)) >o/T *x(A) - -idi/T
d, \/7 + (A)
1sksm. m.
b0/T++N(AN) (A1/7)2²
follows that if > min(IICII.IIC
(I), the real-part of H(A)
Re(H(A)) AO. + 0BBT (iee Ao + C' 0BBT p.d
(53)
This is contradictory to the fact that det( (+)( 0 (Li et al. 2022
Corollary 10.2).
25

---

Published as a conference paper at ICLR 2025
On the other hand, if0 S Ao min( and A1 + O, consider for 3 R. Re(H(A))
TB (m(HH()) C ())(D) BT + TB (A1 (D)
A
(Ao ++ +BFB
(54)
where F diag(f1. fmm with
Au/T+ (A)) - = -1- (No/T + (A))² + (A1/T)2
1sks m.
(55)
Take B = (min,(), then fK 2 0 for each h: < m. The condition Timin (A) > min( |C
BBBTI) implies that (An + +T8)T + C + 0BBT p.d. and together with (55) we get that (54) is
p.d., so it is contradictory to the fact that det H (A)) = 0 (Li et al. 2022 Lemma 10.1).
Lastly, 0 S do S min([|C[], ||C + (B and Å = 0. we have from (33
H(A) Ao C + 0BB ADBT
with d2 (A) 1-0A((A)
A4) Ax(A) (A))at 2 (1 ()x( (x(A) Amen (a))
An/7
(o/r+)x(A)
As r > min'||C[],, ||C + OBBTTI)/Amnn (A) and S Ao I min([[(]), ||C + (BBTT) we have
0 S Aman (A)
An/T < 1 and it follows
H()) 2 Ao OBBT (1 A0/T Amin(A)
BA- BT 0(1 Ao/T )B
Amin (A)
(1 )oco) (C BA- + Ao(coC cBBBBT +1)
2 (1 )oca) (C + BA- BT)
(56)
where Co
[A) The last inequity 56 is due A 2 0 and the condition 1 >
cp min[[]C']] ||C' + (BBT)). They imply that An + BBBT + f) 2 0. As 1 - Apco E (0, 1].
(56) implies that (A) is p.d which is contradictory. In conclusion, Ào O.
K.2 LOCAL CONVERGENCE RATE OF ASYMPTOTIC
The local convergence analysis in Proposition H.2 provides an upper bound of the rate p(T + Mg))
of 7-GDA. This section extends this result to Asymptotic 7-GGA. We aim obtain an upper bound of the rate p(1 + M,,) which is smaller than that of p(1 + +M,)
The following lemma analyzes the eigenvalues of M, for Asymptotic -SGA when p = 0 7(++J-- refinss the eigenvalue bounds of Li et al. 2022 Lemma 5.2) on Mg of r-GDA (when μ 0). Lemma K.1. Under Assumption H. T O, and 0 S 0 < a/amaz (A), any eigenvalue Ag iii
(where do E R, E I.) of the following matrix
-C B
) -TA
BBT BAT
M
+0
TBT
0
satisfies
a. 1 S VFVI- 0) Oxmin (A)
b. 1 # 0, we have do S -X4 with A_ (Amin (A)r min( + 0BB ()).
Let T min[[[C]]] C+ABBT with 0. A O, we have No - -X, with X4-
Amnin. (A)
min (Amin (C + BA- BT). min[[[[]], ||C + 0BBT a))
d. Let L = (| [B], CC - OBBT)) [)). 1fT 2 1, we have X + X < M < 47
Proof. Assume that is an eigenvalue of M, i.e. det(A/ M) 0. If AJ + 7 is invertible, we can compute det(Ar AI - M) using the Schur complement (51) to obtain
det(AT M) det(AT A)det(HH(H)))
26

---

Published as a conference paper at ICLR 2025
Let the spectral decomposition of A be UAAUT, with orthogonal U Rmxm and diagonal AA- Then H (A) can be rewritten into (52)
Part a: If A1l > VTVI- Admin (A)) BlI, then XI + TA is invertible since A is. Therefore det dei(H (A)) Consider
Im (A)) =I+ Blm D)
A1
A
1
1- (Ax(A)
= 1 -Bdiag
BT ksm
(No/T {x()))² (A1/T)²
1 72
2
T (1 0dmin (A)) =I
0dmin (B))
7 X7
X7
As A > VT mmmi BI), we have that I - X7 (1 - Ammin (A))BBT is p.d. and therefore
X Im (()) is p.d., which leads to contradiction.
Part b: Assume Àg > 24. As A1 AT + F.A is invertible and det (((() = 0. Following (54).
we consider
TB
Re(H(()) + A1
Im H(A)) = (Ao + C OBB + BFBT
Take B = 1 (Amin (A)T + min CC |C + OBB II)) > 0, then BFBT is semi-p.d (positive 27
semidefinite) because each f& in (55) is larger than zero (fa 0). Indeed, V1 S k m.
Ao/T + *x(A))) 8 >> A+/T + (A) /
Amin (A)T min |CC (BBT)) B (A
2T
= (A) Amon (A)
Furthermore, either (Ao + rB)T + C or (Ao + T / + C + 0BBT is p.d. due to the following:
If [| < |[C OBBT], we have Ao + T > because - + + = ||C*||-
If |[[|| > |[ + OBBT|I we have do + rB > |[C + OBBT| because -X+ + T3
[C |BBBT
As consequence, Re(H + T8 Im(((A)) is p.d. which is contradiction. Therefore do S -
Part From Proposition K.1 remains p.d. since
we know that do < 0. If A = and 0 > do N4,, Aol + 7
ToT + 2 (rAmin (A) + No) (min(|]C)}, ||C OBBT +a XL)7 semi-p.d.
Therefore XI A is invertible and det( (A)) 0. Following 52 we have
1 - (A)
H(A) = T + C + 0BBT + idiag
ABT kSm
Ao/T (M(A)
No/T OAZ(A)
= +C BA- BT Bdiaa
ßT
(57)
(Da/T + (a(A))AA(())
ksm
(1- (A)()))
- + BT Bdiag
DT
(58)
(>o/T (A)))(A((A)
kSm
>C+BA- BT
CC+BA- - Xmin (C + BA- semi-p.d.
As consequence, (()) is p.d. which is contradiction. Therefore An -X--
27

---

Published as a conference paper at ICLR 2025
Part d: Note that | - 0| 1. For any (x. E R x R", compute
x )
Cx By +
M
=
T BTx Ay
= || - Ca By 0
| Ayyl
S (B
(yyl3)
27 |||
S 2( 011+775 + (0) [bl < 2TL. (
Therefore |M S TT and Xe + X ~ M v 1.2
From Lemma K.1 are ready to obtain upper bound of the local convergence rate of Asymptotic
T-SGA. Recall that Lg = max( ||]] [B |C +BBBT] |]) and μs = min Ls, Aman ( (C- BA BB))..
Proposition K.2. Assume (x", vy)) is DSE of f E C². If 2 Xonen [A] N.a.
2L, and ITL.' we have
p(1 + +M,)) 1
16
C + (B and Me = min(L, Aman (C+ BA- We verify that Amin (A) = Amio ()). L= L, and Hr Ug. Let X do + iλ be an eigenvalue of M,. It follows that we only need to show that [1 + > S 1 - TorL.
Proof. Let L = max(|I =
To apply Lemma K.1 we denote A = A. B = B and C = C. We rewrite that T Tmmin (4)
min [[]], ||C + BBB ()) + with a 2 2L min(I|C'I. ||C + (BBT]) > O. There are two cases
to verify:
Case d1 0: we have Ao -,p. Since Tmmin (A) > L, we have X min(TAmin( (A), Amin BA BT)) min(I,, Amiin, (C BA 1 BA))
Mlg. Thus
Ao S 44 and + 7>o I 1
1 Mx. On the other hand, 7 2 2 and do 2 Lr, thus
1 7Ao 2 1
1 2TL 1/2. Therefore [1 + +7 $ - 1 S - 16TL.
4F1.
Case A1 * 0: we know that L < Ao S -14 = - and |^g S VFL. Note
that a TAmin (A) - Cin[ |C + (BBT II) Tdmin (A) L and by assumption
L Idmen(A) Thus a 2 ZAmin (A) It follows that
2
1 2 (1 yAn)
+ クスン
a
+
2
a
8rL
16T
Amin(A)
2
Amin (A)
Aman (A)
+
<
16L.
32L
16L
Therefore |1+ S V
Aman (A)
Amann (A) 32L
<
L
1
16L
167
L
167L L
L COMPUTATIONAL EFFICIENCY OF 7-SGA
We first discuss the computation of B [n) and [J] when Mi (resp. M22) is an embedded sub- manifold of R (resp. RC)). We then propose linear-time computational procedure using auto- differentiation when M, is Euclidean, which is applicable to orthogonal Wasserstein GANs. When Ma is also Fuclidean, this procedure is equivalent the one proposed in Balduzzi et al. 2018).
28

---

Published as a conference paper at ICLR 2025
To compute [n] at (z, y), first fix n n(x,v) TyM2. From the property of embedded sub-manifolds, we use identify a tangent vector d E Ta with vector 8' (8))g R (resp. M2 with r/' = (n)) E IR.)..
This allows one to compute the cross-gradients in the embedded space, by B (z, v) (x,
(r, = (((grad, (x, u)Y . ,1))) E R <>
Note that (grad, (2, (zz v)), nyyy is computed on Red with metric induced from TyM2.. Assume that its computational time is ((2)) for each i. Then it takes O(d2d) to compute B [n] (z, y) in the embedded space. We can obtain a similar cost for B (x.
Euclidean MM case When M1 = Rd, the computational complexity of B(n)(z,)) can be significantly reduced: Vi S di,
Dy0c, g)(nl 0z, (grad, (x, y), n)
Oz. (z, 1),
(59)
Importantly, one does not need to recompute (1/ v). 7/yy for each i. Therefore, the whole cost of B [zn] y) is O(1 + d22). Note that in (59), the term 1/ is "detached".
For [o] v), we "detach" 5 = 6(x,0) E TyM1 and compute
(T Σ 2o, $5dh
Orp"
Da, (a, Σ 15ch
17"=0
This implies that first compute 0z, (n/ (x, y), v).n") for each i as in (59) We then compute its sum with & which takes O(d)). Finally an extra auto-iifferentiation is taken with respect to r/" which costs (dd)). The whole cost of [5] (x, y) is therefore (d1 + d2). In this case, we use the Euclidean metric on R to evaluate (1/ v), 77") rather than the induced Riemannian metric (59).
L.I EXTENSION TO STOCHASTIC 7-SGA
We construct stochastic 7-SGA through an unbiased estimation of the terms in the update rule of deterministic 7SGA. To achieve this, compute 0z, (1/' (.c, w),n")) in (59) using two mini-batches independently sampled from a training set, one to estimate 1/ (I., y), the other to estimate 1/'. Similarly, we use these mini-batches to estimate 1 (Iz y) and 5 in BT [xx, (v.
M DETAILS OF NUMERICAL EXPERIMENTS
In the ttochastic-rrdiies setting, the expectation of (dhaaaa) (resp. (y(()))) is estimated each iteration of an algorithm, using a batch samples of data in the training set (resp. a batch of samples of Z). In this setting, there an infinite number of training samples from the GAN generator o..
M.1 CHOICE OF IMAGE DATASETS
MNIST dataset We consider all the 10 classes. There are 50000 training samples, 10000 validation samples and 10000 test samples.
MNIST (digit 0) dataset Among all the digit 0 images in the training (and validation) set of MNIST, we take 4932 as training samples, 991 as validation samples. There are 980 test samples.
Fashion-MNIST dataset consider all the 10 classes. There are 50000 training samples, 10000 validation samples and 10000 test samples.
Fashion-MNIST (T-shrrt) dataset Among all the T-shirt images in the training set of Fashion- MNIST, take 4977 as training samples, 1023 validation samples. There 1000 test samples.
29

---

Published as a conference paper at ICLR 2025
M.2 CHOICE OF SMOOTH NON-LINEARITY
We aim to build GAN models whose value function f is twice continuously differentiable, based on smooth non non-linearities studied in Biswas et al. (2022). For the discriminator of Gaussian distribution, is smooth approximation of the absolute value non-linearity of the form
a(a) = va² +
6 6 =00
This function twice continuously differentiable since a"(a) 2 Similarly, for the discriminator in the image modeling, we use a smooth ReLu non-linearity
o(a) = (a + va² + 2/22
M.3 DCGAN GENERATOR
We use smooth DCGAN generator to model the images from the MNIST and Fashion-MNIST
datasets, adapted from WGAN-GP (Gulrajani et al. 2017 2 We consider this generator because there no batch normalization module needed (this module is typically used for other datasets such as that the function + Gz (Z)
CIFAR-10). We make slight modification of the default DCGAN
is twice continuously differentiable at any I E MЛ for fixed Z. For this, each ReLu non-linearity in Z (Z) is replaced by the smooth ReLu non-linearity in Appendix M.2
M.4 SCATTERING CNN DISCRIMINATOR FOR IMAGE MODELING
We construct smooth Lipschitz-continuous discriminator with one trainable layer
Dy(() (vy, (wy P()) + by))),
where is the smooth ReLu defined in Appendix M.2 For fixed é, this makes the function y + (Ø) twice continuously differentiable any y E .M2. However, the function ø r> (0) is not everywhere twice continuously differentiable due the modulus non-linearity in the scattering transform. We therefore replace this modulus non-linearity = + |a| Izre + izim by
ト / + 2 + e for each complex number input = 2re + izim. This makes the function P2(0 twice continuously differentiable. As consequence, the function (s., y) f(x, v) is also twice continuously differentiable, which is induced from the smoothness of (I, y) + (Gx()( and y + (o(daa))).
Scattering transform The input ó with dimension d 784 is represented 28 x 28. is pre-processed by the wavelet scattering transform P(ő) to extract stable edge-like information using Morlet wavelet different orientations and scales. We use the second-order scattering transform with four wavelet orientations (between [0, T)) and two wavelet scales. first computes the convolution of with each wavelet filter, then smooth modulus non-linearity is applied to each feature map. This computation is repeated one more time on each obtained feature map and then low-pass filter is applied each of the channels. The obtained scattering features P()) is an image of size 9 9 with 25 channels (I = 25.n = 9).
image of size
Orthogonal CNN layer The orthogonal CNN layer is parameterized by the kernel wy and bias by. The kernel Wy has 5 spatial size (k 5). With suitable padding and stride (two by two), we obtain an output image of size 5 x 5 (N = 5) with J = 256 channels. Therefore the embedding space dimension of by is 2 6400.
M.5 STIEFEL MANIFOLD GEOMETRY
For the discriminators of the Gaussian distribution and the image modeling, part of the parameters in belong to Stiefel manifolds. To choose a Riemannian metric on a Stiefel manifold (which is non -un--ulidd,,n) we use the one in Manton (2002, equation 20). We also use the SVD projection in Manton 2002 Proposition 12) as the retraction R₂ on each Stiefel manifold.
30

---

Published as a conference paper at ICLR 2025
M.6 INITIALIZATION FOR LOCAL CONVERGENCE
M.6.1
SIMULTANEOUS 7-GDA INITIALIZATION FOR GAUSSIAN DISTRIBUTION
Starting from a random initialization of (a, y), we apply the stochastic r-GDA method to build pre-trained model. It is pre-trained with batch size 1000, learning rate 0.0002 and 100 for 50000 iterations.
M.6.2 ALTERNATING 7- GDA INITIALIZATION FOR MNIST AND FASHION-MNIST
The stochastic alternating r-GDA Zhang et 2022) often used in the training of WGAN-GP (Gulaajani et al., 2017), and it can be extended to Riemannian manifold as the simultaneous T-GDA. Starting from random initialization of (ar, y). we apply alternating 7-GDA to build pre-trained model since we observe that the simultaneous 7- G-GDA method is unstable when 7 is small; while its convergence can be slow when 7 big-
During the alternating 7-GDA pre-training, each iteration amounts to perform 7 = 5 gradient updates of y (with learning rate 0.1) and one gradient update of æ (with learning rate 0.1).
MNIST It is pre-trained with batch size 128 for a total number of 2 x 10 iterations. We obtain pre-trained model with FID (train) 7.3 and FID (val) 9.4.
MNIST (digit 0) It is pre-trained with batch size 128 for total number of 104 iterations. We obtain a pre-trained model with FID (train) 12 and FID (val) 18.
MaShion-MNIST It is pre-traae pre-trained with batch size 128 for total number 2 x 10 iterations. We obtain a pre-trained model with FID (train) 17.7 and FID (val) = 20.
Fashion-MNIST (T-shirt) It is pre-trained with batch size 128 for x 104 iterations. We obtain a pre-trained model with FID (train) = 26 and FID (val) 40.
M.7 STATISTICAL ESTIMATION OF THE EVALUATION QUANTITIES
Estimate ff and angle After training, we estimate the f and angle values by re-sampling du ten times (similar to the estimation of FID). To compute the angle for the scattering CNN discriminator, we use instead 8(x, y) = B(o(w, y * P(odata) + by)) - (Ba((w)))))) P()x) + by))-
Estimate FID scores To compute FID (train) (resp. FID (val)), we generate the same number of fake samples as the training samples (resp. the validation samples), and report an average value by re-sampling the fake samples 10 times (with its standard deviation if needed). Similarly, compute FID (test) using the same amount of fake samples as test samples, but without re-sampling.
N EXTRA NUMERICAL EXPERIMENTS
We perform extra numerical simulations on the MNIST and Fashion-MNIST datasets by using the same Wasserstein GAN architecture detailed Section M.3 and M.4] The training on MNIST and Fashion-Min -NNIST datasets are performed with relatively large batch size 512 (as we consider the full dataset, this results in smaller stochastic gradient variance), while the training on MNIST (digit 0) and MaSSI (T-shirt) datasets are performed with batch size 128.
N.1 EXTRA RESULTS ON MNIST
We compare the computational time between 7-SGA and 7-GGA Figure We see that at T = 10, T-GDA converges faster than 7-SGA at the initial stage, but then in sunden the dynamics becomes unstable, resulting in a much larger FID score. At r = 20, r-GDA is convergent and its computational speed is similar 7-SGA (at 5).
31

---

Published as a conference paper at ICLR 2025
(a)
(b)
3541
GBACT
GRALT SCALE
3000
17.5
Figure Evolution of the FIID (test) score of stochastic T-GDA and T-SGA as a function of wall-clock time on the Wasserstein GAN of MNIST. a): 7-GDA 7 10 vs 7-G at 5. b): T-GDA at r = 20 vs T-GAA at t = =5
Table 3: Last iteration measures of stochastic --GDA and --SGA on the Wasserstein GAN of MNIST
(digit 0). We report the f, angle, and FID scores computed at (x(T), (T)). r-GDA is trained for T 2 x 10 iterations with 7 0.05/T. TT. r-SGA is trained longer with 0.01, 5, 0 = 0.075.
GDGA
T-SGA
angle
FID (train)
FID (val)
T(10*)
angle
FID (train)
FID (val)
5
-0.09
-0.26
21
29 (+0.9)
0.02
0.16
12
21 (#0.9)
10
0.09
0.11
36 (20.6)
0.018
0.2
9.3 (20.2)
15 (1:05)
30
0.036
0.4
13
20 (20.95)
3
0.016
0.2
(.0.2)
14 (E0.3)
N.2
EXTRA RESULTS ON MNIST (DIGIT 0)
The results of 7-GDA and 7-SGA are reported in Table For T-GDA, we vary E {5, 10, 30). We observe that when r 30, r-GDA has more stable dynamics than angle stays around positive constant. At because it oscillates around zero over t. On the other hand, a larger 7 tends to slowdown the reduction of f as in Figure aa). Furthermore, the FID scores at T = 3 x 10a are only slightly improved compared to those at T x 10 Facing such a dilemma, we evaluate the performance of 7-SGA using 7 5 such that rry remains the same. This is the case where 7-GDA is not convergent due to oscillating angles. We find that both the angle and the FID scores are significantly improved with a suitable choice of 0 and T in -SGA.
and 7 = 10 because the 5. observe a negative angle t = T in --GA
Regarding the choice of 0 in r-SGA, we have used this dataset to tune this parameter and then chosen reasonable value be used for the other datasets. Intuitively, when 0 is too small, 7SSGA can be as unstable as --GDA When 0 is too big, it may amplify the stochastic gradient noise in the correction term of SSG. Therefore nevertheless that in a wide range of 6 the performance of 7-GG in terms of the FID (test) score is similar. It also suggests that 7-GG could have global convergence property when @ is small.
choose a suitable is a delicate question. In Figure 5 we observe
8375
1.00 380000
Figure 5: Evolution of the FID (test) score of stochastic 7-SGA as a function of a wall-clock time the Wasserstein GAN of MNIST (digit 0). We vary f E [0.01, 0.5] with a fixed 7 = 5.
N.3 EXTRA RESULTS ON FASHION-MNIST
We perform extra numerical simulations on the Fashion-MNIS" dataset. In Table we study the performance of 7-GDA by varing the choice of It is for T = 2 10 iterations with y 0.1/T.
32

---

Published as a conference paper at ICLR 2025
At = 1 and T 5, we observe similar instability in 7-GDA the MNIST case at 5 and T = 10 (in Table 2). T = 10, r-GDA has a stable dynamics and a good performance in terms of FID scores.
We next study the performance of 7-G by varing the training iterations T', using the same y = 0.02, 5, 0 = 0.075. Table 4 reaches a similar conclusion as Table 2 confirming the importance of the correction term in T-SGA to improve the local convergence of G-GDA
Lastly, compare the computational time between --GDA and 7-SGA in Figure 6 Different the MNIST case in Figure 4
we find that 7-GDA has a faster computational speed at = 10, compared to r-SGA This suggests that the speedup of the 7-SGA in terms of the number of iterations is less significant in this case since 7-GDA works well with a relatively small т. On the other hand, larger
20 in G-GDA makes it slower.
Table 4: Last iteration measures of stochastic 7-GDA and 7-SGA on the Wasserstein GAN of Bushion-MNIST We report the f. angle, and FID scores computed at (a(T),,(T)). 7-GDA is trained for T x 10 iterations with 7 = 0.1/T. T. r-SGA is trained longer with ? = 0.02, T = 5,
0 0.075.
GDGDA
T-SGA
angle
FID (train)
FID (val)
7(10")
f
angle
FID (train)
(val)
1
1.60 (20.008)
0,92
107
109 (20.5)
0.019
0.33 (20.01)
16.98
19.2 (10017)
5
0.02
0.48 (+0.01)
17.6 (#0.08)
19.8 (+0.2)
3
0.019
0.26 (20.008)
16
18.3 (10.13
10
0.02
0.4
19
0.016
0.39 (eo.as)
14.37 (40.08)
16.6 c+0.1)
(a)
(b)
10/
110
153
Figure 6: Computational speed of G-GD and 7SGA as function of wall-clock time on the Wasserstein GAN of Fashion-MNIST. a): 7-GDA at r = 10 vs 7SGA at 7 = b): 7-GD at 20 vs 7SG 7 5.
N.4 EXTRA RESULTS ON FASHION-MNIST (T-SHIRT)
From the results in Table 5 we see that the behavior of the G-DD and 7-SGA algorithms (in terms of the and angle measures) are similar to the MNIST (digit 0) case. As in Table we observe that one can improve the local convergence of 7-GA in the range of small by using 7-SGA. We also find that an improved convergence (in terms of the angle) lead to improved GAN models in terms of the FID scores.
Table 5: Last iteration measures of stochastic 7-GDA and 7-GA on the Wasserstein GAN of Fashion-MNIST (T-shirt). We report the S. angle, and FID scores computed at (=xTT), (T)). 7-GDA trained for = 10a iterations with 7 = 0.1/T. SGG is trained longer with 7 = 0.02, 7 = 5,
0 0.075.
GDA
S-GG
angle
FID (train)
FID (val)
T(10%)
f
angle
FID (train)
FID (val)
5
-0.52
-0.31
80 (20-0
92 (21:
0.02
0.30 (20.00)
22.7 (20.3)
36.1 (20.5)
10
0.03 (#0.03)
0.05 (20.04)
73
86
0.018
0.35 (20000)
20.6 (20.2)
34.1 0
30
0.01
0.15 (20.05)
24.7 (b0.2)
38.7 cbo.s)
3
0.018
0.32 (20000)
19.8 (40.2)
33.3 (20.3)
33

---

Published as a conference paper at ICLR 2025
N.5 EXTRA RESULTS ON COMPUTATIONAL TIME
In Figure 7 we compare the computation time of 7-GDA and 7-SGA. The best performed methods selected compare at the last iteration, according the value of f in Example 2 or the FID (val) score on MNIST (digit 0) and Fashion-MNIST (T-shirt).
In Example 2, we set 7 0.001/T for 7-GDA and 7-SGA (both with deterministic gradients). We find that 7-SGA has a significant speedup compared to T-GDA. This is due to a much faster convergence of 7-SGA at T 10, 0- 0.15 compared to the 7-GDA at 7 50.
On the two image datasets, the speedup is less significant using r-SGA compared to r-GDA (both with stochastic gradients). On MNIST (digit 0), we compare r-GDA at = 30 with r-SGA at T = 5,0 0 = 0.075 using the same discriminator leraning rate "yT = 0.05. We find that 7-SGA is slightly faster and can reach a lower FID (test) score. On Fashion-MNIST (T-shirt), we compare
7-GDA at = 30 with r-SGA at 5, 0 0.075 using YT 0.1. We find that the speed of T-GDA and r-GGA is similar.
(a)
(b)
(c)
-1144
300%
--144
30
1980
1800
20000
2.000
12.00
22000
2,000
2,000
Figure 7: Computational speed of T-GDA and 7-GA function of wall-clock time in Example 2 and on MNIST (digit 0) and Reshion-MNIST (T-shirt). The FID (test) score is computed from the fake (GAN model) samples and the test samples of each dataset. a): Example 2. b): MNIST (digit 0). c): MASSI (T-shirt).
34


Reviews:
[{"review_id": "sVzeUY0D7G", "reviewer": "Reviewer_Lg9L", "summary": "This paper extends the analysis of the local convergence of two-time-scale $\\tau$-GDA and $\\tau$-SGA methods to the differential Stakelberg equilibrium (DSE) of Euclidean min-max problem to the Riemannian min-max problem. This paper first generalizes the notion of DSE in the Euclidean space to the Riemannian manifold (in Section 2.1), using a local coordinate chart. Then, the authors provide a sufficient condition (in Theorem 3.1) for the fixed point method to have a local linear convergence. Based on Theorem 3.1, this paper shows a specific sufficient condition for the $\\tau$-GDA to locally linearly converge to DSE in Theorem 3.2. In addition, the authors generalize $\\tau$-SGA for Riemannian min-max problem, which is originally developed to mitigate undesirable rotational dynamics encountered by $\\tau$-GDA in the Euclidean space. In the Euclidean space, extragradient (or optimistic gradient) method is widely used to relieve such rotational behavior, but its Riemannian version, named RCEG, is computationally expensive. This paper claims that their $\\tau$-SGA equipped with auto-differentiation may have computational benefit over RCEG. Experiments on a toy example and a more realistic Orthogonal WGAN problem empirically confirm this paper's theoretical findings.", "questions": "- lines 45-47 could be improved to better explain this paper's focus on differential equilibriums (DNE and DSE). This could have been local Nash and local minimax points. Then why differential equilibrium? \n- Table 1 is confusing: What is your focus here? The title should be more specific to make a point. Isn't Nash equilibrium found by Zhang et al. (2023) DNE? This is not clear in the table. Also, your result is local (both in optimality and convergence) while others might be global. I am not sure whether local/global should be discussed in the table, but I am sure that this table needs to be reorganized and rewritten.\n- I suggest rewriting Definition 3.1 to make it more explicit that it defines local linear convergence.\n- line 276: Were you trying to say that $M$ with eigenvalues with only negative real parts?\n- lines 524-525: I don't follow what do you mean here.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Existing results on local convergence to DSE and DNE in nonconvex-nonconcave min-max problems in Euclidean space are crucial. Thus, while its extension to Riemannian manifolds may seem straightforward, it is a significant and non-trivial advancement. Although I was not able to check all the details of the proof, the parts I checked looked correct.", "weaknesses": "Missing preliminaries for non-experts on Riemannian manifold: For example, adding the definition of Riemannian gradient/Hessian/cross-gradient, the role of local coordinate chart and the relation between $f$ and $\\bar{f}$ would help readers to better understand the context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lDUy10wUyO", "reviewer": "Reviewer_v3Po", "summary": "This paper analyzes the local convergence of the deterministic τ-GDA and τ-SGA algorithms to differentiable equilibria in min-max games on Riemannian manifolds. Using the Ostrowski theorem, sufficient conditions on the algorithm hyperparameters (in particular, on the learning ratio τ) are given for linear-rate local convergence to Differentiable Stackelberg Equilibria (DSE) for both τ-GDA and Asymptotic τ-SGA (an approximation to τ-SGA that is amenable to easier analysis). Local convergence to Differentiable Nash Equilibria (DNE) is also given for τ-GDA.\n\nThis paper marks the first time that τ-SGA has been written for Riemannian manifolds, and the authors put it forth as an algorithm that can solve the problem of τ-GDA’s slow convergence rate in certain settings. Both theory and example are given to show that Asymptotic τ-SGA can be locally convergent at a smaller τ compared to τ-GDA, and with a faster rate; moreover, in Euclidean space the rate guarantee outperforms that of the extra-gradient method, which has been used to overcome the slow convergence rate of τ-GDA but is costly in Riemannian space. Experiments also show that the gap between Asymptotic τ-SGA and the true τ-SGA is small, so the theoretical results should also hold for the more natural τ-SGA.\n\nFinally, the paper applies stochastic τ-GDA and τ-SGA to train orthogonal Wasserstein GANs with a discriminator parametrized in the Stiefel manifold. It is shown that even with good initialization a small τ may cause τ-GDA to oscillate with high amplitude, but that τ-SGA can converge even at those small values of τ.", "questions": "From the experiments, it seems like τ-SGA is used as a sort of “last mile” algorithm to guarantee fast convergence after good initialization/pretraining (either via ansatz in the analytical examples of Figure 1 or via τ-GDA for the GANs). Is this a reasonable interpretation of the authors’ proposed use of τ-SGA, and is there any reason that τ-GDA—in particular, alternating τ-GDA—is used to pretrain the GANs?\n\nIn Theoerems 3.2 and 3.4, after the main statements there are additional (“furthermore…”) statements for when γ is fixed exactly depending on L_g/L_s. Is this reasonable given that L_g depends on the DSE, which is not known in advance? (Maybe this is not so important, but as it is written I am not sure what the significance of these “furthermore” statements is.)\n\nτ-SGA has an additional hyperparameter θ (or μ) to tune compared to τ-GDA, and in the GAN example of Table 2 a “suitable choice” of θ seems to have been made. Does the value of θ matter much, and how is it chosen?\n\nI am not so familiar with the way “retraction” is used in Section 3.1, though it does not affect much as the algorithms are easily understood. Perhaps some quick definition or source could be given?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Overall, this paper seems like a significant algorithmic contribution with sound theoretical grounding. The authors extend known, tight local convergence results for τ-GDA from Euclidean space to Riemannian manifolds and introduce τ-SGA to the context of Riemannian manifolds. Both in theory and practice τ-SGA is shown convincingly to be able to achieve (local convergence) in settings where τ-GDA cannot, highlighting its usefulness in this setting of Riemannian min-max problems with minimal assumptions (just f twice continuously differentiable).\n\nThe paper is generally well written. The sections on differentiable equilibria, algorithms, and local convergence read especially well, with much background and explanation given to readers. Motivations and the context of prior work and clearly written.", "weaknesses": "While it is clearly stated in the introduction that global convergence is difficult to achieve in this setting and local convergence (to differentiable equilibria) may be all we can get theoretically, it is not clear what these limitations mean, or are expected to mean, in practice. The experiments are set up to show local convergence after good initialization, but it is not clear what the good initialization entails or if τ-SGA can be used when you are not near a DSE. Also maybe some comment could be made about the existence and significance of DSE in the settings provided (e.g., the Wasserstein GANs), and about other methods for doing min-max Riemannian optimization in these setting (e.g., over Steifel manifolds).\n\nI also find the writing of the GAN experiments and their setups/parameters/initialization a bit terse and less clearly written than what comes before, with a few things in particular lacking explanation. I ask some questions about this below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0StUVA2F5V", "reviewer": "Reviewer_Bh31", "summary": "Using the concepts of DSE and DNE on Riemannian manifolds, the author derives conditions on the range of τ and learning rate of x to ensure linear convergence of τ-GDA to DSE and DNE.\n\nIt introduces a novel algorithm τ-SGA to enhance the convergence of τ-GDA, allowing a broader range of τ for convergence when τ is large, and achieving faster local convergence than τ-GDA.\n\nApplying these insights, the author improves the training of orthogonal Wasserstein GANs. Numerical results show that enhanced convergence of stochastic τ-GDA and τ-SGA can improve the learned generator on simple benchmarks.", "questions": "Question for Theorem 3.1. (Ostrowski Theorem on manifold)\n\n- The author indicates that the theorem is analogous to the theorem in the Euclidean case. Is the Euclidean version of the theorem also based on the spectral radius of a linear transformation similar to (9)? \n\n- What is the size of the local convergence radius around ( 𝑥*, 𝑦*)? \n\n- How can one ensure that the initialization lies within this local neighborhood? Does the initialization used in experiments satisfy this requirement? \n\n- What is the reasoning behind assuming a small spectral radius for 𝐷𝑇* ?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This article provides sufficient conditions for the local convergence of τ-GDA and τ-SGA to differential equilibrium on a Riemannian manifold, where the author proves a linear convergence rate of τ-GDA to DSE and DNE, depending on the spectral radius of the Jacobian at equilibrium. THe author introduces τ-SGA on Riemannian manifolds to further improve this rate.", "weaknesses": "- Some key terms could benefit from further explanation or intuitive insights. For example, what are the underlying intuitions behind the linear transformations in (9) and (10)?\n\n- It appears that several theorems are extensions of those from the Euclidean case. What are the main differences or key insights that allowed these results to be successfully extended to the Riemannian manifold?\n\n- Given the author's claim of linear convergence rates for the proposed methods, are there any experimental results to support this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "INjptNIgw0", "reviewer": "Reviewer_ftu6", "summary": "This paper studies min-max algorithms to solve zero-sum differential games on Riemannian\nmanifold", "questions": "I think that this manuscript contributes nothing in science expect some hard understanding of mathematical symbols.", "limitations": "", "rating": 1, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "No", "weaknesses": "This paper does not have any interesting parts. Firstly, the Riemannian optimization is not practical. Furthermore, could you show some practical utilization of your algorithms?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xxArf8Fywx", "reviewer": "Reviewer_sHDJ", "summary": "This paper investigates the local convergence of simultaneous minimax algorithms to differential Stackelberg equilibrium (DSE) and differential Nash equilibrium (DNE) on Riemannian manifolds. The authors study two representative deterministic algorithms, $\\tau$-GDA and $\\tau$-SGA. For $\\tau$-GDA, they derive sufficient conditions for convergence to DSE and DNE. For $\\tau$-SGA, they analyze an asymptotic variant and demonstrate a faster convergence rate to DSE under specific conditions. Furthermore, the authors conduct numerical experiments to explore the behavior of stochastic versions of the two algorithms.", "questions": "1. In line 277, what is the order of $\\gamma^{\\cdot}(M)$? Could the authors provide an intuitive explanation of this function?\n2. The computation of $\\tau$-SGA involves a matrix-vector product. Are the benefits sufficient to justify the additional computational cost?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Significance**: This paper addresses the more general nonconvex-nonconcave setting, extending previous results to Riemannian manifolds.\n2. **Comprehensiveness**: It provides a range of results by examining two types of equilibrium points, two algorithms, and extensive numerical results.", "weaknesses": "1. **Limited Comparative Analysis and Interpretation**: The relationship and comparative insights between the theoretical results could be strengthened. Here are some examples.\n* (i) The paper examines two equilibrium points, DSE and DNE, where DNE is a subclass of DSE with stricter definitions. Convergence to DNE would be expected to require fewer restrictions or achieve a faster rate. Theorems 3.2 and 3.3 support the former expectation, as the range of $\\tau$ in Theorem 3.3 is broader than in Theorem 3.2, yet no convergence rate is provided for Theorem 3.3.\n* (ii) The authors seem to aim to show the superiority of $\\tau$-SGA over  $\\tau$-GDA. However, by comparing Theorems 3.2 and 3.4, the range of $\\tau$ ensuring convergence for asymptotic $\\tau$-SGA exceeds that of $\\tau$-GDA only if $\\| C + \\theta BB^\\top \\| < \\| C \\|$. Further discussion on practical ways to ensure this condition or examples where it holds would be helpful. Additionally, there is no theoretical counterpart to Theorem 3.3 for $\\tau$-SGA. While $\\tau$-SGA is proposed to avoid rotational dynamics, this advantage is demonstrated only in numerical results (e.g., Figure 1), not theoretically, leaving theoretical support insufficient.\n\n2. **Unclear Analysis for (Asymptotic) $\\tau$-SGA**: \n* (i) In line 327, the asymptotic analysis requires $\\theta$ to be of constant order. Why, then, are parameters $\\mu$ and $\\tau+1$ introduced in Eqs. 12 and 13, and what is their significance?\n* (ii) If the authors aim to show the superiority of $\\tau$-SGA, Theorem 3.4 alone is insufficient, and Figure 1's simple example is not enough to establish the similarity between $\\tau$-SGA and its asymptotic variant. The claim \"Theorem 3.4 is valid for $\\tau$-SGA\" in line 363 lacks rigor. If deriving a theoretical result for $\\tau$-SGA is challenging, additional numerical experiments for the asymptotic $\\tau$-SGA$ should at least be provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)