Lion Secretly Solves a Constrained Optimization: As Lyapunov Predicts
Authors: Lizhang Chen
Bo Liu
Kaizhao Liang
qiang liu
Venue: ICLR 2024 spotlight (2024)
Keywords: Lion
Optimization
Lyapunov Analysis
Primary area: optimization
TL;DR: This work shows that the lion optimizer is performing a constrained optimization, and the key design choices of lion is equivalent to performing a hamiltonian mirror descent.

Abstract: Lion (Evolved Sign Momentum), a new optimizer discovered through program search, has shown promising results in training large AI models. It achieves results comparable to AdamW but with greater memory efficiency. As what we can expect from the result of the random search, Lion blends a number of elements from existing algorithms, including signed momentum, decoupled weight decay,  Polayk and Nesterov momentum, but doesn't fit into any existing category of theoretically grounded optimizers. Thus, even though Lion appears to perform well as a general-purpose optimizer for a wide range of tasks, its theoretical basis remains uncertain. This absence of theoretical clarity limits opportunities to further enhance and expand Lion's efficacy. This work aims to demystify Lion. Using both continuous-time and discrete-time analysis, we demonstrate that Lion is a novel and theoretically grounded approach for minimizing a general loss function $f(x)$ while enforcing a bound constraint $||x||_\infty \leq 1/\lambda$. Lion achieves this through the incorporation of decoupled weight decay, where $\lambda$ represents the weight decay coefficient. Our analysis is facilitated by the development of a new Lyapunov function for the Lion updates. It applies to a wide range of Lion-$\phi$ algorithms, where the  $sign(\cdot)$ operator in Lion is replaced by the subgradient of a convex function $\phi$, leading to the solution of the general composite optimization problem $\min_x f(x) + \phi^*(x)$. Our findings provide valuable insights into the dynamics of Lion and pave the way for further enhancements and extensions of Lion-related algorithms.

LION SECRETLY SOLVES CONSTRAINED OPTIMIZA- TION, As LYAPUNOV PREDICTS
Lizhang Chen"
Bo Liu"
Kaizhao Liang*
Qiang Liu
The University of Texas at Austin {lzchen, bliu, kai zhaol, lqiang) @uteeas.eeeeeeeeeeee
ABSTRACT
Lion (Evolved Sign Momentum), a new optimizer discovered through program search, has shown promising results in training large Al models. It performs com- parably or favorably to AdamW but with greater memory efficiency. As we can expect from the results of random search program, Lion incorporates elements from several existing algorithms, including signed momentum, decoupled weight decay, Polak, and Nesterov momentum, but does not fit into any existing category theoretically grounded optimizers. Thus, even though Lion appears to perform well general-purpose optimizer for a wide range of tasks, its theoretical basis remains uncertain. This lack of theoretical clarity limits opportunities to further enhance and expand Lion's 's efficacy.
This work aims demystify Lion. Based on both continuous-tine and discrete- time analysis, demonstrate that Lion is theoretically novel and principled approach for minimizing a general loss function f(x) while enforcing a bound constraint || S 1/X. Lion achieves this through the incorporation of decou- pled weight decay, where À represents the weight decay coefficient. Our analysis is made possible by the development of new Lyapunov function for the Lion updates. It applies to a broader family of Lion-K algorithms, where the sign(-) operator in Lion is replaced by the subgradient of a convex function K., leading the solution of a general composite optimization problem of min, fxx + K (z). Our findings provide valuable insights into the dynamics of Lion and pave the way for further improvements and extensions of Lion-related algorithms.
INTRODUCTION
Optimization serves as the cornerstone in training contemporary Al models. Given the immense computational demands associated with training large Al models, the design of an effective opti- mizer emerges as a paramount endeavor.
Traditionally, efficient optimizers are devised by machine learning experts based on theoretical in- sights [4, 15, 20, 11]. Adam [14] and its variant AdamW [20] remain the most widely employed methods in deep learning. Recently, however, new optimization named Lion (Evolved Sign Mo- mentum) [7] was discovered by an evolutionary search algorithm [32] applied to a symbolically represented program space [3]. Lion has been shown achieve at least comparable performance to AdamW on a wide range of tasks while reducing memory cost and training time [7].
However, the outcome of stochastic search algorithm, Lion does not have priori theoretical guarantee by design. It is still uncertain whether Lion can be regarded as a reliable and legitimate ceneral-purpose purpose optimization algorithm, despite the reported positive results a large, yet finite, set tasks [7]. The lack theoretical understanding also significantly restricts the potential for improving and extending Lion obtain better new optimizers.
general-
In this work, we demonstrate that Lion, along with broader family of Lion-K. algorithms, can be established as theoretically novel and intriguing approach for solving optimization problems with convex regularization or constraints. This is surprising because Lion was discovered in search
"Equal Contribution

---

space that includes arbitrary symbolic operations and was not designed with any theoretical guar- antees. This discovery opens up promising opportunities for developing improved optimizers by leveraging the existing success of Lion.
Lion: Evolved Sign Momentum
The update rule of Lion for minimizing a loss f(x) on Id M 8,m, - (1 - 52) (zx)
Lion:
(I)
F++1 = + (siin(B))m (1 31)V - Axx))
where my Rd is the momentum, e 0 the learning rate, $1, 32 E [0, [) are two momentum related coefficients, and X 2 O is weight decay coefficient. A default value of ß 0.9 and B2 = 0.99 was suggested in Chen et [7]. with which the Lion update rule can be written directly as
Tt-1 + e1) sign ((10+ 1)g. + 0.999; + 0.992 9--2 +... ... 0.99* -r-k + +...,,
where 9: = Vzzz). Here the update of z combines a weight decay term with coefficient (1 cA), and the sign of a weighted average of the trajectory gradients. Notably, the weight of the current gradient 9: is increased by (32 31) 82),8 ~ 10 times compared with typical exponential moving average of gradients as used in the classical Polyak momentum [30].
One can think of Lion as made by "splicing" the elements of many existing algorithms in Lion, which is exactly what an efficient search program can do when given a proper search space [29. 3. The update of the momentum m, is common to the Polyak momentum-ban based algorithms and yields the exponential moving average part of the update. What sets it apart is the unique update of xt, which uses the combination of three key elements:
i) [Sign Reshaper] The use of the sign(-) function for update, similar to signed gradient descent and signed momentum [5, 8], can be viewed of the coordinate-we
extreme way of normalizing the magnitude updates. It is closed related to normalized gradient [19, 25] and adaptive gradient methods such as Adam [14] and RMSprop [36]. Note that Adam can be viewed as signed momentum with an adaptive variance based step size [2], which might be the key factor explaining the gap between Adam and SGD [18].
ii) |Gradient Enhancement] When using 32 > B,, the importance of the current gradient is increased compared to the exponential moving average in standard Polyak momentum update. It can be shown that Polyak momentum with this gradient enhancement results in Nesterov momentum, and leads to the well-known acceleration phenomenon [e.g.. 35).
iii) [Decoupled Weight Decay] The weight decay term Ar outside of the gradient and sign(-). Such idea of the decoupled weight decay what make AdamW [21] significantly outperform the vanilla Adam in training large Al models.
As demonstrated by the empirical findings of Chen et al. [7] and subsequent research, the combi- nation of these elements has been shown to make Lion perform well on a wide range of problems, including image classification, language models, and diffusion models [7].
However, it remains unclear whether the combination of these elements yield theoretically valid and convergent general-purpose optimizer. Furthermore, the use of decoupled weight decay adds to the uncertainty regarding what optimization problem Lion aims to solve: due to its interaction with other parts of the algorithm, decoupled weight decay is always not equivalent to simply introducing la regularization [20].
"Lion King Meets Mr. Lyapunov" We propose and analyze a general family of Lion-K algo- rithms, in which we replace the sign(-) function in Lion with a subgradient VKC of general convex function KC: Rd + R:
M++1 = 32m, (1- (2)-,,)ve (2 fx
Lion-KC
(2)
1z+1 w. < <VVKC3mmm (1 Azx).
Lion recovered when K(x)) = ||ا|| and VK(()) sign(z). Taking the continuous time limit of (2), we obtain the following ordinary differential equation (ODE):
m = - (xx) yy
Lion-KC (ODE):
(3)
f VK(mm c(aVf + ymi)) - Ants
2

---

Polyak Momentum [30]
Nesterov Momentum [27]
K(x) = -
Signed Momentum [5]
K(xx) = |
Hamiltonian Descent [22]
6 ==
Hamiltonian Descent for Composite Objectives [22]
6 = ==0,>>0
Dual Space Preconditioning [233] Mirror Descent [26]
E7 = 1,
Signed Gradient Descent [5]
K(x) = |
1,
Accelerated Mirror Descent [16]
7 = 0, 0, 0
Frank-Wolfe [10]
E7 = 1,
Table I:
Lion-K includes large family algorithms as special cases. Section 3.1
Eq. (2) is the Fuler discretization of Eq. (3) with step size in the case of a 7, with β1 and 82 = - ey. Lion-IC includes a broad set of algorithms as special cases, as shown in Table
87,
To avoid the complexities associated with regularity conditions, ously differentiable when discussing the ODE. But parallel results hold for the time discrete algo- rithm (2) for general non-differentiable convex functions K.
assume that K. is continu-
The crest of this work is to show that, when e7 < 1, Lion-K ODE solves the following optimization:
min F(x) == + x (Ax), BER
(4)
where (x)()) = sup_(x" ( K(=)) is the conjugate function of K.. Because we may have KC (x)(x) too for some x, solving (4) requires to enforce a constraint of Az domK', where dom = (o: (x) < +oo} is the effective domain of KC* In the case of Lion, we have K(x)) = ||>|| and
hence 10 (x) = 8 6[[==] I 1). where the co-indicator function with ö(True) = 0, 6(False)
+oo. Hence, Lion solves the following
optimization problem:
min f(x) s.t.
||
1/2,
(5)
rERd
where the bound 1/A is solely decided by the weight decay coefficient X.
Optimisation Tralctooyy
||
Convergence loss Thy
Ost. leach
(ionet,
11
10 600
00 600
Figure 1: (a)-(c) Trajectories Lion on function f(x) (2) L.5) + 42. with ((a)-())) The boxes in a) represent the constraint set : blue box for || < 1/A with À = 0.5, green box is for À = 1.5. (d) À vs. the converged loss We can see that the converged loss starts to increase only when À excel threshold (A 0.6) to excluded the unconstrained minimum from the constrained set.
Iteration
50th Iteration
100th Iteration
150th Iteration
200th Iteration
250th Iteration
Prequenc..
Param
Param
Param
Param
Param
Param
Figure 2: Histograms of the network parameters of ResNet- 18 on CIFAR-10 10 trained by Lion with À = 10. The constraint of || S 1/A (indicated by the red vertical lines) satisfied within only ~000 steps.
3

---

