Quantitative Convergences of Lie Group Momentum Optimizers
Authors: Lingkai Kong
Molei Tao
Venue: NeurIPS 2024 poster (2024)
Keywords: momentum Lie group optimizer; convex; explicit convergence rate
Primary area: optimization

Abstract: Explicit, momentum-based dynamics that optimize functions defined on Lie groups can be constructed via variational optimization and momentum trivialization. Structure preserving time discretizations can then turn this dynamics into optimization algorithms. This article investigates two types of discretization, Lie Heavy-Ball, which is a known splitting scheme, and Lie NAG-SC, which is newly proposed. Their convergence rates are explicitly quantified under $L$-smoothness and \emph{local} strong convexity assumptions. Lie NAG-SC provides acceleration over the momentumless case, i.e. Riemannian gradient descent, but Lie Heavy-Ball does not. When compared to existing accelerated optimizers for general manifolds, both Lie Heavy-Ball and Lie NAG-SC are computationally cheaper and easier to implement, thanks to their utilization of group structure. Only gradient oracle and exponential map are required, but not logarithm map or parallel transport which are computational costly.

Quantitative Convergences of Lie Group Momentum Optimizers
Lingkai Kong School of Mathematics Georgia Institute of Technology 1kong75@gatech. edu
Molei Tao School of Mathematics Georgia Institute of Technology mtao@gatech. edu
Abstract
Explicit, momentum- dynamics that optimize functions defined on Lie groups can be constructed via variational optimization and momentum trivialization. Struc- ture preserving time discretizations can then turn this dynamics into optimization algorithms. This article investigates two types of discretization, Lie Heavy-Ball, which is known splitting scheme, and Lie NAG-SC, which is newly proposed. Their convergence rates explicitly quantified under L-smoothness and local strong convexity assumptions. Lie NAG-SC provides acceleration over the mo- mentumless case, i.e. Riemannian gradient descent, but Lie Heaay--Ball does not. When compared to existing accelerated optimizers for general manifolds, both Lie Heavy-Ball and Lie NAG-SC are computationally cheaper and easier im- plement, thanks to their utilization of group structure. Only gradient oracle and exponential map required, but not logarithm map parallel transport which are computational costly
Introduction
First-order optimization, i... with the gradient of the potential (i.e. the objective function) given as the oracle, is ubiquitously employed in machine learning. Within this class of algorithms, momentum often introduced accelerate convergence: for example, in Euclidean setups. it has been proved to yield the optimal under strongly convex and L-smooth assumptions of the objective function 21 Sec. 2].
convergence order, for large class of first-order optimizers,
Gradient Descent (GD) without momentum can be generalized to Riemannian manifold by moving to the negative gradient direction using the exponential map with small step size. This generalization is algorithmically straight forward, but quantifying the convergence rate in curved spaces needs nontrivial efforts 6
32 27]. In comparison, generalizing momentum GD to manifold itself is nontrivial due to curved geometry; for example, the iteration must be kept on the manifold and the momentum must stay the tangent space, which changes with the iteration, the same time. is even more challenging to quantify the convergence rate theoretically due to the loss of linearity in the space, leading to the lack of triangle inequality and cosine rule. Finally, there is not necessarily acceleration unless the generalization is done delicately.
Regardless, optimization manifolds is important task, for which the manifold structure can either naturally come from the problem setup or be artificially introduced. A simple but extremely important example is compute the leading eigenvalues of large matrix, which can be approached efficiently via optimization on the Stiefel manifold [19]; a smaller seale version can also be solved
More on the modern machine learning side, one can algorithmically add orthonormal constraints to deep learning models to improve their accuracy and robustness [c.g...5
optimization on SO(n) 29 26
Both examples involve SO(n). which an instance an important
type of curved spaces called Lie groups.
"Code can be found at http:://gttta...cooooo////////// hct.
Lnceeerr_______eeeeeeeeeeeeeeeee On_Lie_Group
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Lie groups are manifolds with additional group structure, and the nonlinearity of the space manifests through the non-commutative group multiplication. The group structure can help not only design momentum optimizer but also analyze its convergence. More precisely, this work will make the following contributions:
Provide the first quantitative analysis of Lie group momentum optimizers. This is significant, partly because there is no nontrivial convex functions on many Lie groups (see Rmk. D so we have analyze nonconvex optimization.
Theoretically show an intuitively constructed momentum optimizer, namely Lie Heavy-Baa may not yield accelerated convergence. Numerical evidence is also provided (Sec. 6
Generalize techniques from Euclidean optimization to propose a Lie group optimizer. Lie NAG-SC, that provably has acceleration.
Comparing to other optimizers that are designed for general manifolds, we bypass the requirements for costly operations such as parallel transport [e.g.. 4 which is way to move the momentum between tangent spaces, and the computation of geodesic [e.g.. M. which may be an issue due to not only high computational cost but also its possible non-uniqueness.
1.1 Related work
In Euclidean space, Gradient Descent (GD) for p-stroongly convex and L-smooth objective func- tion can converge as |. - x.. s (1-C4) | - zol upon appropriately chosen learning rate. Momentum can accelerate the convergence by softening the dependence on the condition number L/p. However, how momentum is introduced matters achieving such an acceleration. For example, NAG-SC [2D has convergence rate D CV but Heavy-Ball [23] still has linear depen- dence the conditional number, similar to gradient descent without momentum (but it may work
better for nonconvex cases).
Remarkable quantitative results also existed for manifold optimization. The momentum-less case relatively simpler, and (32), for example, developed convergence theory for GD on Riemannian convexity and smoothness, which matched the classical Euclidean result - for instance, Thm. 15 of their paper gave a convergence rate of I-C min { H K,K] }
manifold under various assumptions
when the learning rate is 1/L, under geodesic-u-strong conveeitt and Mondeesi-LLsmoothhe the momentum case, analyzed the convergence of a related dynamics in continuous time, namely an optimization ODE corresponding to momentum gradient flow, on Riemannian manifolds under both geodesically strongly and weakly convex potentials, based on a tool of modified cosine rule. However, numerical methods in discrete time that are easy and cheap to implement and provably convergent in an accelerated fashion under mild conditions are still under-developed. One existing idea is to transform a function on the manifold to function on Euclidean space by the logarithm function. More precisely, in the case where the logarithm is a one-to-one map from the manifold to the tangent space, it can be used to project the objective function on the manifold to a function on the tangent space ('pullback objective function'), enabling the usage of accelerated algorithms in Euclidean spaces [e.g.. [I]. Although such analysis may relax the requirement of global convexity, it requires assumptions on the 'pullback objective function', 1, which is hard to check in reality. Another series of seminal works include [33 M. which analyzed the convergence of a class of optimizers by extending Nesterov's 's technique of estimating sequence (21 to Riemannian manifolds. They managed to show a convergence rate between 1 - C and 1 - C L. i.c., with conditional number dependence inbetween that of GD with and without momentum in the Euclidean cases. They further proved that, as the iterate gets closer to the minimum, the rate bound gets better because it converges to 1011- 1- 1-CVE However, their algorithm requires the logarithm map (inverse of the exponential map), which may not be uniquely defined many manifolds (e.g., sphere) and be computationally expensive. In contrast, Lie NAG-SC, which we will construct, works only for Lie group manifolds, but they are
For
AAl the constants C' in this paper may be different case-by-case, but they are all independent of dimension and the condition number.
} FFor continuous dynamics, convergence rate means if (g:) (((=)) = O(e ). For discrete algorithms, it refers e if (gx)) U(g-)= = O(c").
'We will use K to denote constants that depend on the manifold structure, e.g., diameter, curvature. It may be different case- byse-by-ccse.

---

more efficient when applicable, due to being based on only exponential map and gradient oracle. Acceleration of the same type will also be theoretically proved.
Momentum optimizers specializing in Lie groups have also been constructed before 26 where variational optimization (30] was generalized to the manifold setup and then left trivialization were employed to obtain ODEs with Euclidean momentum that perform optimization in continuous time. Our work is also based on those ODEs, whose time however has be discretized so that an optimization algorithm can be constructed. Delicate discretizations have been proposed in [26] so that the optimization iterates stay exactly on the manifold, saving computational cost and reducing approximation errors. But we will further improve those discretizations. More precisely, note first that [26] slightly abused notation and called both the continuous dynamics and one discretization Lie NAG-SC. However, we find that their splitting discretization may not give the best optimizer at least, Ist-order version of their splitting scheme yields a linear condition number dependence in our convergence rate bound. Since this splitting- -aaiii optimizer almost degenerates to heavy-ball in the special case of Euclidean spaces (as Rmk. 28 will show), we refine the terminology and call Lie Heavy-Ball. To remedy the lack of acceleration, we propose new discretization that actually has square root condition number dependence and thus provable acceleration, and call as (the true) Lie NAG-SC.
Finally, note there can be obstructions to accelerated optimization, for example roughly when curvature is negative [16] 10 12). That is, however, not a contradiction because our setup involves positive curvature.
1.2 Main results
We consider the local minimization of differentiable function U G + IR, i.e., minger U (gg), where G a finite-dimensional compact Lie group, and the oracle allowed the differential of U.
Two optimizers we focus on are given Alg.
[I Under assumptions of L-smoothness and locally
geodesic-u--strong convexity, we proved that Lie Heavy-Ball has convergence rate (1 C+ which
approximately the convergence rate of C' min - K) for Lie GD (Eq which is identical to Riemannian GD applied to Lie groups); this is no acceleration. To accelerate, we propose new Lie
NAG-SC algorithm, with provable convergence rate (1 + C Cin (V..K)) Note the condition
number dependence becomes /K instead of k := T./u, hence acceleration.
For summary of our main results, please Table
Algorithm 1: Momentum optimizer Lie groups
Parameter :step size h > 0, friction > O, number of iterations N
Initialization :oo G, E 0
Output :Local minimum of U
for k .., 1 do
Heavy-Ball Ball then
Ek+1 (1 Eh) hT, Lon. (gk)
NAG-SC then
Ek+1 = - (1-yh)ER (1- -h)h (T
-Ta-n Lo VU (gk-1))
-U
h.T gv Lg. (gk)
Dk++1 = 9h (xp(((x+1)
end
return 9N
Remark 1 (Triviality of convex functions on Lie groups). We do not assume any global convexity of U. In fact, U has to be nonconvex for any meaningful optimization to happen. This is because we are considering compact Lie groupf] and a convex function be a constant function (37y. An intuition for this is, a convex function on closed geodesic must be constant. See [e.g., 18 Sec. B.3] for more discussions. Our analysis is, importantly, for nonconvex U, and convexity is only required locally to ensure a quantitative rate estimate can be obtained.
connected compuct manifold could only
'Even if we consider noncompact Lie groups, many of them have compact Lie subgroups (20 and our argument would still hold.

---

Continuous dynamics
Heavy-Ban
NAG-SC
Scheme
Eq. 2
Eq. (9)
Eq. (13)
Step size
VR
min
47.
</T. 2p(e)
Convergence rate c
3V14
2
(1 +
30 V min
3
16L
V2r. 3p(a)
(Modified) energy
Eq. (5)
Eq. (TO)
Eq.
Lyapunov function
Eq. (6)
Eq. (12)
Eq.
[44
Main theorem
Thm.
9
Thm. 13
Thm.
14
Table
summary of main results
Preliminaries and setup
2.1 Lie group and Lie algebra
Lie group, denoted by G, is a differentiable manifold with a group structure. A Lie algebra is a vector space with bilinear, alternating binary operation that satisfies the Jacobi identity, known as Lie bracket. The tangent space at e (the identity element of the group) is a Lie algebra, denoted as g = G.G. The dimension of the Lie group G will be denoted by m.
Assumption 2 (general geometry). We assume the Lie group G is fintte-dimensionall and compact.
One technique we will use handle momentum is called left-trivialization: Left group multiplication by 9 9ÿ is a smooth map from the Lie group itself and its tangent map T3 TyLg TT T is one-to-one map. As result, for any g E G, we can represent the vectors in T,G by TaLe for ç e T, This operation is the sef-trivializattin.. It comes from the group structure and may not exist for general manifold. If the group represented via an embedding to matrix group, i.e., 9, E TR then the left trivialization is simply given by TeLye of with the right-hand side given by matrix multiplication.
A Riemannian metric is required to take Riemannian gradient and we are considering left- left-invariant metric: we first define an inner product (:-) on g. which a linear space, and then move around by the differential of left multiplication, i.e., the inner product at T is for m, e T (n1, (TgLy-1 T2y
2.2 Optimization dynamics
Riemannian GD [e.g.. 332 with iteration 9k+1 cxp (-hVU( can be employed to optimize U defined G. where V is Riemannian gradient, and exp: G x T2G G is the exponential map. To
see a connection to the common Euclidean GD, it means we start from and go to the direction of negative gradient with step size h to get 9++1 by geodesic instead of straight line. Riemannian GD can be understood as a time discretization of the Riemannian gradient flow dynamics ý (g).
In the Lie group case, it is identical to the following Lie GD obtained from left- set-triviallzztion [26]:
gh+1 = gk exp. (hT VU(k))
where To (gk) g is the seft-trivialized gradient. exp, is the exponential map staring at the group identity following the Riemannian structure given by the left-invariant metric, and the operation between 9k and exp(hTT Lox. (VU())) )) is the group multiplication. To accelerate its convergence, momentum introduced to the Riemannian gradient flow via variational optimization and left-trivialization 226,, leading to the following dynamics:
g = TeLoE - ()) ad? - TTgL
(2)
Here g(t) e G is the position variable. ğ is the standard 'momentum' variable even though it should really be called velocity. It lives Ty(t) G, which varies as g(t) changes in time, and we will utilize group structure to avoid this complication. More precisely, the dynamics lets the 'momentum' ğ be T.L,S, and { is therefore T 9 and is our new, tit--trivillized momentum. Intuitively, one can
'The monotonicity of this energy function requires smaller step size than it listed in this table. See discussion in Rmk. 36 and the details provided in Sec. D.I
"The group exponential map and the exponential map from Riemannian structure can be different [8 Sec. D.IJ. However, under our choice of the left invariant metric later in Lemma 3 they are identical and exp will be the group exponential unless further specified.

---

think & as angular momentum, and Te Te being of is position times angular momentum, which is momentum. Similar the Lie GD Eq. T we will not use (g) directly, but its ceftatriviaiization To (V)())) to update the left-trivialized momentum.
This dynamics essentially models a damped mechanical system, and Tao and Ohsawa 266 proved this ODE converges to a local minimum of U using the fact that the total energy (kinetic energy { plus potential energy U) is drained by the friction term -7E. In general, 7 can be positive imeedepennent function (c.g., for optimizing convex but not strongly-convex functions), but for simplicity, we will only consider locally strong-convex potentials, and constant y is enough.
For curved space, an additional term ad- & that vanishes in Euclidean space shows up in Eq. (2). could be understood as a generalization of Coriolis force that accounts for curved geometry and is needed for free motion. The adjoint operator ad x g is defined by adx Y := [X.Y] J. Its dual, known the coadjoint operator ad" g g g. is given by (ad'x Y, 2) (Y, x Z), A g.
2.3 Property of Lie groups with ad" skew-adjoint
The term ad { in the optimization ODE 2 is a quadratic term and it will make the numerical discretization that will be considered later difficult. Another complication from this term is, depends on the Riemannian metric, and indicates an inconsistency between the Riemannian structure and the group structure, i.e., the exponential map from the Riemannian structure is different from the exponential map from the group structure. Fortunately, on compact Lie group, the following lemma shows a special metric on g can be chosen to make the term adद & vanish.
Lemma (ad skew-adjoint (20)). ) Under Assumption 2 there exists an inner product on such that the operator ad skew-adjoint, i.e., sule ade for any ç E g.
This special inner product will also give other properties useful in our technical proofs; see Sec. A.
2.4 Assumption on potential function
To show convergence and quantify its rate for the discrete algorithm, some smoothness assumption is needed. We define the L-smoothness on Lie group as the following.
Definition 4 (L-smoothness). A function U : G + RR is L-smooth if and only Vg
TTLL (Ú) - TyL TULL) Ld(g.9)
where d is the geodesic distance.
Under the choice of metric in Lemma that ad is skew-adjoint, Lemma 21 shows this is same as the commonly used Srodessc---smoothee
(Def. 20).
To provide an explicit convergence rate, some convex assumption on the objective function usually
needed. Under the assumption of unique geodesic geodesically convex set S c G, the definition of strongly convex functions in Euclidean spaces can be generalized to Lie groups:
Definition 5 (Locally geodesically strong convexity). A function U G B. is locally geodesic-pt
strongly convex at 9- if and only if there exists a geodesically convex neighbourhood of g., denoted by S, such that Vig gg 9 S,
U(g) U(i)
log,
logg" gl
(4)
where log is well-defined due to the geodesic convexity of S.
3 Convergence of the optimization ODE in continuous time
To start, we provide a convergence analysis of the ODE 22) since our numerical scheme comes from its time discretization. We do not claim such convergence analysis for the ODE is new, and in fact, convergence for continuous dynamics has been provided on general manifolds [e.g.. 3. However, we will prove it using technique to be self-contained and provide some insights for the convergence analysis of the discrete algorithm later.
Define the total energy EDDE; G R as
FDDE (g. U())
|5l2 1
1
(5)
2
i.e., the total energy is the sum of the potential energy and the kinetic energy. Thanks the friction 7, the total energy is monotonely decreasing, which provides global convergence to a stationary point.
5

---

Theorem 6 (Monotonely decreasing of total energy (26).. Suppose the potential function U CC'C) and the trajectory (g(t),<(t)) follows ODE (2. Then
LODE (g(t),(())= --711 dt
Thm. provides the global convergence of ODE 2 to a stationary point under only C' smoothness: when the system converges, we have &o. O, which gives [V)))
Moreover, using the non-increr -occreccggi property of total energy, the following corollary states that if the particle starts with small initial energy, it will be trapped in a sub-level set of U. The local potential well can defined using U's sub-level set.
Definition 7 (u sub-level set). Given u IR, define the sub-level set of as
e G: U() s uu) == Us:
120
L.e. a disjoint union of connected components. Corollary 8. Suppose U e cC² Let u= EODE (g(()) If the sub-level set Of U is U1zo S, and g(0) E So, then we have gt)) ε So. Vt 2 O.
Under further assumption of local strong convexity this sub-level set, convergence rate can be quantified via Lyapunov analysis inspired by [25). More specifically, given a fixed local minimum 9.. there is provably local unique geodesic convex neighbourhood of g.. Denote by S, and we define CODE on S by
ODE ( + Iell -
logg.' g+ gl
(6)
By assuming the local geodesic-/1-strong convexity U on S, we have the following quantification of Eq. (2).
Theorem 9 (Convergence rate of the optimization ODE). the initial condition (go, Eo) satisfies that go e S for geodesically convex set S G, U E C² (G) is locally geodesic-u-comvex S and the sub-level set U U with EODE (go: {o) satisfies So c S, then we have
- S -Conn LODE ( (go:Eo)
with CODE 2 // by choosing 7 2//..
Remark 10. This theorem alone is a local convergence result and a (Lie group + momentum) extension of an intuitive result for Euclidean gradient flow, which is, if the initial condition is close enough to a minimizer and the objective f has a positive definite Hessian at that minimizer, then gradient flow converges exponentially fast to that minimizer. However, Thm Baleedy ensures global convergence, and if not stuck a saddle point, the dynamics will eventually enter some local potential well. If that potential well is locally strongly convex at its minimizer, then the local convergence result (Thm 9 supersedes the global convergence result (which has no rate), and gives the asymptotic convergence rate. Note however that different initial conditions may lead to convergence different potential wells (and hence minimizers), as usual.
4 Convergence of Lie Heavy-Ballsplittnng discretization in discrete time
One way to obtain a manifold optimization algorithm by time discretization of the ODE (2 is to split its vector field as the sum of two, and use them respectively to generate two ODEs:
و TeL -
[g=0 -E=-E-TTLL.-VU00
(8)
Each ODE enjoys the feature that its solution stays exactly on G g (26). and therefore if one alternatively evolves them for time h, the result is a step-h time discretization that exactly respects the geometry (no projection needed). If one approximates exp(-<hh by 1 hy, then the same property holds, and the resulting optimizer
g gk eXp()(
(9)
E (1 ->hh) - hTT VU

---

In Euclidean cases, such numerical scheme can be viewed as Polyak's Heavy-Bas -alll algorithm after change variable (Rmk. 27). and will thus be referred Lie Heavy-Ball. It is also 1st-order (in h)) version of the '2nd-order Lie-NAG' optimizer in 26 (Rmk. (8).
To analyze Lie Heavy-Ball's convergence, again seek some "energy" function such that the iteration of the numerical scheme Eq. ( will never escape a sub-level set of the potential, similar to the continuous case. Given fixed friction parameter 7 and step size h, we define the modified energy E G Gxp. + R as
HIR (g. (o.()=U(g)) (1-Th)² 1E1
(10)
2
Theorem 11 (Monotonely decreasing of modified energy of Heavy Ball), Assume the potential U is globally L-smooth. When the step size satisfies h 2 "P+L" have the modified energy E is monotonely decreasing, i.e.
EHB (gk Ex)) (1)-1,
- -
Thm. 11 provides the global convergence of Heavy-Ball scheme Eq. (9) to stationary point under only L-smoothness: Due the monotonicity of the energy function E the system will eventually converge. When it converges, since 9 is not moving, we have | 0, leading to the fact that [V(()=))| O. More importantly, the following corollary shows that the non-increasing property of the modified traps y in sub-level set of U:
(g05E0) Corollary 12. Let u E (gos Eo). If the u sub-level set U satisfies go E So and
d So. 22
Us:
h2/2E2HB Eo) + h2 max Ai
(1I)
Then we have gu for any k for the Heavy-Ball scheme Eq. when h 7.+.."
Under the further assumption local strong convexity on this sub-level set, the convergence rate can be quantified via Lyapunov analysis inspired by (25). More specifically, given a fixed local minimum ge, there is a local unique geodesic neighbourhood ge, denoted by S, and we define ! on S by
1 C HB (9.5)= = 1-7h (U(zexp(-18))-UU0) ||
-1
log g. y +
(12)
7h
The exponential decay for the Lyapunov function (Lemma rate for Eq. (9) in the following theorem:
32 helps us quantify of the convergence
Theorem 13 (Convergence rate of Heavy-Batd -Ball scheme). If the initial condition (go, Eo) satisfies that Io E for some geodesically convex set S G, U is L-smooth and locally geodesic-u-convee S, and the u sub-level set of with u ODD (go: 5o) satisfies So c S and Eq. (II). then we have
U(Tu) - U(g)) c (90,
with CHB == (1+
1.) T6T.
by choosing 7 = 2/Th h /a 47.
Note the rate is (1 1/(16x))- The condition number dependence is linear (x) but not Vk. Similarly, the procedure of global convergence - local potential well local minimum discussed in Rmk. al applies the Heavy-Bar -all algorithm.
5 Convergence of Lie NAG-SC in discrete time
The motivation for NAG-SC is to improve the condition number dependence. The convergence rate of Heavy-Ball shown Thm. 13 is the same as the momentumless case [c.g.. (3) Thm. 15] under the assumption of local strong convexity and L-smoothness. To improve the condition number dependence, inspired by (25), we define Lie NAG-SC as the following:
9k+11 = 9h exp(hEx+1)
ERA1 (1 -h) (1 wh)h (Ton LU -Tou L9t-1 (U 1)) - hT Lyg (U(a))
(13)
7

---

Comparing to Lie Heavy-Ball, an extra ( term h -a T To introduced (see [25] Sec. 2] for more details in the Euclidean space). Our technique of left- trivialized (and hence Fuclidean) momentum allows this trick to transfer directly from Euclidean to the Lie group case.
-o-iiLa L.. 1- 1)
For NAG-SC, we will only provide a local convergence with quantified convergence under L- smoothness and local geodesically convexity on a geodesically convex subset S c G. The difficulty in designing a modified energy and proving the global convergence will be given later in Rmk. 36 We define the following Lyapunov function:
NANG-SC
+ (g.E) 1-7h -UG)) Ug))))
4 + |EEl
1
(14)
1 S+ 7 logg, g+ (VU(gexp((Ne)) 1²2 (2))
(jeep(((-))
1-
4(1->h)
where is the minimum of U in S. This Lyapunov function helps us to trap in a local potential well and quantify the convergence rate: Theorem 14 (Convergence rate of NAG-SC). If the initial condition Eo) satisfies that go e S for some geodesically convex set S < G satisfying maxges ((g,.) a for some 2n and A == xax ||adx llop U is L-smooth and locally geodesic- conver on S, and the u sub-level set of with u = (1 - -h) CNAG-SC (go, Eo) satisfies So c S and
d(So, 5-5.5--0 SS)) > hw/ L
(15)
then have
U U(gh) - -U(g)) S of NAG-SC (go, (o)
by choosing h min
and y 2//T with GNAG-SC:= (1+
30 / Mimin V2L 2p(a) })
V2L' 2x(a)
where
x
p(x) == exp(-ppp
(16)
Unlike sampling ODE and Lie Heavy-Ball, monotonely decreasing modified energy is not provided for Lie NAG-SC. It is unclear whether such modified energy for NAG-SC exists, and an intuition is provided in the Rmk. 36
Another fact in Thm. |4 that is worth noticing is, we have a term 1/p(a) that depends on the curvature of the Lie group
R while the Lie Heavy-Ball has the same convergence rate as the Euclidean case 225. unclear if the lost of convergence rate in Lie NAG-SC comparing the Euclidean case is because of our proof technique or the curved space itself. However, we try to provide some insights Rmk. 35
Systematic numerical verification via the eigen decomposition problem
6.1 Analytical estimation of property of eigenvalue decomposition potential
Given a symmetric matrix, its eigen decomposition problem can approached via an optimization problem on SO(n):
min XeRexa X-X X-X
X BXN
where N := diag([I,..... nn]). This problem is hard non-convex problem on manifold, but some analytical estimation [e.g.. 77] Thm. 4] can be helpful for us choose optimizer hyperparameters (we don't 't have to have those to apply the optimizers, but in this section we' d'd like to verify our theoretical bounds and hence a and L are needed).
This problem is non-convex with n"n! stationary points corresponding to the elements in n--rddr symmetric group, including 2n local minima and 2n local maxima. We suppose B = RA R with A = diag 1,. in the n-symmetric group, the corresponding local minimum is X,, (Xx(s)) ), i.e., we switch the columns of X by æ. The eigenvalues of its Hessian at the local minimum ι can be written as
2, _ where X;'s (the diagonal values of A) are in ascend order. Given
Jij (j - ()) >x())) isicján The global minimum is given by n. = id with minimum value Σ i.;-
In comparison, Euclidean NAG-SC has convergence rate (1+C/F) 25
8

---

1-convergeri eneeeeenceiin rate
10-1
102
heavy, ball NAG_SC
200
10-2
heavy_ball ball
10-2
NAC SC
10
10-3
-15
10- 10-4
10-4
2000
4000
6000
8000
10000
0 1000 2000 3000 4000 5000 6000 7000 8000
condition number
#iter
Numerical estimation for under different condition numbers x == &. for Heavy-Ball and NAG- SC, initialized close the global minimum. The dashed curves are fitted value using our theoretical result, ie.. for Heavy-Bai Ball, it is fitted by 1 cHв * Ck for some C' fit by linear regression, and for NAG-SC, it is CNAGSC x C/K
(b) Global convergence non-convex potential. The initial condition is chosen closed to the global maxi- mum, and we plot the value of the potential function along the trajectory. The horizontal tail means the algorithm converges to the machine precision.
Figure 1: Fig. [(a) shows that 1) Lie NAG-SC converges much faster than Lie Heavy-Bi Baal on ill-conditioned problems; The fitted dashed curve and the experimental results align well, showing our theoretical analysis of the convergence rate CHR and CNAG-SC is correct. Fig. [ shows the performance of algorithms non-convex problems experimentally. In this specific experiment, Lie NAG-SC outperforms Lie Heavy-Ball and finds the global minimum successfully without being trapped in local minimums. However, are not sure which is better in general optimization. One possible reason for the good performance on NAG-SC is it uses a larger learning rate and is better for jumping out of the local minimums. The values of Lyapunov function along the trajectory are not provided since it is not globally defined.
Numerical Experiment
We use the eigenvalues at the global minimum to estimate the L and μ in its neighborhood. As result, around the global minimum, L s (n- assume X's i are sorted in the ascend order. Such estimation is used choose parameters (y and h) in all experiments as stated in Table
(n-1)((A) 1),,, A1), and μ s min, (iin(>>+11 >,,, where we
Given conditional number
L. we design A in the following way: choose
diag (0. 1,....1. 2, - and R is uniformly sampled from S0(n) using (22 Sec. 2.1.1]. When the given K satisfies (n 1)(n (00-2),, 2), the condition number at global minimum is the given
The results are presented in Fig. [ and all experiments, we set 10, and the computations are done on MacBook Pro (M1 chip, 8GB memory).
7 Application to Vision Transformer
This section will demonstrate practical modern machine learning application of our Lie NAG-SC optimizer. The setting is a highly non-convex optimization problem with stochastic gradients, due to being real deep learning task, but empirical success is still observed. More specifically, it was discovered [19] that adding artificial orthogonal constraints to attention layers transformer models can improve their performances, because orthogonality disallows linearly dependent correlations between tokens, so that the learned attentions can be more efficient and robust. We will apply our optimizer solve this constrained optimization problem.
The setup is the following (using the notation of (28): consider a Scaled Dot-Product Multi- head Attention given by MultiHead( V) Concat(heade
head W where head,
Attention Qw K KW.KK VW.V, Attention( Q, K, V) softmax Vdr
OKT V. The trainable parame-
ters matrices W.O. e dmaasedds W.K e Rasaa W.V B xdd and WOO é B Boaadd Xdanial The

---

kezpenc00 8espam20000
sappances
2o. 2ou. lne
less value
loss value
lass value
10
Tor fo.
1960
10-2
lagea 10000
250 :000 1530 1150 good
150 1000 2250 g150
250 150 y000 500, goo
#iter
eiter
(a) (momentumlesss) GD
(b) Hcavy-Ball Ball
(c) NAG-SC
Local convergence of Lie Heavy-Ball and Lie NAG-SC on eigenvalue decomposition problem with different condition numbers. The initialization is close the global minimum. The dashed curves are the value of potential function along the trajectory and the solid curves are the values of the corresponding Lyapunov functions. Lie GD (Eq. I has f been chosen as 1/L [32] Thm. 151. We observe: 1. Lie NAG-SC converges much faster than Lie Heavy-Balt Baal,, especially on ill-conditioned problems. 2. Although the potential function not monotonely decreasing, the Lyapunov is.
Figure 2:
Cifar 10 validation error
Cifar 100 validation error
dean 5GD
Euclidean SGD
Lie Heavy-Ball
33.5%
Lie Heavy-Ball
10.5%
Lie NAG-SC
Lie NAG-SC
rate
error rate
33.0%
10.0%
32.5%
9.5%
32.0%
9.0%
165
170
1
160
160 19s
200
165
170
175
165 epoch
180
195
200
epoch
(a)
(b)
Figure 3: Training curve when applying our Lie HB and Lie NAG-SC to vision transformers. Forcing the query matrices and the key matrices on SO(n) 19 Orthogonality across heads] led to reduced training error. Moreover, validation error is also improved (Tab. 2
three input matrices Q, and V all have dimension wwwpueenneeeeggteeeeeee dy and d, are usually smaller than dmoddc--
In the case diusdel dg, which is satisfied in many popular models, apply the constraint 'orthogonality across heads" [19 and require Concat(W;?
I..., Ahead) and Concat Concat(W:K ;i 1..., Phead) to be in 50( We compare the performance of our newly proposed optimizer with the existing ones (the optimizer in [19 is identical Lie Heavy-Ball on SO(n)). Fig. 3 and
Tab. [ are the validation eтror when we train a vision transformer (2) with 6.3M parameters from scratch on CIFAR, showing improvement Lie NAG-SC comparing the state-of-the- algorithm Lie Heavy-Ball. The computations are done on a single Nvidia V100 GPU. The model structures and hyperparameters are identical as Sec. 3.2 in 19] Each presented result is the average of independent runs.
Euclidean SGD
Lie HB
Lie NAG-SC
CIFAR 10
9.84%
9.12%
8.77%
CIFAR 100
32.68%
3..3%
31.38%
Table 2: Validation error rate of vision transformer trained by different algorithms on CIFAR, showing the performance ordered by Euclidean GD Lie Heavy-Ball < Lie NAG-SC for both CIFAR 10 and 100. The blue font means the lowest error rate.
10

---

Acknowledgments and Disclosure of Funding
The authors are grateful for the partially support by NSF DMS- 1847802, Cullen- Peck Scholarship. and GT-Emory Humanity.Al Award. We thank the anonymous reviewers for their helpful comments.
References
[1] Kwangjun Ahn and Suvrit Sra. From nesterov's estimate sequence to riemannian acceleration. In Conference on Learning Theory, pages 84-118 118. PMLR, 2020.
[2] Dosovitskiy Alexey. An image is worth 16x words: Transformers for image recognition at scale. arXiv preprint arXiv: 2010. 19299, 2020.
[3] Foivos Alimisis, Antonio Orvieto, Gary Bécigneul, and Aurelien Lucchi. A continuous- time perspective for modeling acceleration in riemannian optimization. In International Conference on Artificial Intelligence and Statistics, pages 1297-1307. PMLR, 2020.
[4] Foivos Alimisis, Antonio Orvieto, Gary Becigneul, and Aurelien Lucchi. Momentum improves optimization on riemannian manifolds. In International conference on artificial intelligence and statistics, pages 1351- PMLR, 2021.
[5] Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks.
In International conference on machine learning, pages 1120-1128 PMLR, 2016.
[6] Silvere Bonnabel. Stochastic gradient descent on riemannian manifolds. IEEE Transactions on Automatic Control, 58(9):2217-222) 2013.
[7] Roger Brockett. Least squares matching problems. Linear Algebra and its applications, 122: 761-777, 1989.
[8] Zhehui Chen, Xingguo Li, Lin Yang. Jarvis Haupt, and Tuo Zhao On constrained nonconvex stochastic optimization: A case study for generalized eigenvalue decomposition, In The 22nd International Conference on Artificial Intelligence and Statistics, pages 916-925, PMLR, 2019.
[9] Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness adversarial examples. In International conference on machine learning, pages 854-863. PMLR, 2017.
[10] Christopher Criscitiello and Nicolas Boumal. Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles. In Conference on Learning Theory, pages 496-549 542. PMLR, 2022.
[11] Christopher Criscitiello and Nicolas Boumal. An accelerated first-order method for non-convex optimization manifolds. Foundations of Computational Mathematics, 1334)-1433-150, 2023.
[12) Christopher Criscitiello and Nicolas Boumal. Curvature and complexity: Better lower bounds for geodesically convex optimization. The Thirty Sixth Annual Conference on Learning Theory, pages 2969-3013. PMLR, 2023.
[13] EB Dynkin. Calculation of the coefficients in the campbell haasdooff formula. DYNKIN, EB Selected Papers of EB Dynkin with Commentary. Ed. by YUSHKEVICH, AA, pages 31-35, 2000.
[14] Nicolas Guigui and Xavier Pennec. A reduced parallel transport equation lie groups with left-invariant metric. In Geometric Science of Information: 5th International Conference, GSI 2021, Paris, France, July 21-23, 2021, Proceedings 5, pages 119-126. Springer, 2021.
[15] Ernst Hairer, Marlis Hochbruck, Arich Iserles, and Christian Lubich. Geometric numerical integration. Oberwolfach Reports, 3(1):805-882 882, 2006.
[16] Linus Hamilton and Ankur Moitra. A no-go theorem for robust acceleration in the hyperbolic plane. NeurIPS, 2021.

---

[17] Kyle Helfrich, Devin Willmott, and Qiang Ye. Orthogonal recurrent neural networks with scaled cayley transform, In International Conference on Machine Learning, pages 1969-1978. PMLR, 2018.
[18] Lingkai Kong and Molei Tao. Convergence of kinetic langevin monte carlo on lie groups. COLT, 2024.
[19] Lingkai Kong, Yuqing Wang, and Molei Tao. Momentum stiefel optimizer, with applications to suitably-orthogonal attention, and optimal transport. ICLR, 2023.
[20] John Milnor. Curvatures of left invariant metries on lie groups, 1976.
[21] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
[22] Sean O'Hagan. Uniform sampling methods for various compact spaces. 2007.
[23] Boris T Polyak. Introduction to optimization. 1987.
[24] Zeju Qiu, Weiyang Liu, Haiwen Feng, Yuxuan Xue, Yao Feng, Zhen Liu, Dan Zhang, Adrian Weller, and Bernhard Schölkopf. Controlling text-to-image diffusion by orthogonal finetuning. Advances in Neural Information Processing Systems, 36:79320-79362, 2023.
[25] Bin Shi, Simon S Du, Michael Jordan, and Weijie J Su. Understanding the acceleration phenomenon via high-resolution differential equations. Mathematical Programming, pages 1-70, 2021.
[26] Molei Tao and Tomoki Ohsawa. Variational optimization on lie groups, with examples of leading (generalized) eigenvalue problems. In International Conference Artificial Intelligence and Statistics, pages 4269 4280. PMLR, 2020.
[27] Nilesh Tripuraneni, Nicolas Flammarion, Francis Bach, and Michael Jordan. Averaging stochastic gradient descent riemannian manifolds. In Conference On Learning Theory, pages 650-687. PMLR, 2018.
[28] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[29] Zaiwen Wen and Wotao Yin. A feasible method for optimization with orthogonality constraints. Mathematical Programming, 142(1):397-434, 2013.
[30] Andre Wibisono, Ashia Wilson, and Michael Jordan. A variational perspective on accelerated methods in optimization. proceedings of the National Academy of Sciences, 13344):E7351- E7358, 2016.
[31] Shing-Tung Yau. Non-existence of continuous convex functions on certain riemannian manifolds. Mathematische Annalen, 207:269-270, 1974.
[32] Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. In Conference on learning theory, pages 1617-1638. PMLR, 2016.
[33] Hongyi Zhang and Suvrit Sra. Towards riemannian accelerated gradient methods, arXiv preprint 1806 02812, 2018
12

---

A Properties of Lie groups and functions on Lie groups
A.1 More details about compact Lie groups with left-invariant metric
Comparing with the Euclidean space, Lie groups lack of commutativity, i.c., for 9.9 G, 99 and ğg are not necessarily equal. This can also be characterized by the non-trivial Lie bracket [ This non-commutativity leads to the fact that exp(X) X) exp(Y) exp(X X + YY. An explicit expression for log(cxp(( X) cx)(Y)) is given by Dynkin's 's formula [33. Utilizing Dynkin's 's formula, we quantify d log in the following.
Corollary 15 (Differential of logarithm). logg g is well defined, then the differential of logarithm on given by
de logg (olo (T.LyE) ((.lo))(TTLL))) ToLy (p(adiogg) Aε ege
(17)
where the power series p is defined in Eq. (16
The vanishment of ad? [ can also be understood as the group structure and the Riemannian structure compatible. See [8] for more discussion. Under such assumption, have the following
properties:
Corollary 16. Suppose we have adx is skew-adjoint VX g. Then for any g e G and any g such that de logg is well-defined, we huve
(de log logg) g.)
Corollary 17. When de log is well-defined and ad is skew-adjoinl V g. we have
(dg logg g, <) s 1El
Corollary 18. Define
A max |adxllop [X|=1
(18)
When d(g, e) S A for some (0, 2T), have
|d Id] s g(a)
where q defined by
[p(ri) - 11 (xx)=
ri
(19)
008 ssnn
CO8 -sin
COS T
with p defined in Eq. (66).
Remark 19 (About existence and uniqueness of log). As the inverse of exp, the operator log may not be uniquely defined globally. However, we are always considering in a unique geodesic subset of the Lie group, where log is defined uniquely in such subset of Lie group. Similarly, even if do not have globally geodesically strongly convex functions, we only require locally strong convexity.
A.2
More details about functions on Lie groups
The commonly used geodesic L-smooth manifold M is given by the following definition [e.g..
32
Def. 5]:
Definition 20 (Geodesically L-smooth). U - IR is geodesically L-smooth for any g, E,M
( s Ld(g.9)
where g is the parallel transport from 9 to g.
Lemma 21. Under the assumption of ad's is skew-adjoint V.X g. Def. 4 is identical to Def 20
13

---

1 Proof of Lemma 27 For any 9.9 E G, consider the shortest geodesic Φ [0. + G connecting
and i and denote ç T - (g) Using the condition ad is skew-adjoint, we have ((t) 0 and Te is parallel along by checking the condition for parallel transport [14] Thm. 1]:
_ f = - (()
dt
This tells that
Together with the metric is left-invariant, we have
Ld(g.9)
which is identical to Def.
Corollary 22 (Properties of L-smooth functions), U G + R is L-smooth, then for any 9 G, we have
L (g) s (U() (1) 9)
- (g.0) 2
(20)
We denote the one of the shortest geodesic connecting and 9 as g()). i.e., [0, + G with g(0) = and g(1) 9. g()) gexp((E) for some & g with ||E|| d(g.9). Then
Proof of Cor. 22
U())-U()
- (ToL, VU())) I (ToLOCE), (U((
- (T,T,L, vV(())+ + [/' (5.T (4TT)) de
s <S,,TyL vU()))+ [." (101
((.T)))-VV()))+ VU(g)) + ["' [
(E,T,Ly- 2 (g.
Lemma 23 (Co-coercivity). If the function U G + IR is both L-smooth and convex on a geodesically convex set G. then we have for any 9, 9 S,
U 2 ( (TL)))))((L---VV((())o).)o
(21)
2T.
Proof of Lemma
23
By convexity, we have for any g G, & and Le [0,1]]
U expe))(( - (T VU(g)
U(g) U(gexp((())))))))))))))))))(())) gexp((ee) - "eap:/seeeepopppeeeeeeeee/eeeeee
We sum these two inequalities and have
which tells that
i
[T (eep((1)) WeanesseeeeeeeeeeVVeeeeeee H.g
for some linear map H. g - g with eigenvalues between and I., i.e., H, L for any
t E [0, 1].
14

---

Now, we select the shortest geodesic connection and 3, defined by g(t) == eexp(tE), with 9 g eE and || d(g.9). By
S/¹
T To(t) (U())))) 1TLLL--V(0)
Os g -xppe>-) (Uxpexxst)))))))
L H.dds
we have
U(i) U())
L (U(()
L (TLL,,V()) S a Too) (cs) (V(((s)) E))
(ToL VU()).)+ [ H.Eds,
(TLL (U())) L. S (Hdss)
(TgL (V()) 1 [ [. (H,E. E)dsdt
TTh vU()).E 1
2L L'' S. (H.E, H&E)dsdl
1
2 ['' "So" HoLds) dt
(T (U())
2L
di L' [TgL -TgL (VU())
(TgL,--U()))
2L
1
-Tgg)-
Corollary 24. If the function U G + IR is both L-smooth and convex on geodesically convex set S then we have for any 9.9 9 S.
(TgL,- (To4--wGo--TL, (U)) (6)) 1
(22)
Proof. By exchanging g and و in Eq. 21 we have
2 U(g) (TyLg- VU) 9) 21
(23)
Summing up 21 and 23 gives us the desired result.
Corollary 25 (Properties of ju-strongly convex functions). Suppose U G IR is geodesic-u-stronggyy convex on a geodesically convex set c G, then for any 9.9 S,
(TgLy>VU())) (V)(), 9) > ud (g.
(24)
Proof of Cor. 25
By the definition of geodessic//-strongly convex functions in Eq. (4) we have
-()))(())) (TyLe VV( 9) log g g]
U(6) - U())) VU 9) log "g
Summing them up and using gog log g g gives the conclusion.
15