(a)
(b)
(c)
(d)
Iteration
params
params
params
params
Figure 3: Evolution histogram parameter weights trained by Lion on ResNet-18 on CIFAR-I0 [13, 17]. with different and initialization methods. Frequency of network parameters in ResNet on the CIFAR-10 dataset across iterations. (a): Kaiming uniform initialization [12] and À = 20. (b): Kaiming normal ini-
tialization [12] and À 20. (c): Kaiming uniform initialization [12] and À 0. (d): Kaiming normal
initialization [12] and À The weights are quickly confined into the bound [-0.05, 0.05] with À 20, while keep growing with zero weight decay (A 0).
Our proof shows that the Lion-K dynamics consists of two phases: 1) [Phase 1] When d & domX." it exponentially decays the distance from Az, to the set domI.":
dist(Az; domK(*) I exp( A(t - =)) dist(Ax,, domX"") vs S t.
Hence, Ar converges to dom/ rapidly and stays within domK' once it arrived.
2) [Phase 2] After λx enters domK", the dynamics minimizes the finite valued objective F(x).
This is proved by showing that the Lion-K dynamics minimizes the following Lyapunov function:
H(x, m) = af(x)) (Ax) + 1 εr
1- (X* (Xx) + K(m) Am xx).
(6)
We show that, whenever H (Ie, m²) is finite, it is decreased monotonically (i.e., de Hx, me) along trajectories of (3) until a local minimum of point of (Ix m) is reached.
()
Furthermore, have F(x) min.. H (x, m), and hence minimizing [2, m) is equivalent to minimizing Fxx); this is because the minimum the last term in (6) equals zero, min KC* ('*()z) + K(m) Am3 z 0, for any fixed æ. by Fenchel- Young inequality.
The discovery this Lyapunov function a new and non-trivial mathematical result. But intuitively, easily the connection of (3) and (4) by comparing their fixed points. Assume IC and K are differentiable, then a fix point of (3) must implies a stationary point of (4):
a fV + ym = 0, VK(m)) = Ax
v f(.)) + VVC (Az,) = 0.
fixed point of (3)
stationary point (4)
where we used VXC(VKC(())) = x, and Va (HI))) (Ax)
= (
Why Should Lion Decay Weight? From the analysis above, the role of weight decay in Lion is two-fold:
1) It alternates the solution if is large and the constraint || S 1/A is strong enough to exclude the unconstrained minimum zine of (xx). This may improve the generalization and stability of the solution while sacrificing the training loss.
2) If À is sufficiently small to include the unconstrained minimum zine in the constrained set, it does not alter the final solution. In this case, the main role of weight decay is to speed up the convergence because Phase 1 brings the solution into the constrained set with linear rate. Hence, the ideal choice of À is À = 1/ ll
In Figure 4 we plot Lion's performance with different X. The right plot confirms that larger À results in faster convergence but might sacrifice the performance. The left plot shows that there exists an optimal À (=0.56), beyond which the training loss starts to increase.

---

Converged loss on CIFAR-10 -00
Loss curve on CIFAR-10
loss
A=
1008
1
1315
50'
lo.s=0..00
A=2.0
L324
3=5.5
1055
lo55
1339
1840
200
2000
epoch
Figure 4: Analysis of weight decay CIFAR-10 using Lion. The converged Loss weight decay in Lion. We can that the loss starts to increase only when excel a threshold, which is expected from the constraincd optimization view. b) The loss curves vs. epochs with different weight decays. Larger weight decay À yiclds faster convergence (due to stronger Phase I), but may yield larger final loss when it is too large.
Line ID
(((x)
VK(x))
min, f(x) + (1r)
|
sign(x)
min f(x) s.t. ||]
|sr||p
sign(=) <ipn(=]==1""1
min f(x)) ||=||, S
[=]|2
E (ax -,
sign(x:) > e)
min f(x)) + [|al] s.t. ||=r|| S
Exgrou [a:a]
sign(>)][(ar
(
min f(z) a.t. ||l|| am ||=||
E; hu.era(x.)
clip(æ, c,c\/e
min f(x) $ || s.l. ||
Table 2: Examples of K. and VK, and the optimization problems they solved (we set x 1 for simplicity). assume æ = ( =a]] E I2d and |x<)>] 2 | ... is monotonic sorting of elements of x, and your is an integer in . d}. The Huber loss huber.(x.) I([ 2 e)( {) + I([=,] < e)
e 0. See Appendix A for more examples.
Going Beyond Lion Different yield optimization with different convex constraints and/or reg- ularizations. For example, using the l, norm K(xx) | yields constraint the dual norm |æ=||, < 1/A where 1/p++1//
(Table 2, Line 2); zeroing out the coordinates with small magni- tude corresponds introducing é regularization (Line )) E constraint (O), which useful for sparse learning; replacing VK((x) sign(x) with a continuous function would introduce an extra regularization term on the loss (e.g.. )). This work will focus on building the basic theoretical framework, and leave the vast opportunities of practical applications as future directions.
The rest of the paper is organized as follows. Section 2 introduces preliminaries on convex functions. Section analyzes the continuous-time Lion-K dynamics and discusses connections with existing algorithms. Section 4 presents the discrete-ting -ieee analysis. Section presents experiments that study and verify the behavior of using different K's.
Outline
PRELIMINARIES ON CONVEX FUNCTIONS
Assume K:: Rd + IR is convex. A vector u E Rd is said to be subgradient of IC at denoted as aK(x),
K(y) - K(xx
z). Yy Yyek Ed
With an abuse of notation, VC((z) to denote subgradients of K. that is, VK(x) E ŌK(x).
When IC is differentiable at x, there is an unique subgradient VC((z) which coincides with the regular derivative.
The conjugate function K of IC is defined as
K²(x)
sup (a T K(2)).
5

---

Hence, by definition, we have the following Fenchel- Young inequality:
K(xx)= + (3) 2 x y, Vr,y.
The conjugate function KC* take values in the extended real set R R {= and KC* is always closed and convex, even when IC is not. Recall that a function f is said to be closed if for each b R. its sublevel sets {æ: f(x) b3 is a closed set.
IC is closed and convex, we have 10 = K. and
(8) When K. and KC* are differentiable, (8) suggests that VA and VK* is a pair of inverse maps: VXC(VX((())) H. Combining (7) and (8), we get minm K(m)) (x) x xmm 0, which
E OK(())
-
x x a (v)
K(()) + +C)
= xTT
yields F(x) minm (z. We refer to Rockafellar [33] for systematic introduction to convex functions.
A key property of any subgradient VKC and VK* is that they are monotonic maps, which plays crucial rule in our results.
Lemma 2.1. Assume K,, KC is a closed convex conjugate pair and VK, VK* are their subgradients, we have
- [VK(=)-V<())]
v) 20
(VK())) (V2
VK*
See Appendix B.1 for the proof. These two inequalities are crucial because they allow us identify vectors that have non-negative inner product with given direction to achieve monotonic descent in optimization.
Example 2.2. In the case of Lion, we take K(x) = ||=||, with VK((x) = (ag and
if |/ I
So if il - 1
(v) = 1
+00
if lllllo > 1
(V)*
too
Yi
Vi -1
One can verify that the inequalities in (9) hold (even though the values on the left side can be +00)). The Lyapunov function in (6) becomes
[(()) + I#ex (l1mll, - dx m)
f|| I 1
H m)
400
||| 1.
MAIN RESULT: CONTINUOUS-TIME
We study the cuntinuous-time Lion-K dynamics (3), and discuss its connection to existing algo- rithms listed in Table 1. We defer the detailed proofs to Appendix B.7, but outline a novel implicit Hamiltonian + descent decomposition that underpins the construction of the Lyapunov function H ( mz.
Theorem 3.1. Let (x,, (x),m) continuously differentiable trajectory of the Lion-K ODE (3), where K. is differentiable convex with conjugate K"* Assume a, X, >> O and eγ < 1.
1) [Phase 1] Define dist(Az, d inf -|2- | w.r.t any norm |||]|. We have dist(Xrr, domK')) I exp(X(s t)) dist domK'), YO S St. Hence, λz converges linearly set domK and stays within domK once it enters it.
2) [Phase 2] When Hxx, m) in (6) is finite and continuously differentiable, it is decreased monoton- ically along the trajectory:
d di
X * A (2,, m.) + 1- 1- A2(me, m.) 2 0, 1
H me) A m2)
1 εA
where we define my = m4 - f(aV)(rr) + 7)))), and
A m4) = (m, - VK VKC* (Axx)) (VK(m)) )xx) 2 0,
(mi m.) (VK((m))) -VK(m.)) 2 0. 1
(10)
A A (m))

---

3) [Stationarity] Assume V is strictly monotonic. All the accumulation points of (a),m4) as
t - +o0 are stationary points of the objective function F(x) = af(x)) + 3 (Az), and satisfy A E domK"*
A (ar, m²) can be viewed as an indication of the stationarity the system. If H (ro, mo) is finite and Hg = inf., (x, m.) > -0, we have T Jo (X mz)dt < H(za.mo)
T _ 0 when T + +o0.
Proof Sketch. See Appendix B.7 for the full proof. The original discovery of the Lyapunov func- tion was made possible by starting from the incqualities in (10) guaranteed by Lemma 2.1, and working backwards with some guesswork. The following is a simplified proof that highlights the essential mathematical structure that makes (ar, (2) Lyapunov. Define
in = (1, = [V)((x) - -mm m m
④ = = m) = VK(m) - Ax,
and related
(z( m vk=(
(m VV((m) V.((m).
The Ve and Vm have two critical properties:
1) By Lemma 2.1, Vy and V. have non-negative inner products with V2, Vn. respectively:
V2(a,, m)) Vi,(1, m) 2 0,
Vm m)) (I, m) 2 0, Væ, m.
2) By Lemma B.5 in Appendix B.7, the gradients of H can be decomposed as follows:
(x, m) = - Vn V m H (z. m) = =n Vn Y+A
(Implicit Hamiltonian + Descent)
(11)
where 7 = 1+s2 and r// = 1+s2 We call (11) an "implicit" Hamiltonian descent decomposition, in connection with the Hamiltonian + descent decomposition we introduce sequel.
Then we have,
d H (o) V. Vm (-n'Vo -VV)) + (-nVm Vm dt
= - V. Vv + 17 vm S.
The key here is that the cross term V/ Vm is canceled, leaving only the negative terms. The convergence property uses Lasselle's invariance principle; see Appendix B.7 for details.
Hamiltonian Descent Decomposition The decomposition structure (11) is key characteriza- tion of Lion-K ODE, An interesting remark is that (1,, m) is also Lyapunov we have the follow- ing Hamiltonian + descent structure [22, 28] in which the roles of [V H, V, H] and [Ve, Vm in (11) are switched:
V3 = Hi V m mH
(Hamiltonian + Descent)
(12)
Vn, = - - V,,
where Hz, Hm are two vector fields satisfying H. (V+H) 2 0 and AT, (Vm H) 2 0, then d H(z,, VV N V.H (- V H) + H T-
dt
= (V. + (V,
The structure in (12) can be intuitively viewed as a generalized damped Hamiltonian system with ( m) as the total energy. where H 1-7--H,, Am, serves a damping force that monotonically de- creases the total energy, and V-Vm, V HH is the Hamiltonian vector field which preserves the energy but introduces an inertia-like effect into system. One can easily verify (12) on the classi- cal Polayk's momentum. The more general idea is explored in the Hamiltonian descent method of [22, 28], which considers systems structure (12) for the separatiable Hamiltonian form H m) = f(x) + X(()) with A. = In contrast, (11) do not seem to have clear physical interpretation, yet provides handy tool for understanding the general Lion-KC dynamics. Some special cases of Lion-KC, such as when = 0 or = O, can also be alternatively viewed from the Hamiltonian descent structure shown in Section 3.1.
7

---

3.1 CONNECTION WITH EXISTING ALGORITHMS
What makes Lion-K unique is the combination of the gradient enhancement > 0), the decoupled weight decay (A > 0), and the momentum damping (7 > 0), the use of reshaper function V VAC(.).
We discuss the effects of these elements in connection to existing algorithms as shown in Table 1.
Lion-K. Without Weight Decay When À = 0 and VCC = 0, we have lima-so X KC (Ax) = VKC(O) x = 0, and the Lyapunov function can be defined as
H(x, = af(x)) (1 (1-=)))(m).
for which we have
H (Z m2) = VVK(m))m (1- (m: m2) (VK((m)) - vK((m)) 2 0.
dt
In this case, the algorithm solves min, f(z), without the regularization term K KC* (Az).
Interestingly, in this case (A 0) and ey O, there exists second Lyapunov function:
(2, m) = af(x) + 1 1- K((1 - =7)mm,
(13)
with which the Lion-K ODE (A 0) can be decomposed in the form of (12), sum of Hamil- tonian vector field and a descent direction:
(x)...) V H (21, (m)
VK(m))) VIC(m,
rite
my
Hamiltonian
Descent
where m (1 my and hence m. m, = vVV)) If m 0 is minimum of K(mm), one show that the second component above is descent direction of H (xx, (x) in (13), with
1 (m m.) (VX((m)) VK((m)) 2 0,
( m.) >VVC(M))TT m, +
dt
See Appendix B.6 for details.
Lion-K. Without Momentum Damping When = 0, we have
H(x, af(x) 1 1 (x* K(() Ax T mm),
Because min,,.CCC (x) + K((m) Xx m) = 0, the algorithm also corresponds to solving min, f(x)
without regularization K (Xx).
is interesting to see that the weight decay and momentum damping play a somewhat symmetric
role, because turning off either one of it turns off the regularization term IC* (Az). In particular, if
K(x)) | 1/2 /2, the Lion-K ODE can be rewritten into a second-order ODE:
H. + (A + 7)4 + ea ea 2
V f(x)) + 7dx, + (Vx)) = 0,
(14)
in which the role of À symmetric. Equation (21) coincides the high-resolution ODE in [35] for minimizing F(x)) a (xx 7 ||=|| 2 /2, which is high resolution continuous time limit of Nesterov momentum. The hessian-basee damping term fx+(())) plays key role for acceleration phenomenon [see e.g., 35, 1]. When we turn off the gradient enhancement (E = 0), then we get ODE for Ployak momentum.
Interestingly, we set = 7 = 0, but e > 0, ODE (21) still serve to minimize f(x), due to the Hessian damping term.
8

---

Lion-K without Gradient Enhancement When have (2, m) - af(()) + k (Ax) + (Ax) + K(m) Am T xx),
and (m,m, m) = 0,
( m)) (A (A+ m) = (A+ 7m ( - Xx).
In this case, minimizing (ax m) still yields the minimization F(x). Hence, the choice of e does not alter the objective function.
Moreover, with & O, one can conveniently decompose the velocity field in the form of (12), sum of a Hamiltonian vector field and mirror descent direction:
V H mz)
m
a (xts mi)
((r () VX (Aas))
Hamiltonian
Descent
This system can shown to equivalent to the Hamiltonian descent system for composite objects of [28]. Further, if À = 0, it reduces to the conformal Hamiltonian system [e.g.. 22, 24).
Mirror Descent and Frank-Wolfe If Ey = 1, Lion-K reduces to
i VK(=caV((x)) - Are
which can be shown be equivalent to the Frank Frank-Wolfe algorithm for minimizing F(x) ax()) (A=().).
When ey 1, and x 0 with vK((x) iff Lion-K reduces to VV((=eaf(xi)) which is dual space conditioning [23]. or variant of mirror descent for min, f (I)) See Ap- pendix B.4 for more discussion.
Accelerated Mirror Descent The accelerated mirror descent of Krichene et al. [16] is
द X₂ (VK((m))))) zz),
m, a4 ff()))
which is shown to exhibit an acceleration behavior for minimizing a convex f (without the XC* regularization) when a; t/rr and A = r/t and > This can viewed Lion-K ODE with 0,5 0 and but special time-dependent coefficient.
4 DISCRETE TIME ANALYSIS
We now present a result on the discrete-time Lion-KC parallel to the continous time results Theo- rem 3.1, but work for non-differentiable convex functions K. We analyze slight reform of (2):
m++1 = 82m, - (1 f
m B1 m. (1 (xx)
(15)
Tt+1 = 2t + E( <(VK((m++1) - Am++1),
in which we use implicit scheme for the z.-update, replacing Ar, with Ar It equivalent to explicit scheme in (2) with e replaced by T+ex
Theorem 4.1. Assume f: Rd R is L-soooth, and K: Rd - R is closed and convex, and VC is a subgradient of K. Assume 31, 32 E (0, 1), and f3 > Br, and c, X > O.
1) For any two neg-negative integers t, we have
1
4-t
dist(Xa;, dom/
(ist(Ax,,domK3
Vs 1
1
2) Define the following Lyapunov function:
31
H(z, m) f(x) + A ((x))x + e\(1 - B1) (1 32)
(1 (Ax) + K(m) -x"" m).
9

---

and
A (VK(m++1) - X1e+1) " - VV (Arz+1)) 2 0,
A (VK(m)+1) VK(m++1)) (mz+1 mz+1) 0,
where VK is subgradient of K. Then we have
Lea M(241, (1))) S -cd, |VK((m++1) 20
where A, = a + b, with
B1
3, - -32)
a EX(1 B1) Hence, a telescoping sum yields
+120, b= eX(32 31)(eX(1 B1) + (1-B2)) 2 0.
+ 31)
(1-B2)
H (f0, H(T,, mr)
Le BT, + 2
Σ 1=
A
T
cT
where By = E \V(()++) - X2++1llz 112.
The result above shows that + Et A. decays with an O e) rate, if Br finite upper bound. This reduces to the continuous-time result of 7 S A(x., m, O (+) when the step size e converges to zero
If IC is smooth, it is possible to improve the discrete-time rate to O ( with standard arguments based on the proof of Theorem 4. Hence, the impact of the non-differentiabiiity K contributes to the (e) term, which suggests that the algorithm converges upto accuracy. This is typical phenomenon in optimization with non- non-smooth objectives (like sub-gradient descent) or non-smooth update (like signed GD). Because in practice the step size is small decaying, the Oc) term may not have a substantial impact for practical performance.
EXPERIMENTS ON DIFFERENT I.
This section provides a preliminary investigation on the behaviors of Lion-KC with different K. We experiment with the Kss listed in Table 2 on the toy example shown in Figure to confirm the behavior follows exactly as what the theory predicts. Then we focus on the Lion-(, optimizer with general [1,2] since it is the most straightforward extension of the original Lion (with 1).
5.1 LION-K's ON THE TOY EXAMPLE
In the following, we plot the behavior of different Lion-K's on the toy example shown Figure 1. For each K, we draw the optimization trajectory using the corresponding optimizer, the loss f(xx) and the corresponding constraint (e.g., the norm of x) v.s. iteration. The results are shown in Figure 5.
Observation From Figure 5, one can observe that for K(x)= = |>> l2. the constraint is a circle. For K(x)) E, max([z;1 0), additional & regularization is introduced in addition to the loo constraint, which encourages sparse solutions. When K(xx) = Eiggone (A it enforces an & constraint (rather than regularization) in addition to the Loo constraint. The K((x) = E, huber, introduces l regularization effect in addition loo constraint. All optimization trajectories closely match what the theory predicts.
5.2 LION-L, FOR IMAGENET AND LANGUAGE MODELING
Lion-l, corresponds to K(xx) ||-||| p 2 and amounts to solving min, f(x) s.t. ||0|| S 1/X where 1/p 1/q 1. In Figure 6, we plot how the parameter norms (e.g., || llle when p= = 1 and I|- ll2 when p 2) change over training iterations. In Figure 7, compare the performance of using Lion-e, with different p. on ImageNet [34] and Language Modeling tasks, using ResNet-50, Vision Transformer (ViT) [9], and the GPT-2 model [31].
10

---

Optimization Trajectory
1.0
Ope
K(a) ||||a
Feas repion
region
min f(x) s.f. |x]|a
Lans, 1.5
100 Iteration
Iteratio
Optimization Trajectary
+ (ells
||x||=
clined clin
(C() = Σ max([a:] c. f(x) +e [a]la 8.1. |/01
Pelsiie
Feeniire replon
Liat A
Iteration
Iteratioo
Optimization Trajectory
||x||-
Oct efit
Uandi Uo
K(w)= Σ locol
min ((r] s.f |arlla 1 e (allo 1
Irlls wi
Xg
iteration
iteration
Optimization Trajectory
Abd
|
Opti el +
K((x) Σ (x.)er,(z)) min ((x)((x)))))))))( g1ulBB sd. 100
Opt efft
Feae region
rogion
Liand,
Iteration
Iteration
The behavior of Lion-K with different Kss from Table The blue trajectory always reaches the optimum as the optimum is included in the constraint. The green trajectory converges the boundary of the constraint.
Figure 5:
Experiment Setting For the ImageNet training, follow the standard PyTorch ImageNet train- ing code.' We train the ResNet-50 and the ViT-B/16 model using batch size 1024 and cosine learning rate scheduler. For GPT-2 training, we follow the HuggingFace code?, train on OpenWebTexx using cosine learning rate scheduler.
Observation From Figure we observe that even on deep neural networks like VIT [9], ResNet [13], and GPT-2 [31], the behavior of the Lion-K optimizers strictly follow what the theory predicts. From Figure 7, we observe that Lion-(; 1 (the original Lion optimizer) performs better than Lion with other p on ImageNet when ViT is used, and language modeling with the GPT-2 model. The plot indicates trend that smaller E [0, 1] results in better training efficiency. However, the trend is reversed when ResNet-50 [13] is used ImageNet. Therefore, this indicates that the choice of IC might depend on the underlying neural architecture. Based on the empirical observation, we conjecture that Lion-&, performs well among all Lion-f, on the transformer architecture, which is consistent with the fact that Lion-L; is found by an evolutionary search using the transformer architecture [6].
DISCUSSION
As demonstrated in the analysis of the Lyapunov function in Theorem 3.1, the Lion-K dynamics exhibit a distinct nature when compared to typical momentum bassed methods like Polyak, Nes- terov momentum, and Hamiltonian descent, all of which can be conveniently understood as certain generalized dissipative Hamiltonian systems. While the Lyapunov function provides a powerful
Phttps::/huggiingffacs 2 hhttps://huggingge wttee.co/aaatttteeeee htt.aaateees/yy1lmmmmm/////eeeee

---

K(tr) [irla
K(a) ||tl
Vi1-160
Resiic 50
VIT-1688
GPPT-
250
200p
Figure 6: Constraint verification for Lion-& and Lion-&2 ImageNet and Language Modeling tasks, using the ResNet-50, ViT-B/16 and the GPT-2 architectures.
ImageNet ResNet-50
ImageNet ViT-16B
Language Modeling
GPT-2
4.5
9.0
Lion-h
3.5
Loss
400
Train Loss
Lion-f1a
3.0
Lion-f1.
3.5
4.-
Train
4.5
Lion-f1,
Lion f1.6
3.0
4.0
Lion-fz
1.5k
26
2.5k
16
24
8c
12k
124
Steps
Steps
Steps
Figure 7: Performance of Lion-lp with different p. ImageNet [34] (left figures) and Language Modeling (right), using ResNet-50 [13] (left), ViT [9] (middle), and GPT-2 [31] (right).
characterization of the dynamical behavior, intuitive understanding of the Lion-K dynamics mains obscured because we lack a "physical intuition" or constructive derivation like the standard optimization algorithms. This invites more studies in studies and understandings in future works.
The connection between Lion-KC C and Nesterov momentum and accelerated mirror descent suggests the possibility of acceleration phenomena in variants of Lion-K,, which opens exciting avenue for future exploration and research. It might be possible to find novel accelerated algorithms based on the Lion-KC family.
It is surprising and compelling that an algorithm found by random search program has such a rich and intriguing theoretical basis. The reasons for this remain elusive, whether it is coincidence or due to some inherent necessity. For instance, the design of the search space in Chen et al. [6] may in some way entails high likelihood of discovering theoretically sound algorithms with random search. Understanding the underlying logic here could lead to future advancements in automatic machine-based algorithm discovery.
Regarding applications, since Lion-K offers broader family than Lion, it is possible to find within the Lion-K. family new algorithms that outperform Lion in various tasks and metrics. Addition- ally. by using different values of IC, Lion-K can be utilized to address different types of constraint optimization problems.
7 ACKNOWLEDGEMENT
The research is conducted in Statistics & Al group at UT Austin, which receives supports in part from NSF CAREER LEGER1846421,, SenSE2037267, Office of Navy Research, and NSF AI Institute for Foundations of Machine Learning (IFML).
REFERENCES
[1] Hedy Attouch, Juan Peypouquet, and Patrick Redont. Fast convex optimization via inertial dynamics with hessian driven damping. Journal of Differential Equations, 261(10), January 2016. doi: 10. id.101/......221.0888.
12

---

[2] Lukas Balles and Philipp Hennig. Dissecting adam: The sign, magnitude and variance of stochastic gradients. International Conference on Machine Learning, pages 404-413. PMLR, 2018.
[3] Irwan Bello, Barret Zoph, Vijay Vasudevan, and Quoc Le. Neural optimizer search with reinforcement learning. In International Conference on Machine Learning, pages 459-468. PMLR, 2017.
[4] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandkumar. signSGD: Compressed Optimisation for Non-Convex Problems, August 2018. URL http: //arxiv.org//aaee 110111101100 04434. arXiv:1802.04434 [cs, math].
[5] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference Machine Learning, pages 560-569, PMLR, 2018.
[6] Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Kaiyuan Wang, Yao Liu, Hieu Pham, Xuanyi Dong, Thang Luong, Cho-Jui Hsieh, Yifeng Lu, and Quoc V. Le. Symbolic Discovery of Optimization Algorithms, 2023. arXiv:2302.0667. [cs].
[7] Xiangning Chen, Chen Liang. Da Huang, Esteban Real, Kaiyuan Wang, Yao Liu, Hieu Pham, Xuanyi Dong. Thang Luong, Cho-Jui Hsieh, al. Symbolic discovery of optimization algo- rithms. arXiv preprint arXiv:2332.00667.. 2023.
[8] Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Ro- bustness to unbounded smoothness of generalized signsgd. arXiv preprint arXiv:2208.1111 2022.
[9] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.
2020.
[10] M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval Reseurch Logistics Quarterly, 311-))955-100, 1956. doi: 10. 1002/nav.88000301999
[11] Elad Hazan and Sham Kakade. Revisiting the Polyak step size, August 2022. URL http: 1.XXvv1905.00311 [math].
[12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Sur- passing human-level performance on imagenet classification. In Proceedings of the IEEE in- ternational conference on computer vision, pages 1026-1034, 2015.
[13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recogni- tion, pages 770-778, 2016.
[14] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.644, 2014.
[15] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
[16] Walid Krichene, Alexandre Bayen, and Peter L Bartlett. Accelerated mirror descent in contin- uous and discrete time. Advances in neural information processing systems, 28, 2015.
[17] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[18] Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington, and Mark Schmidt. Noise not the main factor behind the gap between sgd and adam on transformers, but sign descent might be. arXiv preprint urXiv:2304.13966 2023.
[19] Kfrr Y Levy. The power of normalization: Faster evasion of saddle points. arXiv preprint 16Xiv:1611.044 2016.
13

---

[20] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101, 2017.
[21] Iyy Loshchilov and Frank Hutter. Decoupled weight decay regularization, 2019.
[22] Chris J Maddison, Daniel Paulin, Yee Whye Teh, Brendan O' O'Donoghue, and Arnaud Doucet. Hamiltonian descent methods. arXiv preprint arXiv:/809.0504: 2018.
[23] Chris J Maddison, Daniel Paulin, Yee Whye Teh, and Arnaud Doucet. Dual space precondi- tioning for gradient descent. SIAM Journal Optimization, 31(1):991-1016 2021.
[24] Robert McLachlan and Matthew Perlmutter. Conformal hamiltonian systems. Journal Ge- ometry and Physics, 3964)2776-300, 2001.
[25] Ryan Murray, Brian Swenson, and Soummya Kar. Revisiting normalized gradient descent: Fast evasion of saddle points. IEEE Transactions on Automatic Control, 64(11))4815 4824, 2019.
[26] Arkadij Semenovic Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency optimization. 1983.
[27] Yurii Evgen'evich evich Nesterov. A method for solving the convex programming problem with convergence rate (I/x² 2). In Dokl. akad. nauk Sssr, volume 269, pages 543-547, 1983.
[28] Brendan O'Donoghue and Chris J Maddison. Hamiltonian descent for composite objectives. Advances in Neural Information Processing Systems, 32, 2019.
[29] Daiyi Peng, Xuanyi Dong, Esteban Real, Mingxing Tan, Yifeng Lu, Gabriel Bender, Hanxiao Liu, Adam Kraft, Chen Liang, and Quoe Le. Pyglove: Symbolic programming for automated machine learning. Advances in Neural Information Processing Systems, 33:96-108. 2020.
[30] Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computational mathematics and mathematical physics, 4(5):1-17, 1964.
[31] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog. 1(8):9, 2019.
[32] Esteban Real, Chen Liang, David So, and Quoc Le. Automl-zero: Evolving machine learning algorithms from scratch. In International conference machine learning, pages 8007-8019. PMLR, 2020.
[33] R. T. Rockafellar. Convex Analysis, volume 11, Princeton University Press, 1997.
[34] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma. Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journaa of computer vision, 115:211-2555 2015.
[35] 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.
[36] Tijmen Tieleman, Geoffrey Hinton, al. Lecture 6.5-rmsprop: Divide the gradient by run- ning average of its recent magnitude. COURSERA: Neural networks for machine learning, (2:26-31,,00) 2012.
14

---

A
EXAMPLES OF IC
We provide a list of examples of IC and the corresponding VK and K It is useful to define the following indicator functions of set {z = 0}:
0
if
0
if 0
8(2)
I(2)
+o if 0.
if + 0.
Note that 8 the conjugate function f(z) = z, as 6(x) = sup, x T 2.
lp norm
1/7 for p 2 we can take When K(x) || E, |x //////
VK(x)= sign(x) |>|
|| p
and
(x) sup x Ta 11=111 sup |2| c- c=c S 1),
where q is the conjugate number of p. satisfying solving
1 p ++1 Hence, Lion-K with lp norm correspond
min ((x) s.l. ||-||, S 1/A.
Group bp norm Assume is partitioned into number of groups: [xcg 1e Consider the group Ep norm: K(xx) = Σt | llp. Then, we can take
vK(x)= sign( ) | |
|| lp
1=1
The conjugate function is
KC' (x) sup Σ
T Fg. 2g.
Σ 8(11rg, ll, S 11).
Hence, Lion-K with grouped Ep norm corresponds to solving min (xx s.l. ||= s 1/2, Vi.
Lower Truncated & Norm
Consider K(x)) = Ei max([a;| - e, 0) where e > 0. We can take VK(x) I([=] e)sign(zx)
(16)
which uses sign(x) as Lion, but zeros out the gradient on the elements with absolute values smaller than e, The conjugate is
10 (x) sup
(1,2, max(|z|; e, 0))
sup Σ
(z;2) -c) c;) s.. a 20, 0, c 02121-c
i=1
sup
[xi ee)+ -4
c20 i=1
8(1z:] $ 1) + e |xi
5 || < 1) + e ||-|||
Hence, Lion-K corresponds to solving
of ey |=ا||
s.t.
||0| $ 1/A.
(17)
Hence, truncating the small gradients in Lion induces an é penalty, which encourages the sparsity of the final solution.
15

---

Lower (Vector-wise) Truncated Ep Norm Consider K(x) max(1 e, 0). We have
sign ( las p-1
VK(()) = I[[|==11p e 2 0)
in which the gradient is zeroed out when | S The conjugate is
KC* (x) sup(# max(11=11p - e, 0))
sup(2 2- c) stt. c20, o, c 1|=11p- -e
sup
|| (e + e) -c
c20
= =[1x=1, 1) + e l|11||
Hence, Lion-K corresponds to solving
m + ey ||ا| s.t. ||~|| s 1/A.
Sorting Norm For [m,, [m.....,ddd.) ral. let |<<a>| |m() ... be the sorting of the elements by
absolute values. Define
Sorting norm:
K(x)) = Σ a |o
where C1 2 C2 ... 0 is descending non non-negative sequence. The sorting norm is convex
because it can be represented as the supreme of a set of convex functions, by the rearrangement inequality, as follows
K(xx) = max TET
Co(t) |m:],
where I denotes the set of permutations {1...., n). One subgradient of K. is VK(x)); Crank(i. Sign)()))
where rank(i, denotes the rank of [.s] in x.
(=) sup TT Σ ca |
sup
(P()) x 2(0) Σ 229
//by rearrangement inequality
=20
sup
(1000 ct) x E w/)
Met 2(1)
Σ
Wí. Wj 0
w20
121
121
sup w20
(1t0 ci) x Wi
/eet 2(3)
Σ
Wie w/ 2 0
524
Σ
6
S
(j)
JS
Hence, Lion-K corresponds to imposing a sequence of bounds on the cumsum of the sorted .::
min f(x)
| S C, where C, Σ Cj.
151
$55
An interesting special case is when c; = I(i S gout) for some integer jour E (l....... d], so that
K(x)= = Σ |ool.
VK(x) = I[[x] 2 Z(vore) (((re)))sgn(( )sign(x),
16

---

the updates of the elements whose absolute values smaller than the 2m**-th largest element. It is useful to compare this with (16) which applies the truncation based on fixed number e, rather than the percentile.
in which
The conjugate
(x) = E
8((6))) 1) + 6(11=11 S gou)
Then, Lion-K in this case corresponds to solving
min
f(z)
S | S 1/A,
which the percentile-based truncation effectively imposes a constraint on the & norm of x. It is different from (17) in which the & norm appears regularization term in the objective, rather than as a hard constraint.
Entropy Consider K(xx)= = -(t)=E= 1
a log (1 (exp(ar;) +
where a > 0. We have exp(az) + exp(-az) tanh(ar).
vK(x)= exp(ax) exp(- (xp(-az)
1= 1-2 with domain in ||]|| S 1. by integration, the Taking the inverse, we have (x) Za log conjugate function is hence,
1 (1 x;) log( xx) + 0(112011 1).
(x)
(I: 1) log(2; + 1) +
2a
2a
Lion-K correspond solving an entropy-regularriee optimization
min + X E(Ax)
s.t. || S 1/1,
where E(x)= = Di
1 (a. + 1) log + 1)n + Aal (1 - r;)) log(1 xz).
2a
Huber Loss
For 2 0, define the Huber loss:
K(xx) = (u;)ra((;) where Hubera = I[[20d 2 a) x |xs| + I((0d < a) x
2a x.
We have
F if (a if > b if <a
= Clipax, -a, a)aa/a
with
Clip(z, a, b) =
b
The conjugate
(C)()) 2 ||0|| + 8(11=)1 11),
1
1C (x)
max( sup J; - |zal, 1:|2a
sup 3i
2a
max (8(1zz) S 11) + +a(xs] 1), 2 fax?
5[[ma] 11 + 2 ax?
2 1011 + 5011=11>0 - 1).
17

---

Relativistic Consider K(x)) =Ei= V2 t then VK(x)
Vor+er and
(x) = sup
Σ T12; V o + e²
d
d/e
e
//Solution: x 1 x
276²
1 27
x
1=1
-ev 1 x² + 8(12zg s 1)
-ev 1 x² + 5(11=1100 S 1)).
related case
[xx)) = |x| - e ( /e 1),
with
VK(())
whose conjugate function is
K (x:) sup Σ Tiz |zi + +elog((=///++1))
Σ ar e/(11 (x:1) | e/(1 (x,1) llog(1/(1 (zxl))
//Solution: |x/ee/(1 [x])
-(( + loog(1 - (z) + 6(122110 < 1).
B PROOFS
B. CONVEX FUNCTION PRELIMINARIES
Lemma 2.1 we have
Assume K" is a closed convex conjugate pair and VK, VK are their subgradients,
(VK(x) - (x()) y) 0,
(VK(()- - v) Tx
(18)
Proof. 1) By definition of subgradient, we have
K(w)) K(x)) > VK(x) x)
K(x)) K(v)) 2 vK(2) (x y).
Summing them together yields (VK(x)) - VK(2)) T
(x y) 2.
2) Because (V) (v), we have
(VK((z)) - (C) VK) TVKK()) -)), y).
Because VK((x) @K(x). by the property of conjugate functions, we have x E (VK(()), and hence
(''()) - <><(((()))) 2 x TT vK(())).
Summing the two inequalities above yields
(VK(z) w) T (v) x) < +E)
0.
18