---

B
More details about optimization ODE
Proof of Thm. o By direct calculation,
d
F((((),(())) (T.LyS, vU(g)) (5,E)
dt
=->1<|
Lemma 26 (Monotonicity of the Lyapunov function), Assume adx is skew-adjoint for any X E Suppose there a geodesically convex set G satisfying:
U is geodesii-p-strrngge convex on geodesically convex set S G.
9> is the minimun of U S.
g(t) S for all t 2 0.
logg.'' 9 and its differential is well-defined for all g S.
Then the solution of ODE
satisfies
CDEE (g(1),((t) s cooe ODE (s(t),((1))
(25)
dt
with the convergence rate given by
2
CODE := 7 min
/ 1
Proof of Lemma
26
The time derivative of L is
+ 1 (
- c
ODE
dt
lolog -od.g -
(U.TLL (E.E) (s. TgL.
(logg:' 9. de loggo" 9) (logg, -1 5) 7
(logg g, Tygg vV(
2
2
2
(s. loggoo. 9. 9)
7 (5,6) (s, vg))
=->(E, 7 (log g. T.ToLo lv)) + (logg. g, T,
2 2 [c. de log 9)
2 (5.5)
where the second last equation is by Cor. and the last inequality is by Cor. 17 strong convexity in Eq. 4 and Cor. 25 for any 1].
By the property of
ODE dt
S s- -2(()(U -())))
> + (1 (1-2)) pnd (g..9) )++ + [K(²) (
(26)
where À is constant to be determined later.
Next, we try give CODE an upper bound. By Cauchy-Schwarz inequaaiinl
|| g. g + E| 2 2 + IIE1²)
and further
CDEE (U + 3 111 d (g.g-)
72
(27)
16

---

Splitting scheme
Heavy ball
velocity
1-e-th
friction parameter
7
(1-e-711
step size
h
1-0-th
Bey
Table 3; Change of variable between Heavy-bal and splitting scheme
Compare the coefficients in Eq. 26 and 27
we have
ODE
CODE ODE
CDE
dt
where the convergence rate CODE is given by
CODE == 7
min
3 ?2 2 + (1 (1- 2) 11
2
2
? min
^o 3' 72
4
(2 })}
2
By selecting A=
2p uty2
to make X = /
(2 (2-X) A) satisfied, we have the desired result.
Proof of Thm.
9 This is the direct corollary from Cor. g and Lemma 26
C More details about Heavy-Ball discretization
Remark 27 (Polyak's Heavy ball 23
Heavy-ball scheme in the Euclidean space is
Tk+1 + ax - -x--1) -VUU
where and B3 are positive parameters. We now write it into position-velocity form. By setting Uk11 28+1-Bk we have
v
Sk+1 I4 + BBE++1
Uk+1 02 - (zVU(xx)
We perform the change of variables given by /B h a + 1 1- yh gives
IK-1 24. hu
Uh+1 Uh+1= = (1-1n)11hhee (vv)
which is the Euclidean version corresponding to Eq.
Remark 28 (Splitting discretization). The two systems of ODEs in Eq. 8 are both linear and has exact solutions. We will refer to the numerical scheme evolving their exact solution alternatively by splitting discretization. More precisely, this gives us the following numerical scheme:
Mh+1 -Th -x exp(hExx+))
(28)
Ek-1 =
1-c
T
L vVU()))
7
After change of variable the Table 3 becomes Eq.
9
Eq. (88 is similar to the 'NAG-SC" in [26]. The authors provide second-order approximation to the optimization ODE Eq. (2) by evolving the two ODEs in Eq. ( in the following way in each step: 1) evolve E-ODE for h/2 time; 2) evolve g-ODE for h/2 time; 3) evolve E-ODE for h/2 time again. Although this zig-zag scheme is higher-order of appreximation of the optimization ODE comparing to the the splitting approximation mentioned in Rmkk. 28 it still has the same condition number dependence. The reason is, we can take out the first evolution of time h12 for the E-system and becomes identical the splitting scheme (with different initial condition.)
17

---

Before we start the theoretical calculation, we mention that update for & in Heavy-Bal -alll scheme Eq. can also be written as
1 -/hh-
Ek
Ek+1 + 1 1-7hh -
(29)
which will be helpful later.
Proof of Thm.
77 Using Eq.
29 have the following calculation of EH
(gk, Ex)
EBB (gk-1, Ex-11)
EB (Ok:
(0k: {k) EB (9N-1;
(1 (1-gh)²
= =U(gk) - (gk-11)+
(1Exl 2 -11Ex-1
2
(1 (1-9
h
= ((0x-1exp((hx)) (gh-11)
|ExI1
Ek +
1 7/h Tyn Lon 1 VU (Ok(0-1))
2
1 7/h
(1th-
-
72
122
U((x-1exp(hEf)) (gh-11)
2 -I(EAT To -
(U(
[VU((b)))]
Lh?
22h²
h2
$ hh T' -1 (gx-1))
|Ealll
(7/2-
2
VU
2
2
$ 1 (1: - 2
h VVU
2
where the second last inequality the property of L-smooth functions given in Eq. 20
When h T have h2 2-22h++ 2 -7h, and EB (gk, Ex) HB Ex- /
The design of modified energy for Heavy-Ball in Eq. 110 and Thm. 77 is new, and is different from modified potential function in existing works (e.g.. (SSI). Our modified energy is not designed to let the Hamiltonian system to have higher order of preserving the total energy. but is defined to ensure monotonicity of the modified energy to ensure global convergence of the numerical scheme.
Remark 29.
Remark 30. We specially choose our update of numerical scheme in Eq. 4 (and also later Eq. (13 for NAG-SC) to ensure such natural form of the modified energy. If we choose to update g first and then (e.g.. (251), the modified energy will have to be evaluated at different time step, EHB Ex). for example.
Proof of Cor 12
We prove this by induction. Suppose have g So. By the dissipation of the HB (gk, & ) s HB (go, Eo). As a result,
modified energy Thm. 11
[|E (1 - -- Vl)
(1 -h)
(1 (1- E (gk, Ex) + h)VU())))
$ / 2E (go,Eu) h max VU
Since have 9k-1 96 (xp((hx=)) we have d(gh+1 9k) s h||Ek+all. Together with the condition that U(g==) S Eii (g Ek+1) S u, we have 2k+1 E Sg. Mathematical induction gives the desired result.
Lemma 31. Assume adx is skew-adjoint for any X g. Suppose there is geodesically convex set S G satisfying:
U is geodesically p-strongly convex convex set S c G.
gs is the minima of U on S.
18

---

& S for all & E N.
logg.'s g and its differential is well-defined for all g S.
Then we have
h
3r h
HB k+1
-bunLk+1
|VU(((+)))
2(1 y/1)
4L
1-yh
where Pag is given by
?h ph(1 - -hh
27/h
bHR == min
27
3(1 ((1-
Proof of Lemma
31 For (gks Ex) following the Heavy-Ball scheme Eq. 9 we use the shorthand notation of CHB HB (gk: Ek), which gives
1
- I1EA
2
(U(gh-))- - U(.)))
2
log g. yn + Ex
(30)
1-7h
1-
Evaluate of the three terms in CHB L separately:
The first term: By co-coercivity in Lemma 23
we have
(U(g))-U(gt))
- (gk-1))
7h
(T (U()))())))))
h
1 yh
1
1
(T Loc (gu())) Ton-1Lou. VVU (VU(9)1))
T
2L
1-2h
The second term: Using Eq.
(29). have
1
[kt11 12- -Exll²)
4
1 I1Ektz - -xxl?
(Sk+1 Ec, Ek+z)
7/
|Ex+zl
1h
2(1 211-7h)
h
2(1 7h) (Ex+1,
Ih
|lE Exl 1
The third term: Define a parametric curve [0, h]
as gr == ga exp(tEx+1)
2
log ge gb. Ex 1')
7
7
log gt ge+t + Ex+1
yh.
7h
1
()11
2
log Ib + Ext1 112
logg.' 9h+1 + Ext1
1-7h
4
7h
(|]
7
logg, gb + Ex+1
7
log g. 9) Ex 11)
1-7h
1h
-
S.") h d
7
1 - 7 logg. ge + Ext2
log g. 9i + Ext1 dt
2 J
dt
1 - 7
7
logg." gb + Ex+1
7
log g. 9) + Ex 19)
( 1-7h
1 1-
19

---

We evaluate the two terms separately.
1 logg. gggg.e Ekt1) --
7
7 log logg, It Ex-1 )at
dl
7
den1 logg, 1 9b, 1 1-
7
log gr + ExO1 ydl
7h.
7
7
dean go 9t, 1-
logg gx 91 dt
- 7h
7
dew. logg." gr, Ex+1 dt
yh
72
Lo" h
7/ (fK+2, log 91) dt + 1 -- l1Ek+1 12
$
(1 (1- -1))
72
S. h
72h
7/e
(Le+), 9: -logg.g gx)
(1 - (h) (fe.1, loogoog 9x)= (l)ggg"')))))))))))))))))))))9
11Ex-1 11?
(1 (1-71) (h)
1 1 yh
72
Lo (LaNL Jh" dean logg do dt
72h
7h
(1-ah)² (5k+1, 10050''900 (kk)
16-+1 11
(1 (1-yh) (1-x))²
1 1- 7h
72
Jo h Sn (EKrI, denn logg.' go ds)dsdt
h2h
7/
(1 (1- 1,0-1,,0gg." 9k)
|Ex+1l
(1 (1-yh)2
1 -h
72
Sam n
Jn |Ek- (fdllddsdl + (1 (1- (EA. log.oo "/- gk)
72
1-7h llEx. 12
7h
$ (1 -1-18 -h))
h2h²
72h
7h
2(1 -//)² |EA+I
(1-7h)² (Sk+1, log ge 9t)
1- 1-yh" llEk+a| 12
Using the update in Eq. (2 we have
2
γ log
7 1- logg gk + Ex
logge' 9.' 9k+1 Ex+1
7h
27
EN-1 Ex: 1 -h
log y--² Iu Ex + +Ex
7h
h
27 logg.' gx +
2 2-
h
1 - 7/ - Tyn - -U(()))
Ex+1 +
Ek+1
Ty Lo- vU(x))
1 1-
1 y/h
1 1-
2/
gx) 71(22
7/1) -11)
2/h
(1 (1-71)² (Ek+1, log
Moog.i'90 (Ek+1,log
||Ext1 12
(1 (1->1)2 (T Lo ((()),, log go 9k)
(1 (1-)
2h
2
(1-7h)2 (Ter
(1- (gx)))
Sum them up, we have
1
1 -
--1-1 1-
log go + Es I²)
log 9k+19. + Ex+11
-1
4
1 1-7h 7
h
(T Lan- (U(g)) Exmi)
IIh
2(1 72)2 )
7/h
(Tp. Lu.Lo---U logg gm)
IIh
2(1 -h))
1,2
4(1 4(17// (V(g))))
III;
20

---

Take a closer look:
h
11 + 111==
(Tg Ln. VU())),
(T WUth))(
2
2(1 [1)]
2(1 yh)2
h
Ty oz vV(
1- 7h {k+1
2(1 -hh)
h
TycL (V(())))
2(1 -?h)²
1 1 112 1T 1II3 - Ex 1 1-
h
T bu (U(g))) / s0
Now we sum everything up
7h 2(1 (h) ((T (U,) 9x) gx)+ 1k++11²) 2(1-
h²
CHB <
[V(()))
By Eq.
(strong convexity) and Eq. 2 s (T -xx VU log. 9t)
22
(corollary of co-coercivity) of U, we have U (gg))
U(g.)=
CHB k-1
- HBB
7h
((U((x)-((g.) + M |oggo' 9x 2+ *11Ex+11 11xx)11))
2(1 7h)
h
(U(()) - -U())) I- 1 (V
2(1 h/)
yh
(1 - -U(g.) +
+ 110 g gh l(ar11)))
(31)
2(1 7/)
h
4L 1-7h \+((1))1
3r
2(1 - -h)
inequality gives
S 1 1 yh -U + 2(1 - -h) log 9. gu 12 +
1
72
3 -EEE11
(32)
4
Comparing the coefficients in Eq. 31 and 32 gives us the desired result.
Lemma 32 (Monotonicity of the Lyapunov function for Heavy-Ba scheme). Assume the conditions in Lemma 31 is satisfied. By choosing 2 and step size
La have bнв TGT. and
4f,
CHB Cun_
(33)
by defining CuB == (1+ bbb)
Proof of Lemma 32
By our choice of h and y makes
3y 41 1-78
0, and the convergence rate by
Lemma
Proof of Thm.
13
This a direct corollary of Lemma 32 and Cor.
D More details about NAG-SC discretization
Lemma 33. Assume adx is skew-adjoint for any X g. Suppose there is geodesically convex c G satisfying:
U is geodesically p-strongly convex convex set c G.
g- is the minima of U on S.
gk S for all t 0.
21

---

logg, 9 and its differential is well-defined for all g S.
maxges , .9) S 7 for some a 2T.
Setting h min|
VTT. 2p(a) and y= 2/P, have
SC Cx CNAG-SC brt
SAG.SC
for the contraction rate bc given by
1
1
bNAG-SC 30
//min
(34)
(2L"" 2p(a)
Proof of Lemma
33 For (g),5k) following the NAG-SC scheme Eq.
(3) we define the shorthand
notation L SA
CNAG-SC Ex),,x), which gives
NAG-SC
1- (0(0-11-U(g..) 2
1
15 2
Ex 1 1-
7 logg.' 9h hVU((n-)) I|²
(((2-hh
4(1 4(1-4h)
(35)
Evaluate of the basic terms of Lk+1
L
-AGGSC first:
The first term: By the property of convex L-smooth functions in Eq.
21
(U(gk) (((kx))
7h
<
(T (V)
I
1 7
1 1
(Tache (Ug Ty, Vi |]]
2T. -7
The second term: NAG-SC scheme in Eq. 13 gives the following:
[
112 -11 11Ex11)
2 (EK+1
EN, Ex+1)
- 1EN+1 Exll
4
7h
115ktal 112
- (T Lou-1 vUK()) VoniLoun (.
2(1-Th)
h
(U( - EllExt1 - Exl =
2(1 - hh)
7h.
11
111
2(1-9h)
h(1-9h)
(Ten Las- VU(gk) - -To 1- ())
Ih
1221- -1 7h)
( (ga) -T -ي -1 V -
Ha
2
h
(T Lgx (U())) Lg -
II
h
IIs
21)
|Ek11 1al?
Il
22

---

"The third term: We consider the parametric curve on G connecting 9k and Jk+1 defined by 9t Is exp(tfx+1), h0.
Sk+1 + 1 1-7h 4
7
logg. 9- 9k+2 + hT nm (gh
Ek +
7 logg. 9b. + hT ge-t Ln VV
1-7h
1
fRe1 +
log 92 -
2k+2 hT on 9-x ((((a))
1
1
Ekt1 + +
log logg yb hTT yu 1-7h
7 y
4
1 1-
4
-
(++1 +
7
log 9k hT su (g(())
Ex [
7 log -. 9k hT su Lo VV (9k-))))) 12
1-7h
4
1-7h
1 (") [C+1
logg 1 9: hT ge -h- VU(()),
1 - deam logg 98 )1)at
2
1-
27
( Ex* +
1- logg." gb hT hT ge (g(())) + hh (U(gk-)) Ex g (V -TT g1Tg L
1
L²" (Sa.1
7
logg -1 9r hT 22 9t (g()),
1- denn loggr 912 8x)a
2
7-
4(1 (h)> ((2-)h)Ek+1 + 2y logg. gh + (3 hT La VU(())) 7 - hT Lg VU
First, we estimate the term 10" (5x.1
log g4 Dt hT gn -0x (u()),, 1- dea. log ( dl
using the property of loo Cor. 16
and 18
log.g
90 Ek-1 hT ge VU (9k), loggo -- 91))
7h
-h logg 9r E denn logg- 9:
7
+ h (To. Lox- (U())), Ex+1) h(Tge Lon VU (gx), dew. loggo' 9i Exta)
$ 1 7h (log gt. Ex+1) |E++1 2 + (( Lax (U(O)) ( +p()) (36)
Taking integral gives
7
logg gi + Ek+1 + hTg. Lu. dea.. logg. 91 )
- 7h
7 (logge gr, Sk-1) |[a+1 2 (
<
1-7h
7
J. (log 9r, Ek-1) dt A +1
1-
We calculate the integral
L." [log.o ge, Ed
L." [M10R00 yos EkrI) Lo (deam logg"' grs Ex.1) d di
<logoo ge. Cx-1)+ f/d Jo 1Emmill drtt
h²
hlogg..' gh. Ek-1) Ex+1l
which gives us
[KX1 + 7 logg, + liT qu VU dea.. log g. g1 de
1-7h
7h
-1)
< 1 7/h
(log g. gr. Ex-1)
2(1 x(1 ||
+ 1/2 ( L... (g)),, + (
23

---

The other term
(h=-> 22 logg. 9s + +33 235-2 L. - - gt m. vV(()))
= (--1(2-7h)lse 16-11 -
9h. Va
- -2 h22- Lon 7ua h
= =-7h(2 - -/) 10 9h Ex+1) 2/ 16 - | + vU(()))
uu -
-2yh(1og go gk, To box vg(()))) (3)22))))UUU(()))
Summing them up, we have
12
[sx11 1-
log
logg.' g. gk+1 hT Lon (V((()))))))))))))))))))))))))))
-
[6
7
logg. gb + hT - VU (gx-1)))))
1-
(1 (1-71)2 (loggr goi Ek+1) 7h(2 (112-91) 7/)
27²h
(1 (1-) 1|Ex+1l2
$
2yh²²
27th²
Ex+1)
1 7h (L
1-
71(2-1 -7h)
2/2h
2h(1 + + 77111)
1|
(1 (1-) (log 9h. Ek+1)
(T (U(()),
(1 (1-7h)2
(1 (1-
27h
13 - 27/h)
(log..'' gki Tyx Lax (U(g))
| 11))
(1 (1-7h)²
2
2h
5
(1 21)) (T gg. (gk()
1 7h
2-hh
13 2
(log oo gk. To Lav vU())))
V (gx))
(1 (1-nh)²
(1 (1-
Eventually, the third term becomes
logge -1 gk+1 + hT st Log VU( ||
Ek+1
7
&e + 1 1h
7
logg." gs + hT gt Lo--1 VU (U(-))))
4
1-7h
hy
2(1 2(1 (11) (T (gh), logg. ( gh)
11h
h
111
2(1 2(1-2/h²
h/2
IIIa
2(1 -7h)
h22
1 Lg. (gu)))
1114
4(1 -h)²
7/2²
2(1- (1->h)* (()) ((a)/((/)))
extra term from curvature
24

---

We sum the all the terms up to get
Lk-1
SAG-SC
Lx
NAG-SC
7h
11-h (ooLoxx Lox (V(()),logg;; gk) |(x-1 11)
1
Ih IIh
2(1-211 - -h)
h
T gg (VU(g)) 1 1-9h Ek+1 Ek hT bnx vU(()))
1 11I+ III.
2(1 -711)
h(1 hh)
(TocL -VU(()))) - -T---
112
2²
T 9h g0-1 (9k( - -T 1 (U((K-1))))))))))) T Lon (U(()))
111
2
2h
h.2
(ER+1 Ex, ( 1Ex+1 - Exll" (1- 7h)2
VU (U(g))
7ih
} + 1I.
II III4
1/1
1- - -12 (1 | -o Tg- 1-
I2 IIs
(1(2-)h)
(1 1V(
Additional term
4(1-7h)
7h?
2(1 - -h) p(a)llu(())lllee
extra term from curvature
11 III2 + 11I3
2
h?
(T' (.LLLg-VV((9)) - (U (VU
IV1
2(1 (11-hh)
Ty Toc VU(())
IV22
2(1 22)2
k--1 Ls
CNAG-SC
CNAG-CC
7h 2(1 77/)
log - [|
11 1-
II III + IV2
1- 7h
(T LogLane Aah - -gU((g)) - -Tyr-1 Lo VU(gk-)), log 1og 97-19k)
I12
2
122
7h
(Tex ( - -Ty -- VU (g)--))) Top. VU
II IV
2
7h
1
-/h) |T (12
Lox- vUnx) Tyx VL (U
I Il
T, 1 7h.
h² 2 2-2-/1 7h
(IV((())) ||0((
Additional term
4 7h
7h2
2(1 - ((1--h) (11-)h)y(a)/aaa PU)
extra term from curvature
1/2 [ Lg vga)) -Ton .. VU ||( 1 - -/
11 + IV Additional term
(T4, + IV Additional term)
(I2 + (T3)
1/2
1 1- 7h
1
T Lg. (VL())) - 1o.,,-9-1 IV (9)-1)))
2
1 1-2h
7h
1 7h Lh
25

---

NAG-SC NNAG-SC.
Lk
2(1 -7h) (1-7% ( (1-77
7/
(o logg. gx) h² VU((s)) + [[5x+2l]
$
1 7
(Tg. Lgx (gx) - log gk
h²
1
+
1 7/h +
| ox (((())) gn
2
1 1- 1- -h LR2
7/2
+ 2(1 2h) p(()] 1
extra term from curvature
By the property of L-smoothness in Eq.
22 we have
-u - -T -o-.- (U log 1 11 VU( - 1n-11- VU (ok-1))
and
NAGGSC Lxx
NAG-SC
<
7/
1- (TT (Lth) gx) -n2[))((VUssITP lExtal? +
2(1 7/)
( 122 || Lox - (gk())) Loc ((
1 7h
2
1-
7h2
[U
2(1 2(1->h)
When h s 1. together with Lemma 33 and Cauchy-Schwarz inequality, we have
V2L"
NAG-SC
Cx
NAG-SC
$ 2(1 -1)) 11-7h (1-1//
7h
(1T ((T (U(g) gu) h(([v((())))))) + [(66-111²)
?11
+ 2(1 - 7h)
((c))
7h
(T Lo (oU())), gu) h(([v(())))))))) + [[66-111²)
2(1-2h)
11
7h?
4(1 -h) p(a) (XI x
+
where X 0 is parameter to be chosen later. Using property of L-smoothness in Eq. (21). (22) and
property of p-strong convexity in Eq. (24). have for any A 0 and X2 2 satisfying X1 + Xa
2(1 2(1-7h)² 2/)² 7h
(C - -CNAG-SC
$ (T WouLon VU(H) gk)
M11 - (11-)))ppaa)
(g())) M(1-a)x> "p(a)
+ )1 -11-70(1111)-
| l|
2
2
A
Mdz d (gggg.)
5 5- d1 (2) (g+)))
V |VU(())
2L
h(1 - Ap)ap(a) ())
(gx))) 2 + h(1 h(1->h)) ((1--h)a~-p)) "p(a)
+ + -(1-7h))l1
||Ex- 112
2
2
(h(1-nh))pp +
d
[VU(2))] udz (gggg)))
s s- (e) U ((+)))
2L
(11 7/h) (1 (1- hY ppaa
|[ 2
(37)
2
26

---

Now we try to upper bound Cx Using Cauchy-Schward inequality,
27
9h-1 1- || ?
EK +
lo
9k + hT
1 1-yh
2y
2
33
LEA 2 + 11 (1-gh 1-yh)
s 3
| +
2y
(d(g).9))++ipp + h -
11-70 (-
27h )2)
27 _ (
2
$3
| 2
1 1
|Ealll +2
1-
d (go. 9h) 1121 +
As result, NAG-SC C
3
6-/12
$
1 -h (((n-1)-U(O)))
+
- - +
4 4
(1-
1lEx1
6y²
(3 (2-7h)
df (g+.9k)
1 h2(|VU(9X-11))
(1 (1-7h)2²
(4 4(1 (11-/h)
(U(nk-)) 1) - (g.)) + 1- 2y2h + 77,212
+ 6.,
1 --2hh
1
de (g+,gk)
+
1121 (/|VU(9--)))
1 yh
(1-gh)²
(1-
4(1 -h)
1
1 1 1-2 h?2
1 2 77?21
372
5
((1-2h) 2L (U(gk-1) - U(.)) +
lEall
2(1-2h) ol (g 9k)
1 7h
4(1 -hh
5- 2
(U(gk-1)- - U(g.)) 1-27h 7721/²
372
$
|Ex| + 2(1 - -h)
dl (g.:9k)
4(1 -h)
(1-7h)²
which is the same as
2(1 2 NC
$ 2
5 27h
(((g--)-U((g)))) 2(1- - 101-222+++77 7,/1/3)
||Ex|12 2+
372
de (g..9k)
(38)
1 1-yh
1 yh
We suppose
h(1 1(1-711)Xp(a)
A 0
h22
(39)
2
2L
As result, by comparing the parameters in Eq.
and (37p. we have the contraction rate is
7/2
2((2 λ1 -22)
hd
p(a)
p(aa)
(1->h)²
uA2(1- 11-7/1 7h)
DNAG-SC 2
1-7h min
1
5 --/h
2
2(1 27hh + 772)22)
6-2
2(2 - A1= -22)
(1- (1-h>*
h1 p(a)
1- -
= =>hmin min
(5- (1-22)))1-7/1))
2
2(1 - 2 + 7>2)) 6.22
Now we try to give lower bound for the contraction rate upon a set of parameters A1, X2). By assuming 7/1 S 7, we have
\1 -2))) 1
hx-1
p(a)
μdz
INAG-SC 2 7/ min
2(2 2(2->x:
2
2
6-
Choosing
\ 2L hhdp(a) h22
make Eq. (39 satisfied. By assuming h S 22. we choose
1 1 hhp(a) ()
1 12
27

---

to make 2(2- -
6,2-
Then we have
DNAG-SC 2 2/mii
1
1
h(a1p(a)
hd
p(a)
(1 - (1-hAp(a))}
2
2
'6(72 n.)
1
11-1 p(a)
1
(1 (--np((a))
2
2
30
hp(aa
1
2 2 ph min
(1 - hp(a))
2
30
by choosing 2/1,, same as continuous case and simply choose X 1.
bNAG-SC 2 2/ A//mmin
h(2 (2222pp(a),
hh1 h(1 hbp(a))
Setting h min V2L 2x()
have
h bNAG-SC 2 2
60
1 miminn
30
( 2p(a)
which gives us the desired result.
Corollary 34. If the iteration for NAG-SC is initialized by 90 E So, with (go, Eo) satisfying NAGGSCC
S ( (1-7h)u
for some with the u sub-level set of satisfying Eq. 15 Then we have yr So for any k for the NAG-SC scheme Eq.
13) when h s V 21'
Proof of Cor. 34
First we prove LNAG.SC 1/4 By L-smoothness and geodesic convexity,
Lemma gives
U(g)-U(g))) 2 [V()))1 VgE
(2-x))) 2(1-> leading to NAG.SC (g. 2 =
As result, when 1 S 2L we have I(I-クグ)
Now we are ready to prove this corollary by induction. Suppose we have 0k-1 E So By the monotonicity of the Lyapunov function, L RAG-SC (gk, (x) CNAGGSC(go. (go, Eo). As result,
|[&l S V /4C s 2 CNAG-SC
Since we have = Ih-1 exp()(x)) we have d(gk,gh-) 1) s h/|Ex|l- Together with the condition that ((g-11) s (1- (1- CAGG-SC (1->h)u, we have gle E Sg. Mathematical induction gives the desired result.
Proof of Thm.
14 This is the direct corollary from Lemma 33 and Cor. 34 when defining CNAG-SC t= (1 + bNAG sc) with bNAG-SC is given in Eq. 34
Remark 35 (Why Lie NAG-SC losses convergence rate comparing to the Euclidean case). In order to utilize the extra term h (T Lo. -VX()) - 1 -VU (UK())))) in Eq. (1)). Lyapunov function Eq. (4) has the term EN I-nh loggg" 9k+1 + hVU(g)), and the term needs to be quantified, consequently. However, due the non-linearity of the Lie group, we have make the assumption that ge-1 and ga are close ge, leading to the space is "nearly linear', so that we can bound the error from the non-linearity of the space using Cor. 18 Please see the proof of Lemma 33 Eq. (36) for more details.
(log g.' gi+1 - log go gu. Top. UUU
However, such loss of convergence rate due to curved spaces is also observed in some of the best results so far [33 17.
For heavy-bal ball scheme, the design of the Lyapunov function only has the term quantify CHB
1-7h logg." g- 9k Ek.
and we can use the properties Eq. (16) and (17
CHB
28

---

D.1 Modified energy for NAG-SC
Remark 36 (Why we cannot have an modified energy for NAG-SC). An 'modified energy' for Lie NAG-SC is provided in Eq. 41), whose monotonicity is shown in Thm. 37 The modified energy is global defined and required only L-smoothness. However, the failure for this eenergy function' is because its monotonicity requires step size O provides acceleration.
/B which is smaller than the step size O VT. that I
Comparing with the Heavy-Baie BBlll scheme, the larger step size and the acceleration of NAG-SC come from extra term (1 h (Toz Lg - (gk)
g 1-2 (-VU(g)-1) which is closely related to co-coercivity in Lemma 23 However, co-coercivity requires (local) geodesic convexity and L- smoothness at the same time, which is not available when we are considering the convergence
globally.
The update for & in NAG-SC Eq. can be also written
1 - 7h (5x hT Ln. (U())) = (fx-1+ + hT
hTg. gi-1 Lo VU(Ok-1)) - hT Lo.- (gx) (40)
This inspires us define the following modified energy:
(1-yh)2
NAG.SC = = [g) + 2(1 o(1+>h->3) - 1|5 hTghT-
(41)
Theorem 37 (Monotonely decreasing of modified energy of NAG-SC), Assume the potential U is globally L-smooth. When h min [
ENGG-SC (gk. (x)
EANAG-S (gk-1, DOVA-SC(ge-1,,66 Ek-1) $0
where the modified energy NAG-SC is defined in Eq.
Proof of Thm. 37
Given L-smoothness of U, we have
SC (gk: Ex) NAG.SC (g--1,
(1 (1-7h)²
= - (U()))U((n)--)
(ILxx + hTg. -UX -1|E6-1 +TTT 2 a- VU (U))2))) P)
2(1 yh -2-22
(1-7h)²
= - -U(AA))
15 hT ge-1 Lo (Ui
2(1 + 7/h -21122)
(1-71)²
11(2 -11)
|
1 1-7h 7/ &K
ToL-1 (U(
2(1 ((1+7h- 22)
1 1-7h
(1 (1-
U(k)) U (gk-1)
EEN + hT ge Lon -1 -U (gk-1)))
2(1 + 7h ??
((1+>h-7 2212) 115a ++22 Th)
s Lo.. (VU
-1))
= -U(x))-U(xx>
2(1 7 10ch--2110 7212) 15a112 MEA, Lom VVU((-1))
1²(3-227h) \V(()=1))1
2(1 +1/h
By L-smoothness, U(ga) - U (gs- a(EE,, Ty -L-2-111 -1 (U(()-1))
Lh2 |Eal1
E.NAGSCC (gx, Ex) FANAG-SC
Lh 1EE
7/h(2 -t)
||Ex| 2- (3
|VU())-1)1
2 2(1 7/ - 72122
2(1 74 72)12)
Consequently, a sufficient condition for NAGG-SC
(gk, Ex)
F.NGG-SC (gh-11, Ex-1) s 0 can be given by
Lh
7h(2-711
5
2
2(1 + 7/ 72112)
29

---

By assuming v/h S 1, a sufficient condition for this can be given by h 2L. ie., when
S min 1 Y {
7 2T. J
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction stated the contributions, assumptions and limita- tions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The section 'Related work' contains our limitations, comparing with existing results.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-specfiiaatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
31

---

Answer: [Yes]
Justification: We make assumtption of compactness (Assumption 2 L Z-smoothness (Def.
and local geodesic-strong convexity (Def. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Details for numerical experiment are included in Sec. 6 supplementary materials.
Code is provided in
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
32

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Code will be released.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https
/ "pipsscc/puullc//uui /utee//ggudddeeeedSuuuummbbbbi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Details for numerical experiment are included in Sec.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
No statistical error bar is included.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
33

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please see Sec.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We confirm we follow the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This paper focuses on theoretical aspect.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
34

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper focuses on theoretical aspect.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: No existing assets used.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
35

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No new assets introduced.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subject is involved.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No human subject is involved.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
36


Reviews:
[{"review_id": "SU6kCobnw3", "reviewer": "Reviewer_m3jJ", "summary": "The paper proposes a new algorithm (Lie NAG-SC) that converges at accelerated rates on Lie groups when initiated close to the true optimum (local convergence). Theoretical analysis and experimental verification shows good performance.", "questions": "Would you be able to numerically compare the different methods when started from the same random initialisation (i.e. same initial position), far away from the global optimum? \n\nCould you discuss the impact of the parameter p(a) on the rates, and explain the intuition for this parameter in the introduction?\nYou should not claim acceleration without addressing the reduction in rates due to this parameter.", "limitations": "Limitations have been clearly addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theoretical analysis is quite advanced, and as far as we are aware of, this is the first method to achieve local accelerated rates for Lie groups.", "weaknesses": "Both the theory and the experimental evaluation only considered local convergence, i.e. cases when the optimizer is initiated near the global optimum. This is a limitation as the relative behaviour of the algorithms further away from the optimum may be completely different.\n\nThe impact of the parameter p(a) on the rates is not sufficiently clearly discussed. This is related to the curvature of the manifold, as well as how closely it is initiated to the true optimum.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **W1**: Both the theory and the experimental evaluation only considered local convergence, i.e. cases when the optimizer is initiated near the global optimum. This is a limitation as the relative behaviour of the algorithms further away from the optimum may be completely different.\n\nWe agree the expert's opinion that global convergence is interesting. However, due to the lack of global convexity, it is hard to have a global convergence rate. Even in Euclidean space, as far as we know, obtaining a uniform, nonasymptotic bound for the global convergence for the optimization of general nonconvex functions is still an open question.\n\n> **W2**: The impact of the parameter p(a) on the rates is not sufficiently clearly discussed. This is related to the curvature of the manifold, as well as how closely it is initiated to the true optimum.\n\n> **Q2**: Could you discuss the impact of the parameter p(a) on the rates, and explain the intuition for this parameter in the introduction? You should not claim acceleration without addressing the reduction in rates due to this parameter.\n\n\nAs shown in Table 1, $p(a)$ only shows up in the convergence analysis of NAG-SC. The details are in line 280 to 284. In short, $p(a)$ quantifies the loss of convergence induced by the curved space. When close to the minimum, the space is approximately flat. The negative effect of $p(a)$ disappears when $2p(a)<\\sqrt{2L}$ (Table 1 and Thm. 14) and the convergence rate will be the same as Euclidean space. This is the reason we claim acceleration. Similar curvature-dependence of convergence rate can also be found in [1] and [27] in the paper. See also Rmk. 35.\n\n> **Q1**: Would you be able to numerically compare the different methods when started from the same random initialisation (i.e. same initial position), far away from the global optimum?\n\nThank you for the advice and we agree that more numerical results would be helpful. Please see the general rebuttal to all. We added optimizer from Riemannian optimization into comparison and also applied our optimizer to vision transformers with Cifar dataset.", "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": "2oWxI0ziD1", "reviewer": "Reviewer_K3KR", "summary": "This paper explores the optimization of functions defined on Lie groups using momentum-based dynamics. The authors propose two discretization methods, Lie Heavy-Ball and Lie NAG-SC, and analyze their convergence rates.\n\nThe main contributions are as follows:\n1. Provide the first quantitative analysis of Lie group momentum optimizers.\n2. Theoretically show an intuitively constructed momentum optimizer, namely Lie Heavy-Ball, may not yield accelerated convergence.\n3. Generalize technique from Euclidean optimization to propose a Lie group optimizer that provably has acceleration.", "questions": "As I mentioned in the weaknesses, the motivation should be more clear. I want to know the novelty of this work compared with [1]\n\nIs it possible show more experiment results in other problems? \n\nComparision with the experiment results in [1]?\n\n[1]Tao, Molei, and Tomoki Ohsawa. \"Variational optimization on lie groups, with examples of leading (generalized) eigenvalue problems.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2020.", "limitations": "See the weaknesses.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors provide the first quantitative analysis of Lie group momentum optimizers which is significant, since there is no nontrivial convex functions on many Lie groups.\n2. Theoretically show an intuitively constructed momentum optimizer, namely Lie Heavy-Ball, may not yield accelerated convergence.\n3. Generalize technique from Euclidean optimization to propose a Lie group optimizer, Lie NAG-SC, that provably has acceleration.\n4. Comparing to other optimizers that are designed for general manifolds, the proposed approach bypasses the requirements for costly operations.", "weaknesses": "1. The idea of the paper is natural. I think it can be seen as a straightforward extension of the results in [1]. So it may be not novelty.\n2. More emperical results are needed I think. Also it better show the comparision with the result in [1].\n\n\n\n\n\n[1]Tao, Molei, and Tomoki Ohsawa. \"Variational optimization on lie groups, with examples of leading (generalized) eigenvalue problems.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> W1: The idea of the paper is natural. I think it can be seen as a straightforward extension of the results in [Tao & Ohsawa]. So it may be not novelty.\n\n> Q1: I want to know the novelty of this work compared with [Tao & Ohsawa]\n\n[Tao & Ohsawa] is definitely an inspiration to this work. However, their algorithm is essentially the same as our Lie Heavy-Ball (Rmk. 28) and may not have accelerated convergence. The novelties of our paper are \n1) quantification of the convergence rate of Lie Heavy-Ball (not enough acceleration),\n2) a solution, which is a new algorithm Lie NAG-SC,\n3) quantification of the convergence rate of the new algorithm (true acceleration).\n\nIn addition, there is a strong technical contribution, namely all the convergence analyses have to be done for fully non-convex functions, because there is in general no non-constant convex functions on compact Lie groups. Rigorous analysis of nonconvex optimization is always challenging, let alone this time on manifold as well.\n\n\n> W2. More emperical results are needed I think. Also it better show the comparision with the result in [Tao & Ohsawa].\n\n> Q2. Is it possible show more experiment results in other problems? \n\nThank you for the suggestion and we perform more numerical experiments. Please kindly refer to the general rebuttal to all and the rebuttal pdf supplement.\n\n> Q3: Comparision with the experiment results in [Tao & Ohsawa]?\n\nThank you for this suggestion. Lie Heavy-Ball mentioned in our paper is essentially the algorithm in [Tao & Ohsawa] (we will clarify this in a revision). In our section 6.2, [Tao & Ohsawa]/Lie Heavy-Ball is already experimentally compared with our newly proposed Lie NAG-SC. \n\nThe general rebuttal to all and Fig. 2 in the the rebuttal pdf supplement contain more experiments, where Lie HB and Lie NAG-SC are applied to (and compared on) vision transformers on Cifar dataset.", "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": "vxv3TUp9DZ", "reviewer": "Reviewer_dors", "summary": "The authors analyze the momentum method and Nesterov accelerated gradient descent method on the Lie group. With some knowledge of Riemannian geometry, they discuss the computational cost.", "questions": "I think this manuscript is none sense, so I do not ask any questions.", "limitations": "The content are none sense.", "rating": 1, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "I have found none strenghs.", "weaknesses": "I do not know the author's motivation to write this manuscript.  \n\nCould you show me a reasonable example for application in practice, or close to practice? \n\nThere are so many high-level mathematical terminologies, but no essential problems are solved.", "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": "ZdVN9LZNUn", "reviewer": "Reviewer_JEvs", "summary": "This work first analyzes the convergence rate of the Lie group momentum optimizer by applying the techniques from optimization theory over manifolds to optimization over Lie groups and extending the Lyapunov analysis to Lie group settings. They also provide the convergence analysis of the discrete version of the above dynamics by constructing new energy function and a new Lyapunov function. Besides, they extend an acceleration technique from Euclidean case to Lie group case and prove its performance.", "questions": "* In the article, a function $U$ is convex means it is convex in the meaning of Euclidean case, even it is defined on Lie group $\\mathtt{G}$. The convexity means $U$ is convex on $\\mathtt{G}$, where $\\mathtt{G} \\subset \\mathbb{R}^N$ is embedded in Euclidean space. Is that right?\n\n* For equation $(16)$, does $d_{\\xi} \\log g$ means $(d \\log)_{g}(\\xi)$, i.e. the differential of the logarithm at point $g$ mapping $\\xi$ ?\n\n* There may be a typo in equation $(18)$. Is the following statement right? $A := \\max_{\\left\\lVert X \\right\\lVert = 1} \\sigma(\\operatorname{ad}_X)$, where $\\sigma(\\cdot)$ is set of all eigenvalues.\n\n* About the **Assumption 2**, does Lie group $\\mathtt{G}$ need to be connected?", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The authors apply the theories from optimization over general manifolds to considering optimization over Lie groups and carefully analyze the structure of Lie groups such that the general theories have more analytical and tractable formulas. Moreover, they extend techniques from the Euclidean case, like the Lyapunov analysis, and Heavy-Ball algorithm, to the Lie group case, which is both intuitive and rigorous.\n\n* The constructions of the discrete version of the energy function and the Lyapunov function from the continuous version of these functions are insightful and it may be helpful for us to consider a similar problem related to a discrete dynamic system.\n\n* The authors provide intuitive explanations for almost every theory, from which I can see the motivations and it is helpful for understanding the whole picture behind the technical details.", "weaknesses": "* In line $280$ and the proof in the appendix, the authors mentioned the ''curvature'' but the article does not provide much information about that. I would like to know if this ''curvature'' is an intuitive term related to the second-order information or a rigorous term related the curvature information of the Riemannian structure of $\\mathtt{G}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **W1**: In line 280 and the proof in the appendix, the authors mentioned the ''curvature'' but the article does not provide much information about that. I would like to know if this ''curvature'' is an intuitive term related to the second-order information or a rigorous term related the curvature information of the Riemannian structure of $G$.\n\nIt is a rigorous term related to the curvature information of the Riemannian structure of $G$. $p(a)$ is explicitly defined in Eq. 17, and $a$ is defined in line 272 in Thm 14, whose definition depends on $A$ (defined in Eq. 18). Under the inner product making $\\operatorname{ad}$ skew-adjoint in Lemma 3, $A=\\sqrt{\\text{max sectional curvature}}/4$  (Please see Sec. D.2 in [R3] in the reference for more details.)\n\n\n> **Q1**: In the article, a function $U$ is convex means it is convex in the meaning of Euclidean case, even it is defined on Lie group $G$. The convexity means $U$ is convex on $G$, where $G\\subset\\mathbb{R}^n$ is embedded in Euclidean space. Is that right?\n\nThe short answer is no. The convexity under discussion is geodesic convexity, which is different from convexity in ambient Euclidean space after embedding. To illustrate the drastic difference, for example, convex functions on Euclidean spaces must be discussed on a convex set, however, we can still have convex functions on a manifold even if its Euclidean embedding is non-convex.\n\n> **Q2**: For equation (16), does $d_\\xi\\log g$ means $(d\\log)_g(\\xi)$, i.e. the differential of the logarithm at point mapping ?\n\nYes, the expert reviewer is totally correct.\n\n> **Q3**: There may be a typo in equation (18). Is the following statement right? $A:=\\max_{\\|x\\|=1}\\sigma(\\operatorname{ad}_X)$, where $\\sigma(\\cdot)$ is set of all eigenvalues.\n\nWe appreciate the careful review and will correct the embarrassing typo.\n\n> **Q4**: About the Assumption 2, does Lie group $G$ need to be connected?\n \nThanks for a great question. We understand the rationale behind this question, but we don't actually require connectness. The reason is: to prove global convergence, we prove and leverage the monotonicity of an energy function, whose definition does not require connectness. For convergence rate, it is only quantified asymptotically and it does not make a difference with or without connectness.\n\n[R3] Lingkai Kong and Molei Tao. Convergence of kinetic langevin monte carlo on lie groups. COLT, 2024.", "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": "CyIaVUxqvO", "reviewer": "Reviewer_zKf2", "summary": "The authors design and analyze momentum-based algorithms on Lie groups.  They first study ODEs and provide convergence rates for them.  Then they discretize the ODEs (in two different ways -- Lie Heavy Ball and Lie NAG-SC), and show that the second discretization (Lie NAG-SC) has a *locally* accelerated convergence rate.", "questions": "Questions and comments (some of which were already asked in the \"weaknesses\" section):\n\n* Explicitly, what do your algorithms look like when the Lie group is a torus (product of circles)?  Does it reduce to standard NAG?\n\n* Can the authors provide examples of Lie groups used in practice which are not SO(n), U(n), or products of those?\n\n* I am not 100% convinced that the Lie Heavy Ball does not have a locally accelerated rate.  My impression is that, with the right choice of parameters, Heavy Ball is *locally* accelerated (essentially because locally a strongly convex cost function looks like a quadratic): see for example \"Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Łojasiewicz Functions when the Non-Convexity is Averaged-Out\" by Wang, Lin, Wibisono, Hu.  On the other hand, the provided numerical experiments seem to indicate that Lie Heavy Ball is not accelerated (but maybe a different choice of parameters would improve convergence?).\n\n* For SO(n) or U(n), can the authors please explain why the log map and parallel transport are prohibitively costly (in comparison to the exponential)?\n\n* Is it necessary to use the exponential map as the retraction?  From the reviewer's experience, for the manifold SO(n), using the matrix exponential is more expensive than using the QR-retraction.\n\n* Line 277 typo: decreaing -> decreasing", "limitations": "No potential negative societal impacts.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is decently written (but not exceptional).  The most interesting feature of this paper is that one can use the group structure of the Lie group to design optimization algorithms, and avoid parallel transport or the log map usually present in the more general Riemannian setting.", "weaknesses": "(1) The requirement that the manifold is a Lie group is very restrictive.  There are many manifolds used in practice which are not Lie groups but still have very nice structure.  Perhaps the prime example is the Stiefel manifolds (which include spheres).  In many applications (especially those related to low rank problems), it is desirable to work with rectangular matrices like Stiefel matrices because storage required for them is much smaller than square matrices (like in SO(n)).  Can the authors provide examples of Lie groups used in practice which are not SO(n), U(n), or products of those?\n\n(2) The paper fails to cite *many* important prior works, most notably (in this order):\n\n* \"Accelerated gradient methods for geodesically convex optimization: Tractable algorithms and convergence analysis\" by Jungbin Kim and Insoon Yang 2022.  This is the first paper to truly achieve \"acceleration\" on Riemannian manifolds, specifically having *global* complexity guarantees which scale like O(sqrt{condition number}) or O(sqrt{1/epsilon}).  All prior work only achieved acceleration locally, which is *arguably* not too interesting (see below).\n\n* The updated version of \"Global Riemannian Acceleration in Hyperbolic and Spherical Spaces\" by Martinez-Rubio also provides global acceleration rates (albeit only on spaces of constant curvature).  [Previous version had exponential dependence on the curvature/radius; this was reduced to a polynomial dependence in the updated version.]\n\n* Lower bounds and obstructions for acceleration on Riemannian manifolds: (a) \"No-go Theorem for Acceleration in the Hyperbolic Plane\" by Hamilton and Moitra, (b) \"Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles\" by Criscitiello and Boumal, (c) \"Curvature and complexity: Better lower bounds for geodesically convex optimization\" by Criscitiello and Boumal\n\n* Acceleration in the nonconvex case: \"An accelerated first-order method for non-convex optimization on manifolds\" by Criscitiello and Boumal\n\n(3) The paper only provides local acceleration, which is *arguably* not too interesting (at least from a query-complexity viewpoint) because locally manifolds look like Euclidean spaces.  This can be made rigorous: there is a generally method for converting Euclidean algorithms to Riemannian ones which locally have the same convergence guarantees: see for example Appendix D of \"Curvature and complexity: Better lower bounds for geodesically convex optimization\" by Criscitiello and Boumal.\n\n(4) I am not 100% convinced that the Lie Heavy Ball does not have a locally accelerated rate.  My impression is that, with the right choice of parameters, Heavy Ball is *locally* accelerated (essentially because locally a strongly convex cost function looks like a quadratic): see for example \"Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Łojasiewicz Functions when the Non-Convexity is Averaged-Out\" by Wang, Lin, Wibisono, Hu.  On the other hand, the provided numerical experiments seem to indicate that Lie Heavy Ball is not accelerated (but maybe a different choice of parameters would improve convergence?).\n\n(5) For SO(n) or U(n), can the authors please explain why the log map and parallel transport are prohibitively costly (in comparison to the exponential)?\n\n(6) Is it necessary to use the exponential map as the retraction?  From the reviewer's experience, for the manifold SO(n), using the matrix exponential is more expensive than using the QR-retraction.\n\n(7) The experiments performed (the eigen decomposition problem) are limited.  The authors say the eigen decomposition problem \"is a hard non-convex problem on a manifold\".  The reviewer somewhat disagrees: in some sense, it is one of the easiest nonconvex optimization problems as all second order critical points (where gradient = 0, Hessian is PSD) are global minima.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> W1: The requirement that the manifold is a Lie group is very restrictive. There are many manifolds used in practice which are not Lie groups but still have very nice structure. Perhaps the prime example is the Stiefel manifolds. In many applications (especially those related to low rank problems), it is desirable to work with rectangular matrices like Stiefel matrices because storage required for them is much smaller than square matrices (like in SO(n)). \n\n> Q2: Can the authors provide examples of Lie groups used in practice which are not SO(n), U(n), or products of those?\n\nThanks for an opportunity of explanation.\n\n1) *Stiefel versus SO(n).* We agree Stiefel is a very important and useful manifold, but it does not mean SO(n) is not important. Even simple Lie groups like SO(2) and SO(3) are extremely important to applications. For example, machine-learning-based design and generation of molecules (or more precisely, molecular configurations) have already become a big enterprise and a billion-dollar industry. In the majority of research in this direction (e.g., [R5,R6]), side chains are modeled by torsional angles (each in SO(2)), and backbone is modeled by rotational angles (each in SO(3)).\n\n2) *Lie groups in practice that are not SO(n), U(n), or their products.* Heisenberg group plays an important role in quantum mechanics. Lorentz group plays an important role in general relativity. Spin group is necessary for describing Fermions. Symplectic group is used not only in mechanics but also in quantum computing and even cryptography. Projective linear group can find abundant applications in graphics and visions.\n\n> **W2**: The paper fails to cite many important prior works, most notably (in this order):\n\nWe appreciate all the references and we will cite them in a revision. However, our paper focuses on a different algorithm under a different problem setting, and the existence of these paper does not weaken our novelty. Kindly see details below:\n\n> \"Accelerated gradient methods for geodesically convex optimization: Tractable algorithms and convergence analysis\" by Jungbin Kim and Insoon Yang 2022. This is the first paper to truly achieve \"acceleration\" on Riemannian manifolds, specifically having global complexity guarantees which scale like O(sqrt{condition number}) or O(sqrt{1/epsilon}). All prior work only achieved acceleration locally, which is arguably not too interesting (see below).\n\nThis is an interesting paper, however, the proposed algorithm (Algo 1 & 2 in their paper) requires logarithm (which may not be uniquely defined globally on compact manifolds) and the expensive parallel transport. What's more, its global acceleration requires global convexity, which is too strong in our case. \n\n> The updated version of \"Global Riemannian Acceleration in Hyperbolic and Spherical Spaces\" by Martinez-Rubio also provides global acceleration rates (albeit only on spaces of constant curvature). [Previous version had exponential dependence on the curvature/radius; this was reduced to a polynomial dependence in the updated version.]\n\nTheir algorithm (Algo. 1) requires a line search in step 6, which can be hard when applied to complex problems (large-scale and non-convex). In contrast, our algorithm can be easily applied to machine learning problems, e.g., vision transformers in general reply to all.\n\n> Lower bounds and obstructions for acceleration on Riemannian manifolds: (a) \"No-go Theorem for Acceleration in the Hyperbolic Plane\" by Hamilton and Moitra, (b) \"Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles\" by Criscitiello and Boumal, ( c) \"Curvature and complexity: Better lower bounds for geodesically convex optimization\" by Criscitiello and Boumal\n\nThese interesting papers will be cited. In fact, these negative results further illustrate the nontriviality of our result, which is a positive one, and there is no contradiction due to different setups.\n\n> Acceleration in the nonconvex case: \"An accelerated first-order method for non-convex optimization on manifolds\" by Criscitiello and Boumal\n\nThis paper is interesting because it uses the idea of optimizing on the tangent space and utilizing the accelerated algorithms in Euclidean spaces. However, due to this reason, many of its conditions (e.g., A2 on page 14) depend on the local chart and can be hard to check. Instead, for our algorithm, the condition of the objective function, the choice of hyperparameters and the convergence rate are all intrinsic.\n\n> **W3**: The paper only provides local acceleration, which is arguably not too interesting (at least from a query-complexity viewpoint) because locally manifolds look like Euclidean spaces. This can be made rigorous: there is a generally method for converting Euclidean algorithms to Riemannian ones which locally have the same convergence guarantees: see for example Appendix D of \"Curvature and complexity: Better lower bounds for geodesically convex optimization\" by Criscitiello and Boumal.\n\nObtaining a uniform, nonasymptotic bound for the global convergence for the optimization of general nonconvex functions, as far as we know, is still an open question even in Euclidean space. One often needs to work with specific objective function(s) and even consider special initalization (e.g., [R4]) in order to get accurate rates; note high accuracy bound is needed as we are investigating whether there is acceleration in this paper. We agree that for convex problems, such as studied in the nice paper `Accelerated gradient methods for geodesically convex optimization: Tractable algorithms and convergence analysis\" by Jungbin Kim and Insoon Yang 2022`, it is possible to get global result (which is remarkable), but the setup considered in this paper is very different, as we consider accelerated optimization of general **non**convex functions in **curved** space. We are not aware of any result that can give global rate in this case.", "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:
**General rebuttal to all**

> **Q1**: More experimental results

A1: We perform more numerical experiments in the rebuttal PDF supplement. 
- We add Riemannian GD and Riemannian NAG-SC [R1] into comparison (Fig. 1 in the attached pdf). Of course, our proposed method converges faster than Riemannian GD which has no momentum nor acceleration. But we also see even faster convergence than Riemannian NAG-SC, which should already have acceleration (however with higher computational cost per step), possibly because our method is specially designed for Lie groups.
- We apply (and compare) the newly proposed Lie NAG-SC method and the existing Lie-Heavy Ball method to a practical machine learning application, namely improving Transformer by requiring attention heads to be orthogonal so that attentions are not redundant [R2]. 


The training of this modified Transformer amounts to a Lie group optimization problem. We used Lie NAG-SC and Lie HB to train the orthogonal parameters and momentum SGD for the unconstraint parameters. We trained vanilla Vision Transformer from scratch on Cifar till a fixed amount of epochs, and observed improved performance in terms of validation error when Lie HB is replaced by the accelerated method Lie NAG-SC (Cifar 10: 9.46% $\to$ 9.89%, Cifar 100: 31.72% $\to$ 31.11%).

[R1] Kwangjun Ahn and Suvrit Sra. From nesterov’s estimate sequence to riemannian acceleration. In Conference on Learning Theory, pages 84–118. PMLR, 2020.

[R2] Lingkai Kong, Yuqing Wang, and Molei Tao. Momentum stiefel optimizer, with applications to suitably-orthogonal attention, and optimal transport. ICLR, 2023.

Meta-review: From the valid reviews, the reviewers reach a consensus that the paper contains interesting result and novel contribution to the community. The Author-Reviewer discussions were substantial, the authors should incorporate the important ones to the final version of the paper and supplementary. Below are some points (but not limited to) we would like to see
 - Since Lie group is quite restrict, the difficulties and motivation should be better presented. Motivating examples from machine learning related areas would be great. 
 - Only local acceleration guarantee, which is understandable due to the nature of the manifold. On the other hand, it seems that practically how to enter the local region is problematic or not clearly discussed in the paper: 1) the locality condition requires $g_*$ which is not realistic; 2) suppose we can solve the first problem via some estimation of $g_*$, how to enter this locally region. For a given problem without prior knowledge, it seems hard.
Decision: Accept (poster)