---

B.2 CONNECTION WITH NESTEROV MOMENTUM
Lemma B.I. The Lion-K ODE is
dt = -(aVi- +ym+)) Are
Th -aVS(2)) 7m4
is equivalent to if and are second order differentiable. In particular, if K(x)) |>>1|/ 22. we have
V²K + X + X + f(z)) + (+x Xxa) + aVf(x)) =0,
(19)
Ét + (A + 7) + f(ri)t + ydz, + aVf(x)) = O.
(20)
This ODE minimizes F(z) ff(x)) > 11122///2
Remark We have the following observations from (21):
1) The role of the weight decay and momentum damping coefficient y symmetric in (21).
2) When either the weight decay or momentum damping is turned off, i.e., 7 = 0, the &g regular- ization in Fxx) is turned off, and we have
f + (A + ,) + ca f(r)) + vV(z)) = 0,
(21)
which coincides with the high- righ-resolutton ODE [35] that serves continuous- time modeling of Nesterov momentum for minimizing (x)).
3) The Hessian- deepedent damping term V fxx())) arises due the gradient enhancement (s > 0), and it is known to play a key role in Nesterov momentum and acceleration [1, 35]. When we turn off the gradient enhancement (s
0), we get
+ + (A + +
which is the ODE for Polayk momentum, the equation of motion of ball with unit mass moving in a potential field fx) with a friction coefficient (A + 7).
Proof. We want cancel my The first equation yields
(1 mmm (VK* (#z + Axς) =aVV())))
(22)
Plugging it into the second equation yields
-1- - = -a(11 -
(VVC +EV
(23)
-aV/(=)) (-)]=))>~V7"" (#: Aaz).
Combining (22) and (23) yields
VV (+t + + = 7VK + Are).
dt
Or
V2K +x)) At) ttd 7VK" aVV((()
B.3
DISCRETE-TIME SCHEMES LION-K
In the most general form, the Euler approximation of the Lion-K ODE with step size c is
Ft+1 = It + <(V/C(m - f(x))(()) + +mm) - Axe)
(24)
m++1 m. ((x.) + vm,))
19

---

The discrete Lion-K scheme in (2) is recovered when y $1 E%,, 32 - ey. By scaling f() by a positive multiplicative ratio, (2) in fact covers all cases of (24) when 7 *
When y 0, however, (24) reduces to momentum- variant of Lion-K:
I++1 = 22 + <(VKC(m V Xra)
Undamped Lion-KC
m++1 m, fzt):
which is the Euler approximation of Lion-K ODE ? = 0, step size and 31 = Ea, and [32 ca. Due to 7 O, the undamped Lion-KC amounts solving min, f(x), without the regularization KC* (Ax).
The connection to Polyak and Nesterov momentum discussed in Section extends discrete-time forms. From the first equation (24), we have
m
1
VK
T++1
It + Xwr + +eVV((a)))
--EY EY
Plugging it into the second equation of (24), we get
2:12 2012-2e11 + )me+)) + +cVV((a41) = ex) (0111-
caVs(ar)) - ( (1- X -
Vx"
Hence,
21+2 D++1 + ) = -VV/=))))-/) (a1t1-
+ Xo4 -
) +(e-c)aV((())
V/C
When VAC (x) I, have
-1 2e+2 = (1 ed)ac+1 - - -
+ edxe) + c((=))aafa)
is simplified into
It-2 = /ttp:://aaaaaaaai/./////////////
(zxz))
When E >
(corresponding 31 32 in Lion-K (2)), this can be shown be identical to
the Nesterov momentum algorithm for minimizing F(x) fx xr || /2. When & (corresponding to B1 .3 in (2)), it is identical to Polyak momentum.
B.4 FRANK- WOLFE AND MIRROR DESCENT
Frank-Wolfe
When σ = 1, Lion-K reduces to
d vx(-Vf(z:)) Aee,
(25)
where we also set Ea without loss of generality. In this case, the ODE monotonically decreases the objective
F(x) = f(x) (Ax),,
without resorting to an additional Lyapumov function. This can be seen from
d
dt F(x)) (Vf(z) + VXC'
- Az) < 0,
where the inequality follows Lemma 2.1.
The Euler discretization of (25) is
F++1 2z + (VK(-V((x)) - Axx).
(26)
This can also be derived from conditional gradient descent, or Frank-Wolfe To see this, recall that the conditional gradient descent update for the F(x) above is
Vt++ arg min (((x)) xx) + x 1c (>xx)
x
Øt+1 = 2, + co Iz):
Solving Me+1 yields 1
Ut-1 x vK(-vf(x)),
and hence
F++1 = (1 co)o + " "VK(-V
Taking 6 yields (26).
20

---

Dual Space Preconditioning and Mirror Descent When further set 0 in (26), Lion-AC reduces to
It+1 = mz <VX(-V(()))
(27)
When VK(()- 0, Eq. (27) is dual space preconditioning [23], which is closely related to mirror descent [26], for minimizing f(x). To see the connection with mirror descent, note that (27) is equivalent to
1t+1 xz cò.,
with
d, arg (z)())) T 8 KC)
Because KC* and K. are differentiable, then VK(()) 0 implies (0) 0, and hence K achieves the minimum at zero. In this case, K.* (6) K (0) can be viewed as a Bregman divergence, and hence justifying the connection of (27) with mirror descent. Recall that the Bregman divergence B, (o |I y) is the Bregman divergence associated with a convex function h: Fd + IR is defined as
Bx v) h(x) h(y) Vh(y)) (x y).
With VK (0) = 0, it is then easy to show
1C* - 1C (0) = Bx- (8 0) Bx;; (xt + 66 x1),
where KG = KC
B.5 LION-K WITHOUT GRADIENT ENHANCEMENT (c =)
Theorem B.2. Consider the ODE of Lion-KC-W K-W without gradient correction:
2, = VK((m,) Az,
(28)
rh aV fxxt) 7ms,
with X, a, O. Its fixed point is the minimum of
min 2 (Xx))
)
It yields the following Lyapunov function:
H(x, m. = az(x)) + x (Ax) + (IC + K(m) - Ax T m))
Proof. Observe that
V (x, = aVf(z) + +) Am V H(, V.((m) - Ar.
and (28) can be written into
i == (1) V m (m,
m: = (I,, m²) = V n (Zz, m.) ilm (Z,, me);
with H (21, (1 + am V)*()zz)) By Lemma 2.1, have
A (V m H) (m VX (Ax)) (VK(m)) (VKK)) Ax) 2 0.
Then
d (I., N V4 + V H Vm dt
= V. (V. H) + V H (-V.H - = Am S.
In fact, this ODE has Hamiltonian descent structure [22], it can viewed as Hamiltonian system damped with descending force:
+ V
(x))
-
( A) N vx (Aæz))
m
V H (x), mi)
Hamiltonian
Descent
where the Hamiltonian component is orthogonal to the gradient N.H. V H| of H m) and preserves the total energy H(x, and the descent component introduces a damping like effect to decrease the energy H (x,, m).
21

---

B.6 LION-K WITHOUT WEIGHT DECAY A HAMILTONIAN DESCENT DERIVATION
When the weight decay in Lion-K is turned off (A = 0), there is an alternative way to analyze it that amendable the Hamiltonian + descent structure in (12).
Recall that the Lion-K. ODE is of the following form when X = O::
# (m(m)); mn m. c(aV f(=) + 7ym))
(29)
m4 = V ((+))) -ym
Assume ey < 1. Define K(m) - T- x((1 s7)m), and the following Lyapunov function:
HI,, m) = (z) + K(m) af(x) T- KC((1 -7)mm.
(30)
Note that V Vz m) = fz) and VnH(z m) = VK((1 - ())() One can decompose (29)
into the following Hamiltonian + descent decomposition:
m H mz)
VK(m))
VK((m)
me
V (2,, me)
Hamiltonian
Descent
where we define m. = (1 - and hence m. mg -5 [(
Using the monotonicity of subgradient (Lemma 2.1), one can show that the second component in the decomposition above is a descent direction of H (z, m) in (30):
1) Let HH VVK(M)) VK((m)) then it is descent direction of H m)), because
Vx V. ((x()) T N.H.
(m) - mm)) (VV((())) VK(())) s 0,
where we used the monotonicity of VIC(-).
2) If m = is the minimum of KC, then V H4 == -yym is descent direction of H (x, m) because,
V Hr,, m.) TV V. - my) m. S 1 1 Ey
7
(K(()) KC(1 - m4)m S O.
Hence, we have
H(I,, V (2,, m+) V H, + V H(r, T T H; --1 (m) - m)) (VVC(M)) ((((m)))-<((())))) VKC(m)) ( mm S
dt
Moreover, if m = is the unique minimum of K, and Ey < 1, then VK((( =7)m;) m = 0 implies that m, and one can show that the equilibrium points of (29) are stationary points of H H m) using LaSalle's invariance principle.
B.7 MAIN RESULT OF LION-K ODE
Theorem B.3, Assume is convex with conjugate K*, Assume f,K.K' K* are continuously differen- tiable. Assume (It, m.) is the solution of the following ODE:
i = ((()) - Aree
with
Th = m. - - + (V.().)).
m a fz()) mmm
where a, 7, X, 0 and ey S Let
[xx(Ar) + 1-87
H(z,m)= = af(x) - X
(Xr)()) + K(m) - Am Tm).
1+ ad
22

---

Then H yields Lyapunov function in that
X+ 7 A (ft, (+) +
1 1-87 A2(me, m4) 20, 0,
(2,, m²) A(xe,m))
dt
1 Ed
(1+
where
(x = (m VK (X=*() - Xo),
A2(m, ()) 1 -m (mmmm) vK(m)).
Moreover, the accumulation points of all trajectories are stationary points of F(x) = af(x) + ()x)).
Proof. It is not obvious how construct the Lyapunov function directly from the ODE. The fol- lowing proof describes the process of discovering (x, m). We start by examing what inequalities can write down using the monotonicity of VCC and VK via Lemma 2.1, and then work out the Lyapunov function backward.
Write m- m s(ym + fV))) Because VK is monotonic mapping, we have by Lemma 2.1 the following key inequalities:
(- m + VK. (Ax)) (VX()))) - -a)) 5.
(m m) (VX((m)) VK((m) S0.
or equivalently
(caVS(>)
VX VAx)) O Ax) <0
(31)
e(oV/(x) + ym) ( ((VK((m) Ar) (VK(m) Ax)) 00
(32)
Write V. VK(m) Az, and Vm -av f(x) - ym. So the ODE is ă V2 and m inequalities can be rewritten into
Vm. The
(eaV)(x) (1 - e7)m VK (Ax)) VV 50 - -VV m (Va - (VK((m) - )x)) 0
(33)
(34)
Taking [([+n) (Eq. (33) + 17 x Eq. (34)) for any 17 2 0, we get
aVf(x) - [V
s7 m))
+
1 VK (Nat) V/ +
n/
(VK(m) TT 5o
<(1 + 1))
e(1 + n)
s(1 + 11)
Define
1-1 + ((()) 1- 1- + n) c(1 + n)
EY(1
m) = af(x) + s(1 + n)A
(Cx(
m Tr.
5(1 nn)
Then the inequality was reduced to
Vlre
(z) VV
V (m) 50. 0.
1 ey + +1)
If we take y such that
Yl 1- + 17)
1,
(35)
then we have when following à = V₂ and m = V.n
d H( m) V (., Va + Hm)(m, Vi 50. O.
dt
Furthermore, when (35) holds, we have 1- BY 71 =(> 7))
1 c(1 + m)
X X+7
1 1- + +1) E(1 + 1)
(1 (1-87)A
(36)
1 1
1+
23

---

and hence
((z,m)=af(x) ( A+7 1 1-
((() + 1-27 (K* + +(()) Am Am)x)
[1+
1 1
1 Ed
=af(x) + ()x) + 1+
1-
(Ax) + <(m) Am x)
In this case,
H
H(x (z,m)
dt
1
(Eg. (33) + 1j x Eg. (34))
e(1 +1))
X+7 Eqg. (33)
1 1-
11
1-87
Eq. (34).
11
from (36)
1+
c(1 Eλ)
c(1 + 11)
6(1 (1++aA)
1+ (m - (A=)) T (VK((m)
A A+?
Xx)
1-67 67 (m -m) (VK(m) VK(m)) < 0.
(1 + cAee
To ensure that 2 O, we need ey $ 1.
LaSalle's invariance principle Let (2) is continuously differentiable Lyapunov function of d d d v(z)), satisfying ät ((z)) I 0. By LaSalle's Invariance Principle, the accumulation points of any trajectories of de 2 v(2)) is included in
(the union of all trajectories 2, satisfying d (2)) for all 2 0..
For the Lion-KC ODE and its H, the points I should satisfy mn = (Arz()))), which yields VKC(m) Ara and hence
4 VK((m)) - Ax; = 0.
This suggests that is constant for the trajectories in I. Because m. VK (Azs) and mr my f + yym),, we have
1-mymm== VIC f(x)(
Hence, (1 m7) is also constants in the trajectories in I. This suggests that - ---y)) along the trajectories in I, and hence
= (1 --
-11 - (aV 7m1)
-(1 - Viy-))aa((()) - ~VV ()z;) - eyaVf(
-oVf(xz) (Xxx(
=FF(())) (1(x)) af(x) + 2x0)
X
Hence, all trajectories in are singleton points and are stationary points of the objective F(x:) (f( ()z).
B.8 THE DECOMPOSITION STRUCTURE
We provide the decomposition structure (11) which provides simplified proof of the Lyapunov property.
Lemma B.4. For ODE i; Va( me), m Vm me), let Hx, m) be a function satisfying
V Hx, m) = Vi(x, m) + Vm m)
V H (x, (m, Vz, m),
24

---

where R and V2 and V. have positive inner products with Va. Vm. respectively, that is, Vm(x, m) Vn (z, m) 2 0, Vx,
Vala, m) m)) 2 0,
d Then we have
H m,) S.
dt
Proof.
d (1 VaHl V2 + VnHl ' Vm
dt
= =- + aVm) ) V22 + (-Vm - aVa) TVa)
= = V2 V. 50.
Lemma B.5. Under the condition of Theorem 3.1, let V2(2, m) = VK((m) Ar
m-
(I, m)) aV fx)) -ym
E
and related
Vi m) = (Ax( = -VVV((z) + (1--mm)m VK (Ax);
(2, (m) = VK(m) VK(m).
Then have V. V 2 and VuT Vm 2 0 by Lemma 2.1. Moreover,
N.H HH, m) =rr'V= V
Vm (x, m) -17V + V/V3.
where 1l = 1-ey IteX
and r// = I4eX
7+>
This yields
H (Zt, mz) = V T V2 + Vm Vm = - V2 + +n vm) S 0.
dt
Proof. Let = 1-s7 We have We have
Hx, m) 1 (VK(m) Xx))
= -((V((m)) Ax VK(m)) vK(m))
nnV2 - -vn).
V. v,H(I,m)
Am)
(7 17
+ (a - (7 + v5)) (n)) (7 1))(1 - 57))
7+
fzz) - (1 + f((
mm
-Ite
7+ VV-
I+
where we used the following identities v):
+ 1 87 7
1+ 1+
7 8
1-E7
1 1- ()+) = 1 Ital
++ =1
a - +7+ - + 7+1 X
672 2-
1t 8q
-
1+
25

---

B.9 CONSTRAINT ENFORCING: CONTINUOUS TIME
When K can possible take infinite values, the minimization of (x, m) becomes a constrained optimization. Let domP>* (x:: K.* (x) +000. The optimization be framed
min H (z, m)
s.t. Ax E domM
The Lion-AC algorithm would first steer the region where K has finite values, and then de- crease the finite parts of the objective function. In the following, we show that Lion-K enforces the constraint with fast linear rate: the distance from Xx; and domK decays exponentially fast with time I, and once Aro E domk.", then Xr, stays within doml.* for all / >> lo-
Theorem B.6. Under the condition of Theorem 3.1, we have
dist, domlC*) S exp(A(s 1)) dist(Arr;; domm.))
Proof. Define Wi-+ = exp(A(s - t)). Integrating in = VK((m)) - Arz we have
Sr Wr Vi(, 5
Arę = (1 - W. Wo-s))=s-1t + w. (Axs) where 2x-st
S Wr-der
We have VK(mm-) E dom from Lemma B.7 and domI convex. Hence 25-st, as the convex combination of [V.((,, Ir. belongs to domK." For any > O, let Xē, E domm to the point satisfying |A Ar & dist d + e. Hence,
dist(Arı, domk))=
inf
||Az; - 2||
zEdomk
s Aa - (1 W W3-st) - We stis)
Wa-s ||X Xd
S exp(2(s - (Xr domk"" + +).
Taking -> 0 yields
dist(Aa,, dom)(*) S exp((((s - ()) dist(AA,,, domX)*).
Lemma B.7. Assume K. is proper, closed and convex, and IC* is the conjugate K. We have @K((=) C domIC",
Vz E domK.
Proof. If x E OK((2), then attains the minimum of K*(x) sup, K({)), suggesting that KC* (x:) = x K(=) +oc, and hence domK>*
B. DISCRETE TIME ANALYSIS
Theorem B.S. Assume f: Idd + I is L-smooth, and K: IRd - R is closed and convex. Consider the following scheme:
m4+1 = 32m - (1 - (1-33)V// /2)
m Bimm (1- (I,)
(37)
Et+1 = It + e(V - \x(41),
where VK a subgradient of K. and B1, B2 E (0, 1). and B3 > Br. and e, > Let K* be the conjugate function of K. Define the following Lyapunov function:
1
31
H(x, m.) f(x) + KC* (Ax)+ c
(K (Ax) + K(m)) Ax"" T m).
31- + (1-1111)) 32)
and
A = (VK(mu4)) - (x(+1) (m++1 ( (Are+11))
A (VK(m441) - vK((m+1)) (Mie44 ml-1),
26

---

where VK is subgradient of K. Then we have A 2 0 and A 2 0 from Lemma B.9, and
L
M++1) - ((z,, - -((as) + bDA)) +
[VVK(m++1) Ar
where
cΛ3 +120,
81 (2)
b
2 0.
31) + 32)
(32 - Bi) B1) + -1-132)
Hence, a lelescoping sum yields
H(aam))) (xT, mr)
Le Bi,
Σ
a + EA
+ 2
cT
where B, = Ei [k( x
Note that we used an implicit scheme the update of æt in (43). It equivalent the explicit scheme with adjusted learning rate:
Le+1 = It 1+
(VK(m++1) -xxt).
Proof. We follow the proof in the continuous-timg case to find out a Lyapunov function for the discrete time update in (43). We start with constructing the basic inequalities and work out the Lyapunov function backwardly. From Lemma 2.1, we have
(VK(()++1) - Xx++1) (VK* (Aæe+1) - mm+11) S.O.
(38)
(VK(m)+1) VK(m++1)) (m++1 - m++11) S Taking a x Eq.(38) + b Eq(39) for b 2 O, we have
(39)
(VK(()+1) 1 (X - mm + 6(m++1 - m++1)) +
+ +(V(((me+1) A1(+1) T (-me+1 + +m++1) 0.
Plugging (43) yields
(VK(()+1) (r(+1) (AVK ((a b)39 b,3gm, + (a (a +)88888118 +)8 (m, + (zxx)) 0
- -b(32- - (VV(m(((++))) - AI (m,+
Define
(( (a- ()) + a j (xx)) + c (((m) - cr T m, with c= (a b)33 bB2,
and
1.11, - (((x)) (Vk cmps
Vnll VX((m+1) cr
Then the inequality can be written into
H. (VK(m-1)) Ar++1) + H. [b1B2- 1182-Bap B1)1 (-m+ (-m.-V\(xx))) SO.
Vs(ut))
Plugging the update rule of 2441 = xz + (VK(m++1) -X0141) and mm = -(1 32) (x(x))), we get
H.H.T (
x2 ( M
( (c(l-32) B2)
(D(3) (b(82-31)4 31)A
(m++1 me) s 0.
-mo)
To make this coincide with the linear approximation of the difference (10441m444)) - H H(,,, (see Lemma B.9), we want
b(32 -B1)
c(1 -82)
27

---

On the other hand, to make the coefficient of f(z) in (x, equal to one, want 1. This yields the following equations on a, b, c:
b(32 31) 1
c= (a + 6) bB2,
a 1,
a, 2 0.
c(1 82)
To solve this, let c = zc( B and b = =(1 - 52) for some 2 0 and plug them together with a c+ into the first equations:
zc B1)A = (=c(22 + + - 82)) - x(1 -2)
We get
31
2 - - B1) c(32 B1)A31 82) (1- B2)82
31
ex(32 B1)(1 - 31) + (1 (2) 31)
81
(32 - Bi) - B1) + (1 32)) 0.
Hence
3, 32)
eλB1
20, 0, c=
20, a=c+120 0.
(32 - 31)(E - B1) + (1 (1-13) B2))
eX(1 - B1) + (1 32)
In this case, have
1
H(r f(x)= + x0 (Ax)) ((IC((az) + K(m) - Ar xx=mm) m)
f(x) + 1 xx(()x))= + <2(1 (1 32) (1" (Axt) K(m) dx" m). Jm)
and
Vm H,!
[M++1- - mh ( = =-ad! - b0, SO.
From Lemma B.9, we get
H(I141, (2,, S -e(ast + b0))) + 2 ||:41 -
xell2
Lemma B.9. Let H(x, m)) m f(x) + (x)) + K2(m) - Xam, where J is L-smooth, and K1,, K₂. are convex functions with subgradient VK1 and VK2. Then
L - 2 | - 2el12
H ((e411)m41)) - H (I m.) < A H (I++1 21) + FmHl (m++1 m)) + where
A.H, Vf(xa) + KC (x(++))) Am
v, H, = (2(+++1) A
Note the use of dn vs. Ie+1 and my vs. m441 in H.H, H4 and & Hy
Proof. We have
f(1141) f(x)) < Vf(x)) (I++1 - 21) + 2
| - 22
(1(())) (x,)),) < ( T
(#c+1 xx+)
Ko(me+1) K2(mm) < VK2(m++1) (me+1
[ - -m,)
T 1 - x1 m4 = mf (#r+1 xx) + x (m++) me).
Summing them together yields the result.
28

---

Theorem B.10. Under the same conditions of Theorem for any two integers S t,
dist(Ax,, dom I ( (1+c)) dist(Xz,, domk Vs S t.
1
Proof. Rewriting the update into the explicit form:
1 Tee + E VK(m++1).
Tz+1
Ited
( I+ex
b-8
Unrolling this update yields, with W5-st
E Ekast1 Wh Wk-s VK((m)
Az; = (1 - W w.-s))a-stt + Wx-
2g-st
Ek=st1 Wk-st
We have V domm from Lemma B.7 and domX is convex. Hence 28-te. the convex combination of [Vi(mm)a j. belongs to domAC*. For any 1j > 0, let dd, E domM. to the point satisfying |At, Ar,, S dist domk.*) + 17. Hence,
ditt domX
= inf ||xr - =|l
=Edomk.
< ||x (1 -1 -W5-)))2s-1 + ws -s-s
W it |At, - X
1 9-t
(dist(Ax,, domm + 17).
I+ed
Taking 7) + yields the result.
B.11 ANALYSIS WITH STOCHASTIC GRADIENT FOR LION-K
In this section, we are going to have the convergence analysis of discrete time Lion-IC. The proof idea is adapted for section B010, by defining the same Hamiltonian function, obtain the bound for A and A?.
Compared with the deterministic case, the main challenge is bound an additional correlation term due to the stochastic gradient at each iteration t:
V, = cov (gr, VIC(f++1) ()) = cov(ge, VK(3ime (1 Bi)g:)),
(40)
where cov(X,V) Y) E[(x B[X]) - -E((Y)).
Definition B.11. For a random variable X on Rd, its (trace of) variance var(X), when exists, is defined as
var(X) = E|| E|X1|
Assumption B.12. Assume
Umax
var(gr) <
Thatch
where Tbatcch represents the batch size.
Assumption B.13. D the data distribution, the stochastic sample & ~ D i.i.d, given a function fx: E), the gradient V fz; {) is taken with respect variable and E[) = (fzz)
Theorem B.14. Under the assumptions delineated in B.13 13 and B212, consider fffunction f: Rd + R that is L-smooth. Additionally, let K: RRd R. be a closed and convex function, consider the following scheme:
M4+1 Bamm (1 -2)gg
m++1 = 8ime - (1 - -11ge
(41)
2t+1 St c( (VK((m+t1) \m
29

---

where gi (f(zri Et) as shown in B.13, mo.91.- 91...... "2......tt...................... .t..... random variables with
Eigd] = f(()). VK is a weak gradient of K. with VK(() = 0. [VV((z) - [VX()) -
LK. I vll Va, y Rt. and Bi, B2 (0, 1). and B2 > 31, and e, x 0.
Let IC* be the conjugate function of K. Define the following Lyapunov function:
1 + K (Ax)
31
= =(z,m)=
(K" (Ax) K(m)) dx Aamm).
211- + (1 32)
and
4 = (VK(m4+)) - (1(+1) (mi+1 - V.C VIC (Ar++1)),
A (VK(m442) - vK(m++1)) (m++)1 m4-1);
where VK a subgradient of K. Then we have A 2 and A 2 0 from Lemma B.9, and
LE"
E [H(14,,, m++1) - (T2, me)] - E
- -e(as, + bat) + VK((M++) - >x l1
2
LK (1 B1)
Umar Thatch
LK
(1- B2) Umaz
te 1+ da
I de
(1+ 32) Nbatch
where
B1 - -32)
+1 1120 0,
b=
2 0.
eA(1 21(1-11) + (1 82)
(32 31-](1 B1) + (1-32)
Umax, Thatch are defined in B. 12
Hence, a telescoping sum yields
T Σ
1 E [aS
b S E
H (2o, mo) H(TT mr)
Le
B,
Ci
cT
2
Thbatch
where B, = + ΣT VK(m++1)
Ar 112 and C₁ = ( Lx (1 - -11)
Lx It
(- (I+Ba)
Pgg
I+Ac
Umaz-
Proof.
The proof is a simple extended variant of 4.1. Following the proof of Theorem B.8, define
H(r,m) = (a - c)x()) + K (Ax) + ((()) - cx T m,, with c= (a + b)3 6B2.
where
EΛ,3,
-1 - 32) + +120, b= (B2 3i)(e(11 Bi) + (1 B2))
20, c= a-
eX(1 - ((11-1))+ ++++1111111 (1-B22) 322
By the definition of 41, Aj, we have ! b
a ((V(()+)))))) - Am++1) ( (X2+11+++)
+ bVKK(m++)) - VK((m+))) (m++11 - m++1)
(VK(m++1) - > (a(VVK - -1++1) + b(m++1 - m)-1))
+b( +D(VK((4+1)) (x(+1) (m++1 mm+1)
-(VK((m+1) )1(+1) (OVK** - ((a + b)35, bB2)mr + (a - (a + b)8 bB2)) (z())
6 1 82 c -
32 B1 X - ( -C(+1) 7(m+11 - -m))
-mm]] = =- [(a c)ge + aVK* (Nr+++1) - c (VK(m)411) - \w++1)
C [K -c04t1] (mi41 m²)
1 [(a - c)g + aV tVVk cmil (#141 xz)
1 LA
- -cest1
(m+41 mc)
(42)
30

---

By Lemma B.9,
L r - xel12
H1 m++1) - H(1, m.) S H. (0++1- - xι) + VnH, (m4+1 m)) + 2
where
(a
cmly
H, A
C VV(mm++1) ed (Va,s VK((m++)) VK(me+1))
with
Vg, 1c+1 - 2t = c(VK(mm+1) - xx(+1)
Vm, m4+11 144 -(1 32) m2)
ma+1 - M++1 = (32 (9t - -m²) = -132 -B1)V
Vm, -VK((+++) VKK(m++))
This gives
H (6 (H m.)
$ H.H, (I141 x1) + V H, (mi+1 - mi) + L
| =x
2
Hence,
H1I+1 m441) (x m.) S (a ()) + (A641)) (V cmmll (x141 - 1z))
C [ co.++ (maH1 - -mm) + || - -2:e13
A
1(a c)gi VVK' -cmel
cmi]" (Ie+1 xz)
[V -c0+1] (mo+1 - mm)) + L || xx
2
c(a (v)(()))) 1 (VVK((44))) -xx+11)
-c(aai +b4/) + 1/1
2 1112011 2.112 //by equation 44
(aa - (v)))))) T (VKK(())+)) - \m(+1)
It suffices to bound E [VV T(V (VK((+++)) \(++1)]-
Note that
E [VV((=)) 91) (VK(m+++1 A
= (V (x)) (1) i de
1
VI((mi+11
1 Ae mt)
1
À
E (VV)(z)) 91) VVK(m=+))
E [(Vf(z)) TTa)
1+ Ae
1+ λE
By Assumption B.13,
E [[V g.) xxx)] AB., Eg, [Vf(xz) f(( m
=0 //by B.13 [V) = V\(x)
Next, let bound E [VV[(x) 9:) VK(me+1)]
E (V)(x)) 9t) VIC(m++11] E [V]((x)) - 9.) VK(3im (1 B1 91)
Lxc(1 31) 31)var(g)) + Lx / /var(8mm)) var(ge)
//by B.18
(1- 32) Umaa
Lx(1 31) Umar Lx (1 B2) Pbateh
//by B.18
Nhatch
31

---

Hence,
(V)(zt) 9t) (VK(M++1) - Amc+1ll
X E [(Vf(xx) "
E [[V](()) 9a) [[(M++1)]
+ 1+ de
*+ de
LIC (1 -1-11) B1)
Umar
Lu
(1 - (3) Umar
+ de
Whatch
1 de
(1+ B2) Tbotch
Y be two - random variables with var(X) too and var(Y) +oo, and assume K. yields a weak derivative VK. We have
Lemma B.15. Let X, X,Y
BI(Y EY) VK(X + +X)] S Liceva((Y) + Lxvar(X) var(Y)
Proof.
-[(Y--(Y)) - TEXY))VXXX + ++Yo]
E((Y-=(V)) (VK(X + +6 - +R(I)
VEIIY E BIVVCC + + [ + +
=VE WE I| E| LEE + c E[x] - 2
LKV L I E|IJI (VEXX-EXXI) + V J|Y EE(111?
LxCE IIY B| + TEVBII BIY B[Y]1 / - E[X]|*
= Lxevar(Y) + Lx var(X) var(Y)
Lemma B.16 (Cumulative error of stochastic gradient [4]). Following the same setting in theo- rem B.14, denote 6, 91 fxx)), for any k oc and fixed weight -oo a1, ... Og 0o, Σ 8t is Martingale. In particular,
E
Σ ond
aja²
1=1
Proof. We simply check the definition of a Martingale. Denote Ys = Σ ajor First, have that
k |aa [
Y = E
Σ
triangle inequality
Σ Jan EE 6 [[]]]]
law total probability
Σ oon Bly E 21]]
Jensen's inequality
Jaz la < x
32

---

Second, again using the law of total probability,
E[ 111, Yal = E
andj aidi
andR
Y 0tg+1
E [ōk+1 a1 5 Gg
= V/2 + 0c++1
E TR [ 11+1, an o1 dx laid1, 046k)
Yx 00-4
E [8k+1
Yk
This completes the proof that it is indeed a Martingale. We now make use of the properties of Martingale difference sequences to establish a variance bound on the Martingale.
Bla oj + Blara,
Σ
6 8111] + E aja (l,b6 .... 0z ) [|]6
01,,0,,.,,,1111111 51-1166 8111] +0
1=1
a afa²
The consequence of this lemma is that we are able to treat 81,..., 6g as if they are independent, even though they are not-clearly 5, dependent on ój...., 8 through rt. By Lemma B.16, we can compute the variance of momentum 1/4
t
var(m;) (1 (1
32 6,
i=
(1 32
32 22 18:11
(1 Umaa
(1 + M2)atthh
B.12 ANALYSIS WITH STOCHASTIC GRADIENT LION
Theorem B.17. Under the assumptions delineated in B.13 and B.12, consider a.function f: Bd R that is L-smooth. Consider the following scheme:
M441 32m (1 - B22gt
m 8im, (1 B1)gt
(43)
Ø1+1 = Dt + c(sign(mit+)) Xx++1),
.t.............................. .t.... are random variables with E[gd] = fxxx). 31,32 1), and 32 > Br. and e, 0.
where St = V as shown in B.13, mo, .
Define the following Lyapunov function:
1 - |xx11" eX(1 - Bi) + (1 B2) (||x=| + ||m]|| Ax TTm).
B1
((x, m) f(x)
and
1 = (sign(me41) - Xx(+1) (M++1 - sign" (Ax++1)))
A (sign(me+1)) - sign(me+1)) (Mi+)))))))+11111111111 m++1);
33

---

where sign' is subgradient of KC" Then we have A 2 0 and A 2 0 from Lemma B.9, and
Le
d Umaz
E me+) ( S E
-e(as)
bم +
2 [[sig(((u+1) - Xo++
+ 1 d /bbttc
where
eA31 a <X(1 -11-31) 31) (1 32)
B1 B2)
+ +100,
b
2 0.
(32 Bi)(eX(1 Bi) + + (2))
Umax Abtthh are defined in B.12
Hence, a telescoping sum yields
T-1 T
H (20, mo) - HHHT, mr)
Te
1 v Umaz
B + bae E
+
B₁ +
cT
2
1 Ac
Bbatch
t=
where B, = EE= sign((u++) 212+1l12
Proof. Define
H(z, m) (a c)f(x) a ||_l" [m cr T,, with c= (a b3,31 -632,
where
81 - (2)
+120, 0, b= - B1) (1 (3))
20, c-
c²(1 31) (1-13) (22
By the definition of 4 A7, we have
a + 1
al - 1 (m++1 - sign" (Xx++))
+ +(sign((+++1) - sign(m(+1)) (m++1 m++1)
=sign((m++1) )x(+1) T (a(sign" (Ax++1) me+1) b(mm+((m1111 -m++1)
b(sign((m+4)) - (2(+1) ((m+1 - m4+1)
- Ar (asign" (rriggn"(XXx+4)) - ((a + b)31 - bB2)mm + (a (a- (a b)81 + b32) fxx))
32 81 > ( (m44))
c04+1 (m4+1 -CE411)
m²)
1 32
= =- [(a c) + asign" (A0++1) - cmm]] (sign(me++1) - \m(+1)
[
c sign(m++1) cB4+1] -c0++1] (m++1 m²)
I(a c)gr + asign" (Ax++1) cme]] (1124 Iee)
7 sign(m++1) -c0e1]] (Me+1 me)
(44)
By Lemma B.9,
L H( m4+1) H1,, m.) < V.H, (It+1 1T,H11111111 - 21) + V H, (m++1 mc) +
| - xrl12
2
where
V H: = (a- -a (a-c)vf(x)) + asign" (A#141) cma,
V H, R 1igg((m+1)) CT++1 ex (VV.. sign(mmu1) + sign(mes1)
34

---

with
V2, F++1 2t = c(sign(me+1) Ar(+1)
Vm,t = m4+1 my -(1 - (2) m²)
me+1 m441 - (9) m²) -(32 Vm,
Vm,e- = - + sign(m++1)
This gives
H ([4+4. H mz)
L | - 20112
$ V.H, (It+1 - x1) V H, (m++1 - mi) +
2
Hence,
H H(141, m441) - H m²) & [(a fx)) + asign" asign" (Mxx+1) -emi] (0 - -x2)
c [x sign(mu+1) - co1+1] (m441 - me] + L | - 22112
+
((a c)gi + asignn assign(Xxx++1)) - cmi]" (Ie+1 21)
+ [ sign(m+++)) - c24+1] - (m+41 - mm+ + - | - 22112
CC
L
2
c(a (V[((())) - 91)) ((sign(((()))))))) Ax
L
( + bn7) + - 10++1 1212 //by equation 44 2
+ c(a - f - 91) (sign(me+))) A2(41)
suffices to bound E [VV[(x) 9t) (sign(miz+)) \m++1)]-
Note that
E fxx)) - gi) (sign( - Ar(+1)
A
E (V (xx) 9o)T( ( 1+ Xe
sign(me+41)
+ Xe m1) +
E [(Vf(x;) - gi) sign(mi+1)
[VV((z) g
1+ Ae
+ Ae
By Assumption B.1
[V) g.) {xx)]] ABEr, [Eg, (Vf(z,) vf [=,1
=0 //by B.13 =[V](r,E))=V[l
Next, we can use B.18 to bound E [(V)(x)) gz) T sign((i++))
E (V)(z)) 9t) sign((f++1)
(V)(x)) 9t) sign(Bim, (1 B1)9.)
/ d var(gr)
//by B.18
d Umar Ubatch
l/by B.12
Hence,
E (V)(zz) - gc) (sign(mi+4) Ax(+1)]
1
A E [[Vf(x;)) - 9.) T
E [VV((z)) - gt) sign(me+1)]
I Ae
I + Ae
1
d Umax
+ Xe
Abatch
35

---

Lemma B.18. Let X.Y be two -V-uuue random variables with var(Y) < too, and assume K.
yields weak derivative sign. We have (E((Y EY) T sign( X + cY) S vdvar(Y)
Proof.
EIYY EE(I) sign(X + +cr) Bijy E|yIl| - E| Vd var(Y)
36


Reviews:
[{"review_id": "InEnLrKMoN", "reviewer": "Reviewer_GtGX", "summary": "This paper studies the Lion optimizer, which is discovered through program search. It is shown that Lion indeed minimizes the loss while constraining the $\\ell_\\infty$ norm of the parameters. Specifically, the authors proposed a general framework for analyzing a general class of Lion-type algorithms, which lead to solutions of general composite optimization problems determined by reshaper function. Theoretical analyses revealed the two-phase dynamics of such algorithms: In the first phase, the iterates convergences to the constrained domain exponentially fast; then in the second phase, the dynamics minimizes the objective.", "questions": "In Section 3.1, the authors discuss the connection with existing algorithms. Do the corresponding convergence results also reduce to those classic ones?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is well written and very easy to follow. The proposed framework is very interesting, not only demestifying the Lion optimizer, but also encompassing many other algorithms. The authors have clearly explained the idea and discussed thoroughly the related background. The results seem solid and novel.", "weaknesses": "1. The current analyses apply to only algorithms with full gradient. It would be interesting to see results for Lion with stochastic gradients.\n2. It would be helpful if the authors can discuss and comment on the implications of Theorem 4.1. Also, it is worth explaining why it is necessary to use a different implicit scheme.\n3. Typo:\n    - In the first sentence in the paragraph above Figure 4, \"difference $\\mathcal{K}$\" -> \"different $\\mathcal{K}$\"\n    - The second paragraph above Lemma 2.1, \"a systematic introduce to ...\" -> \" a systematic introduction to ...\"", "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": "puGksq8vMd", "reviewer": "Reviewer_fjaH", "summary": "Authors use the analysis of the Lyapunov function to prove the theoretical guarantee for a broader family of Lion-K algorithms, in which the lion algorithm is part of. Authors also discuss connections of Lion-K with existing algorithms. They also emphasize it is still lack on the physical intuition on this algorithm.", "questions": "1. Can you comment on the convergent rate of lion and lion-K algorithms, based on the current results? Why it performs comparable or favorably to AdamW? \n\n2. Can you comment the possible convergence on lion-K vs interesting decomposition (12)? It seems they may both work well.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper is very well written and super clear. Authors make every effort to have all the points stated out in a very concise way, even for the audience without too much background. The key contribution is they found the Lyapunov function for this family which is completely non-trivial. The guessing requires lots of trial and error. With the Lyapunov function, the optimization schemes are theoretically guaranteed", "weaknesses": "To demonstrate efficiency in the conclusion, authors didn't compare with other methods. At least, it is necessary to include other benchmark algorithms in empirical evaluations.", "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": "BURSFJdPLb", "reviewer": "Reviewer_2PBx", "summary": "This paper provides a theoretical understanding of the Lion optimizer, a new optimizer discovered by program search. The authors introduced a general class of optimizers, Lion-$\\mathcal{K}$, and showed that these optimizers minimize the training loss $f(x)$ with an additional constraint on $\\mathcal{K}^*(x)$ via a Lyapunov based analysis. The Lion optimizer corresponds to the case where $\\mathcal{K}\n$ equals the $L_1$-norm of $x$, thereby imposing a constraint on $\\|\\|x\\|\\|_{\\infty}$. Extending beyond Lion, the proposed Lion-$\\mathcal{K}$ also encompasses algorithms such as Polyak/Nesterov Momentum, Singed Momentum, and (Accelerated) Mirror Descent.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The main idea of this paper is novel and interesting. It offers a fresh perspective on the theoretical understanding of Lion and sheds light on the role of the key components, such as the (decoupled) weight decay and the gradient enhancement (the Nesterov trick). The proposed family, Lion-$\\mathcal{K}$, also encompasses a wide range of optimizers.", "weaknesses": "1. This manuscript appears to be incomplete. Notably, there is a lack of discussion on related works, and the empirical results presented in Figures 1-3 are neither interpreted nor mentioned, even though there seems to be sufficient space for such discussions. I strongly recommend that the authors enhance the completeness and rigor of this paper via:\n   - Interpretation of the empirical results, \n   - Ablation studies on the key components of Lion to justify the theory, \n   - Empirical validation of (at least some) algorithms listed in Table 2. \n\n2. This paper does not connect the superior performance of Lion or other Lion-$\\mathcal{K}$ optimizers to their main finding. How does this additional constraint help optimization or generalization?\n\n\n3. (Minor) Some typos:\n    - In the definition of the conjugate function below eq (4), the subscript should be $z$ instead of $x$. \n    - Above Lemma 2.1: crucial rule -> crucial role. In Lemma 2.1, $\\nabla \\mathcal{K},\\nabla \\mathcal{K} \\to \\nabla \\mathcal{K},\\nabla \\mathcal{K^*} $.", "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": "cU33zyAOKj", "reviewer": "Reviewer_GggD", "summary": "This paper analyzes the recently introduced Lion optimizer, which was found previously in the literature through program search, and shows how it fits into a general family of optimizers, Lion-$\\mathcal{K}$ which are shown to optimize a specific regularized/constrained version of the original cost function. This optimizer also recovers several known optimization methods from the literature such as mirror descent, momentum or weight decay. The analysis of this optimizer is done by proposing a new general of Lyapunov function yielded by the dynamics of Lion-$\\mathcal{K}$.  Results are provided in the continuous time and discrete time setting. Additional experimental results are provided to illustrate the training dynamics.", "questions": "I just have one question regarding the impact of the non-differentiability of $\\mathcal{K}$: \n\n(a) In the continuous-time setting, it is assumed that $\\mathcal{K}$ is differentiable. Then in such case the convergence to a stationarity point of the constrained/penalized function for the (continuous-time) algorithm is established in Theorem 3.1. \n\n(b) Then, a discrete-time analysis is provided, which allows $\\mathcal{K}$ not to be differentiable, but however in such case I think the result is a little bit more difficult to interpret: indeed, the only result provided is  Thm 4.1, which is about $H(x_{t+1}, m_{t+1}) - H(x_{t}, m_t)$ (or, alternatively, about the sum of deltas), but unless I am mistaken, there is no result that looks similar to convergence to a stationary point of the constrained objective (there is also Theorem B.9 in Appendix but that one describes only the first phase of the dynamics). Therefore, I think it is a bit hard to verify from reading such theorem whether the conclusions of the discrete-time case (which correspond to the algorithm used in practice) will actually match the conclusions from the continuous-time case.\n\nMore precisely, those two theoretical results above are interesting in themselves, but I am just wondering to what extent they can indeed successfully predict the actual behaviour of the Lion-$\\mathcal{K}$ method: indeed, as mentioned in the paper, Lyapunov analyses need $\\mathcal{K}$ to be differentiable.  When the function $\\mathcal{K}$ is not differentiable (as it is the case for the $\\ell_1$ norm which is considered in the paper), analyses can break. But I believe this is more than just a technicality, i.e. I think the behaviour of algorithms for differentiable vs. non-differentiable $\\mathcal{K}$ may be quite different: indeed, in the simple case of mirror descent (section 3.1), for instance, writing the discrete Mirror Descent update naively with $\\mathcal{K}$ taken as the $\\ell_1$ norm gives an algorithm of the form $x_{t+1} \\leftarrow \\text{sign}(x_t - \\nabla f(x_t))$, which clearly does not converge in general to $min_x f(x)$ as iterates remain restricted in $\\\\{ +1, 0, -1\\\\}^{d}$ (the same problem would also happen for the continuous case Mirror Descent). But however, I think that having a non-differentiable $\\mathcal{K}$ for the usual discrete-time Frank-Wolfe is OK.\n\nTherefore, I believe it would be good to elaborate more (and/or give more references), in the continous case, on why the analysis of Lion-$\\mathcal{K}$ would still somehow be valid or almost valid for non-differentiable $\\mathcal{K}$, and/or, in the discrete-case setting, to give more details or a more intuitive reading of the result in Theorem 4.1. I think this would allow the reader to further confirm that what Lion-$\\mathcal{K}$ is doing is indeed constrained/penalized minimization, without worrying that issues similar to the ones of Mirror Descent happen in the case of Lion-$\\mathcal{k}$.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "### Originality\n\nI believe the work is original, as it is, up to my knowledge, the first to propose such a general general Lion-$\\mathcal{K}$ algorithm along with the corresponding Lyapunov function for its dynamics. In addition the derivation of such a Lyapunov function seems non-trivial, and I believe it will be of interest to the community.\n\n### Quality\n\nI believe the quality is good, as theorems are clearly stated with their assumptions, and full proofs are well detailed in appendix, and with an overview in the main body. Particular care was also taken in the experimental analysis to verify the theoretical results in practice.\n\n### Clarity\n\nThe work is clear, theorems are clearly stated as well as their assumptions.\n\n### Significance\n\nI think this work is very significant, since Lion is currently a state of the art optimizer in deep learning, therefore analyzing its dynamics is of very high importance to the machine learning community. Additionally, the discussion on the relationship of Lion-$\\mathcal{K}$ with other methods from the literature such as Mirror Descent, Momentum etc makes this analysis even more relevant and general.", "weaknesses": "I just have a question regarding the impact of assuming differentiability of $\\mathcal{K}$ in the continuous-time analysis (see question below).\n\nI also noticed just a few minor remarks/typos:\n- “Going beyond Lion, difference $\\mathcal{K}$” —> “Going beyond Lion, different $\\mathcal{K}$”\n- “One can think Lion” —> “One can think of Lion”\n- “Gradient Enhacenment” —> “Gradient Enhancement”\n- “Section 3 analysis” —> “Section 3 analyzes”\n- Appendix B.6 : “Becomes a contraint optimization” —> “Becomes a constrained optimization”\n- Although I think the Figures 1-3 are nice, unless I am mistaken those are not mentioned in the main text: I believe it could be good to mention them, for instance after the discussion on the different phases of training.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)