How Memory in Optimization Algorithms Implicitly Modifies the Loss
Authors: Matias D. Cattaneo
Boris Shigida
Venue: NeurIPS 2025 poster ()
Keywords: memory
momentum
implicit bias
implicit regularization
generalization
adaptive methods
Adam
Lion
signum
gradient descent
Primary area: optimization

Abstract: In modern optimization methods used in deep learning, each update depends on the history of previous iterations, often referred to as memory, and this dependence decays fast as the iterates go further into the past. For example, gradient descent with momentum has exponentially decaying memory through exponentially averaged past gradients. We introduce a general technique for identifying a memoryless algorithm that approximates an optimization algorithm with memory. It is obtained by replacing all past iterates in the update by the current one, and then adding a correction term arising from memory (also a function of the current iterate). This correction term can be interpreted as a perturbation of the loss, and the nature of this perturbation can inform how memory implicitly (anti-)regularizes the optimization dynamics. As an application of our theory, we find that Lion does not have the kind of implicit anti-regularization induced by memory that AdamW does, providing a theory-based explanation for Lion’s better generalization performance recently documented. Empirical evaluations confirm our theoretical findings.

How Memory in Optimization Algorithms Implicitly Modifies the Loss
Matias D. Cattaneo" Princeton University
Boris Shigida' Princeton University bs Ds16240princeton edu
Abstract
In modern optimization methods used in deep learning, each update depends on the history of previous iterations, often referred to as memory, and this dependence decays fast the iterates go further into the past. For example, gradient descent with momentum has exponentially decaying memory through exponentially aver- aged past gradients. We introduce a general technique for identifying a memoryless algorithm that approximates an optimization algorithm with memory. It is obtained by replacing all past iterates in the update by the current one, and then adding a correction term arising from memory (also function of the current iterate). This correction term can interpreted as a perturbation of the loss, and the nature of this perturbation can inform how memory implicitly (anti-)regulle Jregularizes the optimization dynamics. As an application of our theory, we find that Lion does not have the kind of implicit anti-regularization induced by memory that AdamW does, providing a theory-based explanation for Lion's 's better generalization performance recently documented [13]. Empirical evaluations confirm theoretical findings.
Introduction
Many optimization methods used in deep learning are first-order methods with exponentially decaying memory. For example, adding "momentum" to gradient descent (GD) is well-established practice to make training smoother and convergence faster (c. g. Krizhevsky et al. [39]). Adaptive methods such as Adam [36], RMSProp [61], AdamW [46], and AdaFactor [57], which are commonly used to train large language models [27, 21, 15], all have exponentially decaying memory. Despite the popularity of such optimization methods, there is little theoretical knowledge about the implicit bias memory introduces to them (potentially informing what regions of the loss space the method takes the iterates to, what minima they converge to, how such minima influence the generalization of the trained model, and on). In this article, we introduce general framework for identifying such biases.
We study a general class of optimization algorithms described by the following iteration ( ((n) h f())
(()))
(1)
where ((m) E Idd are the (evolving) parameters of the machine learning model, (0) is some initial condition, is the step size or learning rate, and the functions f()) map from (some subset of) (Rdy IRd and allowed be different each iteration. The right-hand side in Equation (1)
depends on the whole history of previous iterates, which means the algorithm has memory.
Authorr are listed alphabetically by name.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

For many algorithms used in practice, dependence on the history comes in one specific form: by using what we call "momentun variables", that is, exponential averages of some functions of the iterate @l3) (usually, more specifically, functions of the loss gradient). We present five leading examples to illustrate this point.
Example 1.1 (Heavy-ball momentum gradient descent; Polyak [54]). This optimizer can be written in the form (1) with
(O!m)
0 ( = mi
(x+1)
where
mi (n+1) Σ g" MO--VLLC (L((())
some initial condition (()) and where 3 E [0, 1) the momentum parameter, C is the loss function to be optimized, and V C is its gradient.
The optimizer in Example 1.1 is often just referred to as GD with momentum, where the exponential sum m m=[=+1) in Equation (2) the "momentum variable": it exponentially averages past gradients. The aforementioned optimizer is well-known and often used for training recurrent neural networks and convolutional neural networks, but underperforms adaptive optimizers when training other architectures such as transformers [68, 45, 2, 40J. The following modification is also commonly used (this formulation is taken from Choi et al. [14] and matches the standard PyTorch implementation) Example 1.2 (Nesterov's ' accelerated gradient descent; Nesterov [53]). This optimizer can be written in the form (1) with
F(1) ((())
((0)) m
(n+1)
(n+1)
+ m2
where
mi
(n+1) = 3
ga- (())))
m2 (n+1)
(L((()))
for some initial condition (()) and where 3 E [0, is the momentum parameter, C is the loss
function to be optimized, and V C is its gradient.
The next example presents the most prominent adaptive optimizer, nowadays commonly used for training large language models [27, 21].
Example 1.3 (AdamW; Loshchilov and Hutter [46]). The optimizer can be written in the form (1) with
(n+1)
(1)) (e(
)(0))
m
(n+1)
+ +m
(n+
m2
+
where
m
(x+1)
1 31
3
(((())
1
gx+1
k=0
1 B2
n
m2 (x+1)
32
aa-k
(V
1
k=0
(n+1 1)
(n)))
m
for some initial condition (0)) and where < 31, < are momentum parameters, e > 0 is numerical stability parameter, 0 < is weight decay parameter, and the squares and square roots are taken component-win wise.
also "momentum variables": exponentially averaged gradients and exponentially averaged squared gradient components respectively, with coefficients in front of the sum, such as (1 - (1 - 1 providing "bias correction" [36]. The variable
In Example 1.3, m (n+1) and m ml=+1)
(n+1)
(n+1) here is degenerate "momentum variable". with memory decaying infinitely fast.
m3
The following modification incorporates Nesterov's momentum into Adam This formulation
taken from Choi al. [14] (except here is inside the square root in the denominator).

---

Example 1,4 (NAdam with decoupled weight decay: Dozat [22]). The optimizer can be written in the form (1) with
(@(m)) ....,,,0))
1(0)
Bim1 Bimmaat)
(a+1)
31)
3m
(
(x+1)
(n+1)
m3
(x+1)
m2
+
where
mi mi
(a+1)
31
P1 go- 1
((
1 - 31
k=
m2
(a+1)
32
n
8/ 8
(VC
52+11
k=0
(n+1)
\0
my
m4 (m+1) VL(O("),
for some initial condition ( and where 0 & B1, B2 are momentum parameters, >> 0 is numerical stability parameter, 0 < is a weight decay parameter, and the squares and square roots are taken component-wiss
As final example, consider new optimizer called Lion (EvoLved Sign Momentum), which was recently discovered by an evolutionary search, and then verified to generalize better than AdamW on variety of tasks [13]. We consider generalized version of the Lion algorithm. Example 1.5 (Lion-KC; Chen al. [12]). The optimizer can be written in the form of (1) with
((")(()))
0()) 1--KKm (m (n-1)
(n+1))
+ m3 m(=+1)
(n+1)
m2
where
mi
(x+1) -(1 p2)
P1
P2 V ((((()))
2
02
k=l
m2 (n+1)
1 -
P1
V
(L((()))
P2
m3 1) = (m())
(3)
for some initial condition 0 (0), and where 0 & Pl, < 1 are Lion's momentum parameters, À >>> 0 a weight decay parameter, KC: gd + is some convex function, and VK is its subgradient. L
We choose the letter / rather than ,3 for Lion's momentum parameters because they are not precisely parameters controlling the speed of exponential decay in "momentum variables", explained in Section C. Ordinary Lion corresponds to K(x)) = ||ق||| and VK(x) = sign(x) in Example 1.5, where the sign function is understood component-wise We consider the generalized Lion-K algorithm because it covers a few known algorithms as special cases: see Table and Section 3.1 in Chen et al. [12]. In fact, it also includes Example 1.1 special case by taking AC(x=) || /2/ P1 P2. and = 0, but we will deal with that important specific example separately for clarity.
It is reasonable to expect that adding exponentially decaying memory to algorithm in such way as described above (for example, replacing the gradient with exponentially averaged past gradients) changes the optimization dynamics, thereby affecting the performance of the trained model. The technique we introduce identifies how the iteration evolution changes when memory is added. This technique starts with iteration having memory, and replaces it by memoryless iteration that approximates the original one, provided a correction term added. Specifically, we start with algorithm (I), and then construct corresponding new memoryless iteration:
(n+ 1) (m))
h i. (n)
(0)
dopends the whole history g(n)
(()
correction
Φ (n+1)
0 (n)
h (x)) (1m)))p (e)))
(4)
only depends on Ø (() (no memory)
3

---

where we slightly abuse notation and put
Fln) (0 ( =
F(n) (0))
(1)
n +
times
and where the function M (()( captures a correction due to the presence of memory. We then
prove an explicit bound on the approximation error ||0(*) - 0 f())
||. as a function of the learning rate h. Interpreting the correction term can sometimes generate predictions on whether memory helps or hurts generalization of first-order methods with momentum.
Our theory only relies on memory decaying sufficiently fast, not necessarily in the form of momentum variables, and thus covers all the examples listed above and many others, while also allowing for both full-batch and mini-batch training. Section 2 first presents a heuristic discussion of our proposed technique focusing on the simplest possible case for clarity: GD with momentum (Example 1.1). Then, Section 3 presents our main theoretical contribution, which we specialize and apply to all the listed examples in Sections C and D.
Depending on specific optimization algorithm considered, our general result can lead to different practical conclusions. As substantive application, Section 4 studies AdamW (Example 1.3) and Lion-K. (Example 1.5), and demonstrates that Lion does not suffer from the anti-regularization effect that AdamW's memory has, which predicts better generalization of (full-batch) Lion. Section (with details in Section E) discusses further implications of our main theoretical result: constructing modified equations, and identifying implicit regularization by noise in mini-batch training. Section is devoted to limitations and future directions.
Due to compute constraints, consider large-scale empirical testing of this theory out of scope of this paper. However, we provide a preliminary empirical illustration in Section J (with some details, compute resources and licenses in Section K).
1.1 Notation
We use standard notations for the Ep norm of vector ||1|| = (E,li))) the infinity-norm is defined as || = max./e/] pe]; finally, the norm without indices is by default Euclidean: ||o|| = ||0|| When we write u = (h)). where g(h) is some fixed function of h and un,h some sequence of vectors possibly depending on h, we mean that there is a constant C' not depending on h or n such that te & Ch))). We will contract repeating arguments when convenient, e. g. instead of ((n) (0 (f..... 9) we will write just ((n) (0). We will use notation L(-) for the loss and (-(-) for its gradient, h for the learning rate.
2 Building Intuition: Memory Regularizes GD with Momentum
We provide a heuristic explanation of our technique, considering the simplest algorithm with ex- ponentially decaying memory: heavy-ball momentum GD (Example 1.1). As explained above, would like to remove the dependence of the right-hand side in
0 g(++1)_ = (())
h
3
(L((())
(5)
k=
on the "past" iterates ((n-1) (00) leaving only the dependence on the "current" iterate ((x). Let us represent "past" iterates through the "current" one. First, write
g in = (nn) + h
3 3'VC(0((---)) (())
3 (V +
6=u
where the second equality relies exponential averaging replace historical iterates with ((n) influencing only higher-order terms. Similarly,
12 ( ((n-1) +
go ((
b=0

---

n-
((-1)) + h
8 VL(( + 0(h))
b=0
n-2
= (()) +
36
[ + 0(²2),
b=0
b=0
where the last equality follows by inserting the expression for ((n-1), Continue like this up to
0 k) (())
B
1= b=
where the k2 provides an estimate on the accumulation of error terms of order h²?
We have now represented all the historical iterates through the current one. Combining it with Taylor expansion around (n) in Equation (5), we obtain
( = =0(n) h
3k VC(O + (IV?
3 +
k=
b=
= = - h On
V(((())) n²2 (1 3)3
3[ on (1)
V L(O (
B
where (1) terms go to zero exponentially fast as n - 0c. Now using (()))) =
V\/2) obtain that heavy-ball momentum GD close ordinary GD (no momentum) with different step size and different loss, given by
h 1-3 Vī(0),
h3
e (++) (())
where [(0) (()) 2(1-B) VC
(6)
The term 2(1-3)= [O) that is added implicitly to the loss by the momentum can be interpreted as implicit regularization. Since usually taken to be close to one, the term strongly penalizes the squared norm of the gradient. There is empirical evidence that such penalization improves generalization [6, 59, 26]. In fact, this term (up to coefficients) can be interpreted as a first-order approximation of & sharpness [26], which suggests that it moves the trajectory towards "flatter" minima; this is often thought to improve generalization [25].
A much more fine-grained analysis of this algorithm is provided in [10] where, in particular, the
modified loss described to arbitrary precision rather than just to first order h.
General Theory: The Effect of Memory
The general form of an optimization algorithm with memory is given by Equation (1). The only property memory we use is that (uniformly in n) decays exponentially fast, as made precise by Assumption 3.1 below. Openness and convexity of the domain of optimization D, that is, where all (o(")) will be assumed to lie, are innocuous assumptions (e.g., Rd is open and convex); impose them to avoid technicalities with differentiation and Taylor expansion.
Assumption 3.1 (Memory Decay). Let D be an open convex domain in Rdd. Let o be a family functions D=+1 + Rd, two times continuously dif- ferentiable their respective domains, such that for any E Ezo, k1, f2 E n2), r,ú,j (I..
(F(") ..... o (0)) )
82 8 a0(n-ki k1) (0(o))s)))
|F(") 7-11
50! (nk))
7kr
where F(n) (F(")
F ((m))T and 7-1, Thi and nk families of positive reals (not depend-
ing on n.) satisfying
nes k?
Ta k2 00.
kp
5

---

3.1 Deriving the Memoryless Approximation
By Taylor expansion with the Lagrange remainder,
F((m) (f(n)
( F(()(( (0(n)
0 (()))
((n ) T OF(")
(0 (1)
(()))
00 n k)
0 p(1)
1 (g(m-hk) ((1)))
00 n k1 0g kz) (c) (5) -
2
h1 11.11
OF
= (0(n-k) -
-(())
(0 n1)
((1)) + 0
(8)
00(n
where Ç is some point on the segment between (0("),
) and (0( (0(")...,,))) (())): in the last step
we used Assumption 3.1, 0(n-k1)_ ((n) = (ki 11), and (nn O(a) (k2l).
Next, write
@(n-k) -0(n)
Σ (0 g(o+1))
n-1
Σ 8 smn-k
(0(
((0) =
Σ
F (g(m)
(())) + O(KP122
=
8
where in the last step we used F(*) (0(*)
0
(
0 ((n-s))) which fol-
lows from Taylor expansion and Assumption 3.1. Insert this into Equation (8) and use Assumption 3.1 again continue:
p(x)
(0(m)
((0)
F(") (p())
(()))
n
OF
(n)
n-1
h
(n k) (0(m)
0 (n))sT
Σ
(( ..... (()) +
00
We conclude that the original numerical iteration can be rewritten in the form (4), where the linear in h correction function is defined as M())
(M M
() with
OF(") (x)
M (0) = 00 n
(0)
(0)
The derivation of the memoryless iteration is now complete. Although not a proof yet, it is the first step towards the approximation bound constituting main theoretical result.
3.2 Approximation Bound
argument similar to the derivation in Section 3.1 can be made to obtain the following result.
Theorem 3.2 (Memoryless approximation: 1-step error bound). Under Assumption 3.1, there exists
discrete memoryless iteration (m)) oo
p= satisfying (4) with initial condition の0)) (()) correction
function defined Equation (9), and a constant C1 not depending on h, such that
(1+1)
+ +hF(m) (0
(0) ll < C,h..
sup n
The proof is available in Section F.
The importance of this one-step approximation result is that it allows to bound the global error between the memoryfull iteration ((n) and memoryless iteration (m) on finite time horizon.

---

Corollary 3.3 (Global error bound on finite "time" horizon). In the setting of Theorem 3.2, let (0(")) JnEZoo be the sequence of vectors generated by the iteration in Equation (1) with initial condition ((0)_ Let T 2 0 be a fixed "time" horizon. (The number of iterations considered is not T but [T/h].. Then there exists constant C22 depending on T but independent of h, such that
0 T0") II & C2h².
The proof is in Section G.
4 Application: the Effect of Memory on Adam W, Lion and Signum
We first study AdamW with memory by an application of Theorem 3.2 and Corollary 3.3. Neglecting coefficients decaying to zero exponentially fast, we have
VC(((m))
0 ( (1 Ah) h
(VL(O(m))) +M
A sign V((D(n))
where M (n)(0) is given by
h B1 - B1) - B2(1 - -12)
32(1 - B2)
8
(VIV + +V
(V 2 +) 1/2
(V + 3/2
Here I|-11z.e is the perturbed one-norm defined as || = can write this in the form of preconditioned gradient descent (with decoupled weight decay):
Σ + Taking e to zero, we
Vi(a!))
(n+1) = (1 - (1)g(()))
(VL(O
where
rescaled loss
2(0) = A T- Cb] -1( ( T-p. (IV + XV
is the modified loss. Assuming B2 > B1, we see that (+) is implicitly anti anti-penalized. By The- orem 1.1 in [66], full-batch AdamW converges to a KKT point of the constrained optimization min /// L()). If |10]|= & 1/X, then the norm VL(())l dominates the term CV e in absolute value, so the main effect of memory is anti- anti-penalizing the one-norm of the gradient. Thus, if weight decay is sufficiently small, memory anti-regularizes (large-butch) Adam W. Incidentally, by Lemma 3.8 in that work, 0 is KKT point of this optimization problem and only if the constraint is satisfied and (*) 0. This is generalization of the observation that the correction term is zero and only the point is stationary, true of simpler full-batch algorithms (for Adam with À = 0
follows from the above; for full-batch GD with momentum it is clear from (6)).
Consider now Lion-K (Example 1.5). Neglecting terms going to zero exponentially fast as n -> oc, the memoryless iteration is
( =(1-hA)0 - with (
+M (
(0) - -h 1- P2
P1 (
As mentioned above, ordinary Lion is recovered by setting K(x)) -||||||- This function is not differentiable, so let replace it with the smooth convex approximation || where is a small positive constant. The results of Section can be applied, and the memoryless iteration
(C(O()))
(n++) = (1 (1))(())
(IV +8) 1/2 + M (2) (0(0))
with M.n)( (0) h P1
P2 ((V,2 + +5) 3/2 V, [IVC()) AV -C(()))
7

---

This term is small as long as E is small. Therefore, better generalization of Lion number of tasks [13] may be partially attributed the fact that memory does not anti-regularize Lion. In addition. notice that the correction terms are exactly the same for Adam with 31 = B =: 3 and Lion with Pi = P2 3. Since Lion with P1 P2 is Signum [8], we provide a novel perspective on the similarity between Adam with B1 ~ 32 and Signum, a point discussed and verified empirically in [69].
5 Further Implications
5.1 Modified Equations
We have taken a very general algorithm (1) and converted it (under Assumption 3.1) to memoryless iteration (4) with O(h²) uniform enror bound on a finite time horizon (Corollary 3.3). Since this iteration has no memory, standard methods can be used to derive an ordinary differential equation (ODE) in the form i G2 (0) =: (0) + 2 whose continuous solution approximates this iteration and hence the initial algorithm (with the same approximation guarantee). Similarly to Section 2, the derivation is heuristic (although the approximation bound easily made rigorous) and proceeds as follows. Relating the iteration number n of a discrete iteration and the time point / nh on continuous trajectory, we would like the continuous trajectory to satisfy same one-step relation as the discrete iteration, up to O(h"):
(( + 1)h) (nh)
F())) (0(nh),.... -., ((nh)) + M ((() + 0(h))
In fact, we will ensure it true for nh replaced by any
0 h) 0(1) - ( 0()) + M ( (0(1)) +1.))
(10)
But, using a Taylor expansion. and recalling that finding the trajectory satisfying 0(t) G₂ (0(t),, hence (tt) (O(t))((()) we have
-22 0(1 + h) 0(1) + h((() - 00) 000(+(((()))) + 0()) + +G;00)++++((0
1²2
(0()))
+ 2
(t) + (o()t())) Gz(((t)) (G + O(h3).
2
In order to match (10), we need
G₂ (0) (F.) ().....))) 0),
G2( (m)) (0)/h+ (O)G())
So, apart from the correction term coming from memory, the ODE Ô ( (0) derived has another term
2 (O)G
2
arising from the fact that the algorithm is discrete.
For the example of full-batch heavy-ball momentum GD in Section 2, where ()) -(1 3) V (() (ignoring coefficients going to zero exponentially fast in n), this additional term is equal to (1 - - [2///4 providing additional implicit regularization. We recover the ODE derived by Kovachki and Stuart [37], Ghosh et al. [26]:
VL(0)
1
0
1 1-8
(1- 3)3
8

---

5.2 Mini-Batch Training
In specific cases, it is possible identify the additional implicit regularization that is introduced to the algorithm by noise, if mini-batch training is used as opposed to full-batch. Assume that the form of F(() (0(m)) (0)) is given by
Fl"( (
Σ g (n(nn)))(( (o(m-k)))
where the {g (+)) functions are uniformly bounded along with two derivatives, and is random permutation (O....,2) n) (chosen among all such permutations with equal probability). The interpretation is that a large number of mini-batche in epoch, and mini-batches are sampled randomly without replacement.
The correction term introduced by memory (9) is
n- 8 (x()=116)) (0).
M (0) = hB Σ V (
6=0
We can take the average E over all permutations æ (re-orderings of mini-batches). Deferring some details to Section E, the result is that for large n
B
E E[M ( (0)]/h
V ( 9())
(1 (1- 3)3
3
(( Vg) (n()) (((()))))))))))) -0)-
+ (1 - 3) B)
The second term can be interpreted implicit regularization by noise. For clarity, (11) is uniformly distributed random variable over {O....,,) so this expectation an average over mini-batch indices.
For example, take (0) V (k(k) (0) the kth minibatch loss. Then we obtained that "on average" mini-batch GD with momentum is given by the iteration like (6), except the modified loss has additional regularization term:
h8
h3 2(1 (1 - 3) (VV
2(0) L(0) +
2(1 - 3)2
regalarization by mini butch noise
6 Limitations and Future Directions
The approximation bounds in Section 3.2 are in terms of the learning rate h, which means that has to be sufficiently small for (our approximations and hence) the optimization trajectories to be close. This is a standard limitation in the literature. Fortunately, practically relevant learning rates are often small enough (especially mid-training. if learning rate decay schedule used). Additionally, there is a negliggiee effect of mini-bater noise on the picture we are describing in Section J; particular, Lion does not necessarily outperform Adam if batches are small [13]. We are able to characterize this effect using similar techniques, but this is out of scope of this article and is work progress.
Taking a broader view, one may question the effect (explicit or implicit) regularization on training progress and outcomes in deep learning. which is an intricate question not easily amenable to theoretical analysis [67, 1, 34]. Between 2023 and 2025, the mainstream paradigm in deep learning (especially large language models) is best described scaling-centric rather than generalization- centric [65] which decreased interest in implicit regularization. The main purpose of this work to introduce general framework for identifying correction terms, whether they are treated as implicit regularizers or not. In the future, it is likely possible to build on it to study implications for the training dynamics, including characterizing the properties of the loss landscape around the optimizer's trajectory. Additionally, it is reasonable to anticipate that because of limited high-quality data, overfitting is about to become widely important issue again, if not already [65, Section 7].
[62, 35].

---

Finally, we discuss some of the most popular optimizers in recent years, but other important algorithms like Shampoo [30, 58] or its versions are also amenable to this analysis, and the approximation results in Section 3.2 hold for them (assuming a typical choice of momentum schemes). However, interpreting the higher-order corrections is not trivial, and we leave that as additional future work.
Acknowledgments
We thank Boris Hanin for his comments. Cattanco gratefully acknowledges financial support from the National Science Foundation through DMS-221056 and SES-2241575. We acknowledge the Princeton Research Computing resources, coordinated by the Princeton Institute for Computational Science and Engineering (PICSciFE) and the Office of Information Technology's 's Research Computing.
References
[1] M. Andriushchenko, F. Croce, M. Müller, M. Hein, and N. Flammarion. A modern look at the relationship between sharpness and generalization. In Proceedings of the 40th Interna- tional Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 840-902. PMLR, 2023. URL https::: http///rrceedn...c./o////o mlr. press/v222/ andri andriushchenko23.. html.
[2] R. Anil, V. Gupta, T. Koren, and Y. Singer. Memory efficient adaptive opti- mization. In Advances in Neural Information Processing Systems, volume 32. 2019. URL https://papers wwwr.ps..c.pappr............. wwtppcppppeeeaeeeeeeeee forr_ffllew files www.s//eleeeeeeeeeeeeeaeeaaaaaee http//pape//////a///// 88150099902252221668777887766 wtwp://e27e00--tattttttoo .tml.
[3] S. Arora, N. Cohen, W. Hu, and Y. Luo. Implicit regularization deep matrix factorization. In Advances in Neural Information Processing Systems, volume 32, 2019. URL attps://proceediie www.iis...ppp..p. cc/paper fflles_ httppperfiieee/pppe///////////// httpp/pppp////////e/ee Doc Abstract. .html.
[4] S. Arora, Z. Li, and A. Panigrahi. Understanding gradient descent on the edge of stability deep learning. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 948-1024. PMLR, 2022.
URL https: : ttttps::/proceeeeeeeee httpp//rooeeen...eeee .mw.iiinnnnmmmm.....mmmm.mmmm..m mlr. www..presssveeee v262/ arora22a. html.
[5] A. Barakat and P. Bianchi. Convergence and dynamical behavior of the ADAM algorithm for nonconvex stochastic optimization. SIAM Journal on Optimization, 31(():244-274, 2021. doi: 10.1137/1MM1263445
[6] D. Barrett and B. Dherin. Implicit gradient regularization. In International Conference on Learning Representations, 2021. URL http://ppaaeeeeeeeeeeeooooodddda
[7] J. Bernstein and L. Newhouse. Old optimizer, new norm: An anthology. In OPT 2024: Optimization for Machine Learning.
[8] J. Bernstein, Y.-X. Wang, K. Azizzadenesheli, and A. Anandkumar. signSGD: Compressed optimisation for non-convex problems. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 560-569. PMLR, 10-15 Jul 2018. URL https:/ httpee///oocceeedeee mlr www.:meer./m///t/mtm.t.m wwwppreeeeveeeeee htt////000///ennneee
html.
[9] A. Betti, G. Ciravegna, M. Gori, S. Melacci, K. Mottin, and F. Precioso. A new perspective on optimizers: leveraging Moreau- Yosida approximation in gradient- based learning. Intelligenza Artificiale, 18(2):00-311, 2024.
[10] M. D. Cattaneo and B. Shigida. Modified loss of momentum gradient descent: Fine-grained analysis. arXiv preprint arXiv:2509.084. 2025.
[11] M. D. Cattaneo, J. M. Klusowski, and B. Shigida. On the implicit bias of Adam. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 5862-5906. PMLR, 2024. httss h h/ppr//eeoigg......//.e/.////.sp mlr. prwss/ v225///vvv/////e cattaneo24a. html.
10

---

[12] L. Chen, B. Liu, K. Liang, and Q. Liu. Lion secretly solves a constrained optimization: As Iyapunov predicts. In The Twelfth International Conference on Learning Representations, 2024. net/ htr///orumm//// iiw.ummmdddde4422222rr
[13] X. Chen, C. Liang D. Huang, E. Real, K. Wang, H. Pham, X. Dong, T. Luong, C.- J. Hsieh, Y. Lu, and Q V. Le. Symbolic discovery of optimization algorithms. In
Advances in Neural Information Processing Systems. volume 36, pages 49205-49233 2023. URL https: /
https://prroceedings nerrips. cc/ccc/ppppo httppppperleeeeeeeeeeeeppaa fileffile////eeee Saaperr_flesepppe//0033.... httpp/pppppp////////eee
ha3b=9926650f4477cc8877777338333 http://ccccaa111178884----ttatte Abstract. html.
[14] D. Choi, C. J. Shallue, Z. Nado, J. Lee, C. J. Maddison, and G. E. Dahl. On empirical comparisons of optimizers for deep learning. arXiv preprint arXiv:1910.0544 2020. URL https://arxiv http:aawwwvv....aaaaaaor.a aaa/abas///11 19900 05446.
[15] A. Chowdhery, S. Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, P. Barham, H. W. Chung, C. Sutton, S. Gehrmann, P. Schuh, K. Shi, S. Tsvyashchenko, J. Maynez, A. Rao, Barnes, Y. Tay. N. Shazeer, V. Prabhakaran, E. Reif, N. Du, B. Hutchinson, R. Pope, J. Braddbur.. J. Austin, M. Isard, G. Gur-Ari. P. Yin, T. Duke, A. Levskaya, S. Ghemawat, S. Dev, H. Michalewski, X. Garcia, V. Misra, K. Robinson, L. Fedus, D. Zhou, D. Ippolito, D. Luan, H. Lim, B. Zoph, A. Spiridonov, R. Sepassi, D. Dohan, S. Agrawal, M. Omernick, A. M. Dai, S. Pillai, M. Pellat, A. Lewkowyez, E. Moreira, R. Child, O. Polozov, K. Lee, Zhou, X. Wang, B. Saeta, M. Diaz, O. Firat, M. Catasta, J. Wei, K. Meier-Hellstern, D. Eck, J. Dean, Petrov, and N. Fiedel. PaLM:: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240): 1-11:, 2023. URL http:// / //lr///mr../// org/ httg/apers///eeeooo stteerrs/22222/ 224/22-1144 html.
[16] J. M. Cohen, B. Ghorbani, S. Krishnan, N. Agarwal, S. Medapati, M. Badura, D. Suo, D. Car- doze, Z. Nado, G. E. Dahl, al. Adaptive gradient methods the edge of stability. arXiv 2022.
preprint arXi
[17] E. M. Compagnoni, T. Liu, R. Islamov, F. N. Proske, A. Orvieto, and A. Lucchi. Adaptive methods through the lens of SDEs: Theoretical insights on the role of noise. In The Thirteenth International Conference on Learning Representations, 2025. URL https: //pp///veeeee.....///m net/forum d=ww3CLRhF1v.
[18] Z. Dai, Yang, Y. Yang, G. Carbonell, Q. V. Le, and R. Salakhutdinov. Transformer- XL: Attentive language models beyond a fixed-length context. In Anmual Meeting of the Association for Computational Linguistics, 2019. URL https://ap. www.stiisshollle.... Ttg/CorppsII::577 57759363.
[19] A. Damian, T. Ma, and J. D. Lee. Label noise SGD provably prefers flat global mini- mizers. In Advances Neural Information Processing Systems, volume 34, pages 27449- 27461, 2021. URL https: httl::ttttt///ooooeeeee //poceedd/nc wtw.:eeeeediinne..nnneeeeeeeeeee nwwrips. www..pp..ccpppprrrreeeee.
[20] A. Damian, E. Nichani, and J. D. Lee. Self-stabilization: The implicit bias of gradient descent at the edge of stability. In The Eleventh International Conference on Learning Representations, 2023. URL https: openrevieeeeeeeee/ net net/ffrumm? hatrrummm?ddnKHHHA5......
[21] DeepSeek-ALl -II, A. Liu, B. Feng, B. Xue, B. Wang, B. Wu, C. Lu, C. ZZhao, C. Deng. C. Zhang, C. Ruan, D. Dai, D. Guo, D. Yang, D. Chen, D. Ji, F. Li, F. Lin, F. Dai, F. Luo, G. Hao, G. Chen,
G. Li, H. Zhang, H. Bao, H. Xu, H. Wang, H. Zhang, H. Ding, H. Xin, H. Gao, H. Li, H. Qu,
J. L. Cai, J. Liang, J. Guo, Ni, J. Li, Wang, Chen, J. Chen, J. Yuan, J. Qiu, J. Li, Song.
K. Dong, K. Hu, K. Gao, K. Guan, K. Huang. K. Yu, L. Wang. L. Zhang, L. Xu, L. Xia, L. Zhao,
L. Wang, L. Zhang, M. Li, M. Wang, M. Zhang, M. Zhang, M. Tang, M. Li. N. Tian, Huang, P. Wang. P. Zhang, Q. Wang, Q. Zhu, Q. Chen. Q. Du, R. J. Chen, R. L. Jin, R. Ge, R. Zhang, R. Pan, R. Wang, R. Xu, R. Zhang, R. Chen, S. S. Li, Lu, Zhou, Chen, Wu, S. Ye, S. Ye, S. Ma, S. Wang, S. Zhou, S. Yu, S. Zhou, S. Pan, T. Wang, T. Yun, T. Pei, T. Sun, W. L. Xiao, W. Zeng, W. Zhao, W. An, Liu, W. Liang, W. Gao, W. Yu, W. Zhang, X. Q Li, X. Jin, X. Wang, X. Bi, X. Liu, X. Wang, X. Shen, X. Chen, X. Zhang, X. Chen, X. Nie, X. Sun, X. Wang, X. Cheng, X. Liu, X. Xie, X. Liu, X. Yu, X. Song, X. Shan, X. Zhou, X. Yang, X. Li,
X. Su, X. Lin, Y. K. Li, Y. Q. Wang. Y. X. Wei, Y. X. Zhu, Y. Zhang, Y. Xu, Y. Xu, Y. Huang,
11

---

Y. Li, Y. Zhao, Y. Sun, Y. Li, Y. Wang, Y. Yu, Y. Zheng, Y. Zhang, Y. Shi, Y. Xiong, Y. He, Y. Tang, Y. Piao, Y. Wang, Y. Tan, Y. Ma, Y. Liu, Y. Guo, Y. Wu, Y. Ou, Y. Zhu, Y. Wang.
Y. Gong, Y. Zou, Y. He, Y. Zha, Y. Xiong, Y. Ma, Y. Yan, Y. Luo, Y. You, Y. Liu, Y. Zhou,
Z. F. Wu, Z. Z. Ren, Z. Ren, Z. Sha, Z. Fu, 7. Xu, Z. Huang, Z. Zhang, Z. Xie, Z. Zhang,
Z. Hao, Z. Gou, Z. Ma, Z. Yan, Z. Shao, Z. Xu, Z. Wu, Z. Zhang, Z. Li, Z. Gu, Z. Zhu, Z. Liu,
Z. Li, Z. Xie, Z. Song, Z. Gao, and Z. Pan. Deepseek-v3 technical report. arXiv preprint
arXiv:2412. 2024. URL https: //arxiv.a.i/////a org/ abs//412.111..
[22] T. Dozat. Incorporating Nesterov momentum into Adam. ICLR Workshops, 2016. URL
[23] C. Ernst Hairer and G. Wanner. Geometric numerical integration. Springer- Verlag, Berlin, 2 edition, 2006. ISBN 3-540-30663-3.
[24] M. Farazmand. Multiscale analysis of accelerated gradient methods. SIAM Journal on Opti- mization, (0(3))0037-23333333 2020. doi: 10.1137/18M12039997
[25] Foret, A. Kleiner, H. Mobahi, and B. Neyshabur. Sharpness-aware minimization for efficiently improving generalization. In International Conference on Learning Representations, 2021. URL httptttt//peeeeeeiiiie
[26] A. Ghosh, H. Lyu, X. Zhang, and R. Wang. Implicit regularization in heavy-ball momentum accelerated stochastic gradient descent. In The Eleventh International Conference on Learning Representations, 2023. URL https:/ / http///peeeeeeeeeeeeeeeeeee wew..wwww.. net/ f formmrrmmi BidziidBttZttyZy
[27] A. Grattafiori, A. Dubey, A. Jauhri, A. Pandey, A. Kadian, A. Al-Dahle, A. Letman, A. Mathur, A. Schelten, A. Vaughan, A. Yang. A. Fan, A. Goyal, A. Hartshorn, A. Yang, A. Mitra, A. Sravankumar, A. Korenev, A. Hinsvark, A. Rao, A. Zhang, A. Rodriguez, A. Gregerson, A. Spatarr, B. Roziere, B. Biron, B. Tang, B. Chern, C. Caucheteux, C. Nayak, C. Bi, C. Marra, C. C.McConnell, C. Keller, C. Touret, C. Wu, C. Wong, C. C. Ferrer, C. Nikolaidis, D. Allonsius, D. Song, D. Pintz, D. Livshits, D. Wyatt, D. Esiobu, D. Choudhary, D. Mahajan, D. Garcia- Olano, D. Perino, D. Hupkes, E. Lakomkin, E. AlBadawy, E. Lobanova, E. Dinan, E. M. Smith, Radenovic, F. Guzmán, Zhang, G. Synnaeve. G. Lee, G. L. Anderson, G. Thattai, G. Nail, G. Mialon, G. Pang. G. Cucurell, H. Nguyen, H. Korevaar H. Xu, H. Touvron, I. Zarov, I. A. Ibarra, Kloumann, I. Misra, I. Evtimov, J. Zhang, J. Copet, J. Lee, J. Geffert, J. Vranes, Park, J. Mahadeokar, J. Shah, J. van der Linde, J. Billock, J. Hong. J. Lee, J. Fu, J. Chi, J. Huang, J. Liu, Wang, J. Yu, J. Bitton, J. Spisak, J. Park, J. Rocca, Johnstun, J. Saxe, J. Jia, K. V. Alwala, K. Prasad, K. Upasani, K. Plawiak, K. Li, K. Heafield, K. Stone, K. El-Arini, K. Iyer, K. Malik, K. Chiu, K. Bhalla, K. Lakhotia, L. Rantala- Yeary. L. van der Maaten, L. Chen, L. Tan, L. Jenkins, L. Martin, L. Madaan, L. Malo, L. Blecher, L. Landzaat, L. de Oliveira, M. Muzzi, M. Pasupuleti, M. Singh, M. Paluri, M. Kardas, M. Tsimpoukelli, M. Oldham, M. Rita, M. Pavlova, M. Kambadur, M. Lewis, M. Si, M. K. Singh, M. Hassan, N. Goyal, N. Torabi, N. Bashlykov, N. Bogoychev, N. Chatterji, N. Zhang. O. Duchenne, O. Çelebi, P. Alrassy, P. Zhang. P. Li, P. Vasic, P. Weng, P. Bhargava, P. Dubal, P. Krishnan, P. S. Koura, P. Xu, Q. He, Q. Dong, R. Srinivasan, R. Ganapathy, R. Calderer, R. S. Cabral, R. Stojnic, R. Raileanu, R. Maheswari, R. Girdhar, R. Patel, R. Sauvestre, R. Polidoro, R. Sumbaly, R. Taylor, R. Silva, R. Hou, R. Wang, S. Hosseini, S. Chennabasappa, S. Singh, S. Bell, S. S. Kim, S. Edunov, S. Nie, S. Narang, S. Raparthy, S. Shen, S. Wan, S. Bhosale, S. Zhang, S. Vandenhende, S. Batra, S. Whitman, S. Sootla, S. Collot, S. Gururangan, S. Borodinsky, T. Herman, T. Fowler, T. Sheasha, T. Georgiou, T. Scialom, T. Speckbacher, T. Mihaylov, T. Xiao, U. Karn, V. Goswami, V. Gupta, V. Ramanathan, V. Kerkez, V. Gonguet, V. Do, V. Vogeti, V. Albiero, V. Petrovic, W. Chu, W. Xiong, W. Fu, W. Meers, X. Martinet, X. Wang. X. Wang, X. E. Tan, X. Xia, X. Xie, X. Jia, X. Wang. Y. Goldschlag, Y. Gaur, Y. Babaei, Y. Wen, Y. Song, Y. Zhang, Y. Li, Y. Mao, Z. D. Coudert, Z. Yan, Z. Chen, Z. Papakipos, A. Singh, A. Srivastava, A. Jain, A. Kelsey, A. Shajnfeld. A. Gangidi, A. Victoria, A. Goldstand, Menon, A. Sharma, A. Boesenberg, A. Baevski, A. Feinstein, A. Kallet, A. Sangani, A. Teo, A. Yunus, A. Lupu, A. Alvarado, A. Caples, A. Gu, A. Ho, A. Poulton, A. Ryan, A. Ramchandani, A. Dong, A. Franco, A. Goyal, A. Saraf, A. Chowdhury, A. Gabriel, A. Bharambe, A. Eisenman, A. Yazdan, B. James, B. Maurer, B. Leonhardi, B. Huang, B. Loyd, B. D. Paola, B. Paranjape, B. Liu, B. Wu, B. Ni, B. Hancock, B. Wasti, B. Spence, B. Stojkovic, B. Gamido, B. Montalvo, C. Parker, C. Burton, C. Mejia, C. Liu, C. Wang, C. Kim, C. Zhou, C. Hu, C.-H. Chu, C. Cai,
12

---

C. Tindal, C. Feichtenhofer, C. Gao, D. Civin, D. Beaty, D. Kreymer, D. Li, D. Adkins. D. Xu, D. Testuggine, D. David, D. Parikh, D. Liskovich, D. Foss, D. Wang. D. Le, D. Holland, E. Dowling, F. Jamil, E. Montgomery, F. Presani, E. Hahn, E. Wood, E.-T. Le, E. Brinkman, E. Arcaute, E. Dunbar, E. Smothers, F. Sun, Kreuk, Tian, F. Kokkinos,
Ozgenel,
R. Caggioni, F. Kanayet, F. Seide, G. M. Florez, G. Schwarz, G. Badeer, G. Swee, G. Halpern, G. Herman, G. Sizov, Guangyi, Zhang. G. Lakshminarayanan, H. Inan, H. Shojanazeri, H. Zou, H. Wang, H. Zha, H. Habecb, H. Rudolph, H. Suk, H. Aspegren, H. Goldman, H. Zhan, I. Damlaj, I. Molybog. I. Tufanov, I. Leontiadis, I.-E. Veliche, I. Gat, J. Weissman, J. Geboski, J. Kohli, J. Lam, J. Asher, J.-B. Gaya, J. Marcus, J. Tang. J. Chan, J. Zhen, J. Reizenstein, J. Teboul, J. Zhong, J. Jin, J. Yang. J. Cummings, J. Carvill, J. Shepard. J. McPhie, J. Torres,
J. Ginsburg, J. Wang, K. Wu, K. H. U. K. Saxena, K. Khandelwal, K. Zand, K. Matosich, K. Veeraraghavan, K. Michelena, K. Li, K. Jagadeesh, K. Huang, K. Chawla, K. Huang, L.. Chen, I.. Garg. L., A, I.. Silva, I.. Bell, I.. Zhang, I.. Guo, L. Yu, I. Moshkovich, L. Wehrstedt, M. Khabsa, M. Avalani, M. Bhatt, M. Mankus, M. Hasson, M. Lennie, M. Reso, M. Groshev, M. Naumov, M. Lathi, M. Keneally, M. Liu, M. L.. Seltzer, M. Valko, M. Restrepo, M. Patel, M. Vyatskov, M. Samvelyan, M. Clark, M. Macey, M. Wang, M. J. Hermoso, M. Metanat, M. Rastegari, M. Bansal, N. Santhanam, N. Parks, N. White, N. Bawa, N. Singhal, N. Egebo, N. Usunier, N. Mehta, N. P. Laptev, N. Dong, N. Cheng, O. Chernoguz, O. Hart, O. Salpekar, O. Kalinli, Kent, P. Parekh, P. Saab, Balaji. P. Rittner, P. Bontrager, Roux, Dollar, P. Zvyagina, P. Ratanchandani, P. Yuvraj Q. Liang. R. Alao, R. Rodriguez, R. Ayub, R. Murthy, R. Nayani, R. Mitra, R. Parthasarathy, R. Li, R. Hogan, R. Battey, R. Wang. R. Howes, R. Rinott, S. Mehta, S. Siby, S. J. Bondu, S. Datta, S. Chugh, S. Hunt, S. Dhillon, S. Sidorov, S. Pan, Mahajan. S. Verma, Yamamoto, S. Ramaswamy, S. Lindsay, Lindsay, S. Feng. S. Lin, S. C. Zha, S. Patil, S. Shankar, S. Zhang, S. Zhang, S. Wang, S. Agarwal, S. Sajuyighe, S. Chintala, S. Max. S. Chen, S. Kehoe, S. Satterfield, Govindaprasad, S. Gupta, S. Deng, S. Cho. S. Virk, S. Subramanian, S. Choudhury, S. Goldman, T. Remez, T. Glaser, T. Best, T. Koehler, T. Robinson, T. Li, T. Zhang, T. Matthews, T. Chou, T. Shaked, V. Vontimitta, V. Ajayi, V. Montanez, V. Mohan, V. S. Kumar, V. Mangla, V. Ionescu, V. Poenaru, V. T. Mihailescu, V. Ivanov, W. Li, W. Wang, W. Jiang, W. Bouaziz, W. Constable, X. Tang, X. Wu, X. Wang, X. Wu, X. Gao, Y. Kleinman, Y. Chen, Y. Hu, Y. Jia, Y. Qi, Y. Li, Y. Zhang, Y. Zhang. Y. Adi, Y. Nam, Yu, Wang. Y. Zhao, Y. Hao, Y. Qian, Y. Li, Y. He, Z. Rait, Z. Veti,o, Z. Rosnbrick, Z. Wen, Z. Yang, Z. Zhao, and Z. Ma. The Llama 3 herd of models. arXiv preprint ar arxiv:2407.22 2173, 2024. URL https: //arxiv.. org/ aaaaab//2200 21783.
[28] S. Gunasekar, B. E. Woodworth, S. Bhojanapalli, B. Neyshabur, and N. Sre- bro. Implicit regularization in matrix factorization. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Ad- vances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL
cwtrris..c/papppee wwce/appr_fiiiee peperrfiles files/ http///appp///111/1 aubstract.htm
[29] S. Gunasekar, J. Lee, D. Soudry, and N. Srebro. Characterizing implicit bias in terms of optimization geometry. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1832-1841, PMLR, 2018. URL https: // http///ppoeenn....///////// imm.eedddiinmm........m.mm.mm.mm .pres//e////eee taress/v80.. guwaseaaaaaaaaaa.... httml..........m............
[30] V. Gupta, T. Koren, and Y. Singer. Shampoo: Preconditioned stochastic tensor optimization. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1842-1850. PMLR, 10-15 Jul 2018. URL https:/ httpss///ocoeeedeegpe mlr, press/v80 gggggppp1laa.... html.
[31] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and patlern recognition, pages 770- 778, 2016.
[32] Z. Ji and M. Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.0 1803.07300, 2018. URL htttss://artiti org/abs// aa//a/bss//00/ /803. .03300.
[33] Z. and M. Telgarsky. The implicit bias of gradient descent on nonseparable data. In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1772-1798. PMLR, 2019. URL htt.httts://poceeeiiie mlr. wwwppeeessse. /a19a.ji9....///// html.
13

---

[34] Y. Jiang", B. Neyshabur*, H. Mobahi, D. Krishnan, and S. Bengio. Fantastic generalization measures and where to find them. In International Conference on Learning Representations. 2020. URL https::////.. htttps://ppenreeeeeee http///ppppeeeeeeee/e/e/// http:////papreeeeee//ee///aaaaa/
[35] K. Kim. S. Kotha, P. Liang. and T. Hashimoto. Pre-training under infinite compute, 2025. URL
https://arxii org/ abs/2509. 14786.
[36] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprini arXiv:1412.6980, 2017. URL
http:///axxxv..oo.aaaa/ hatp:/111....000 6980.
[37] N. B. Kovachki and A. M. Stuart. Continuous time analysis of momentum methods. Journal of Machine Learning Research, 22(17):1-40, 2021. URL http::/jmmr..... http://jiinoorro.oeeeeeee prg/papers/v22/ 19 199-66.62 html.
[38] A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images, 2009.
[39] A. Krizhevsky, L. Sutskever, and G. E. Hinton. Imagenet classification with deep con- volutional neural networks. In Advances in Neural Information Processing Systems, vol- ume 25, 2012. URL https://ppooceedings neurips cc/ wwcppaper_ffiiee www.ffillespppeeeee /2112////p///211// htab///996020b666666646666626862 Abstre4-bbbbbbtaat...... .attracct.tmm.......
[40] F. Kunstner, J. Chen, J. W. Lavington, and M. Schmidt. Noise is not the main factor behind the gap between sgd and adam on transformers, but sign descent might be. arXiv preprint 13960.
arXiv:2304. 13960, 2023. URL httpttps:/aaxiv.or///oo
[41] F. Kunstner, J. Chen, J. W. Lavington, and M. Schmidt, Noise not the main factor behind the gap between SGD and Adam on Transformers, but sign descent might be. In The Eleventh International Conference on Learning Representations, 2023. URL https: /ppprreveeeee.eee////ee net/forum? 1d=a65YK0cql88g.
[42] Q. Li, C. Tai, and W. E. Stochastic modified equations and adaptive stochastic gradient algorithms. In Proceedings of the 34th International Conference on Machine Learning, vol- ume 70 of Proceedings of Machine Learning Research, pages 2101-2110. PMLR, 2017. URL attps://proceedingg mlr pwwps////elii1/// html.
[43] Y. Li, C. Wei, and T. Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. In Advances in Neural Information Processing Systems, volume 32, 2019. URL
wttpc//pppp..feeepeeeeeeeeeeeeee wwwerips.cc/paapeeee wwt.f//pppeeeeee..././ Abstracctdd.b.ttt............... html.
[44] Z. Li, T. Wang, and Arora. What happens after SGD reaches zero loss? -a mathematical framework. In International Conference on Learning Representations, 2022. URL https:
/ //openreview, net/forummidssiCC443
[45] L. Liu, X. Liu, J. Gao, W. Chen, and J. Han. Understanding the difficulty of training Trans- formers. In Proceedings of the 2020 Conference on Empirical Methods Natural Language Processing (EMNLP), pages 5747-5763, 2020. doi: 2020 emnlp-main. 463/
mm...-mainn.....6 URL
https://aclanthhlogg
[46] I. Loshchilov and F. Hutter. Decoupled weight decay regularization. In International Con- ference on Learning Representations, 2019. URL https://openrevien www.eeww.ee/ofooeeeeeeeeee meet/frrrm?dd 8kg6RicqY7.
[47] C. Ma, L. Wu, and W. E. A qualitative study of the dynamic behavior for adaptive gradient algo- rithms. In Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, volume 145 of Proceedings of Machine Learning Research, pages 671-692. PMLR, 2022. URL https: http:::///ccceeeeeeeeeme mlr. www.mmrrr.......em.mmmmmmm.eee 1/5l//145//// ma24ammm22....mmm
ptt..per///////222222 html.
[48] S. Malladi, K. Lyu, A. Panigrahi, and S. Arora. On the SDEs and scaling rules for adaptive gradient algorithms. In Advances in Neural Information Processing Systems, volume 35, pages 7697-7711, 2022. URL httpppppp//prccceeiigggeeeeeee/ neurips cwwpaper.c.....ee.ee httpppperrflllppppppppaee html.
2022/hasha http///22cc1211 202p///ea/22ccr00000ee0002222000
14

---

[49] S. Merity, C. Xiong, J. Bradbury, and R. Socher. Pointer sentinel mixture models. In Inter- national Conference on Learning Representations. 2017. URL http:://pppeeerriiir net/ forum? Barum?id-Byy777 722dxe.
[50] T. Miyagawa. Toward equation of motion for deep neural networks: Continuous- time gradient descent and discretization error analysis. In Advances in Neu- ral Information Processing Systems, volume 35, pages 37778-37791, 2022. http:://proceeding.nenrrrt cc wwwpppppr...e (G5902222211811ccc07771117777000
URL
www.f//ppppeee//22/.... Conettt-oooeeeeeeeee html.
[51] M. S. Nacson, Lee, S. Gunasekar, H. P. Savarese, N. Srebro, and D. Soudry. Convergence of gradient descent on separable data. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 3420-3428, PMLR, 2019. URL https: //pp://///ocedggs... mlr. press/v89/ http///////nannnbbba/ html.
[52] M. S. Nacson, N. Srebro, and D. Soudry. Stochastic gradient descent separable data: Exact convergence with a fixed learning rate. In Proceedings of the Twenty-Secom -Secon- International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 3051-3059, PMIR, 2019. URL https: https:s//ppoceednggg mmlr wwt///////n91a..../// html.
[53] Y. Nesterov. A method for solving the convex programming problem with convergence rate of ) In Dokl. Akad. Nauk SSSR, volume 269, pages 543-547, 1983.
[54] B. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964. ISSN 0041-5553. doi: sec.aa/ee/arttaaaaa///////56ssss com/science/ http://ioncc/aticceeppippeee
URL http://wcieeeeeeee.....
[55] Q. Qian and X. Qian. The implicit bias of AdaGrad separable data. In Advances in Neural In- formation Processing Systems, volume 32, 2019, URL paper_file fiwes/ html.
neurips cc/
[56] M. Rosca, Y. Wu, C. Qin, and B. Dherin. On continuous time model of gradient descent dynamics and instability in deep learning. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL htttttps:///ppnre//eee http////ppeeeiiieeeeeeeeeeeeeeee
[57] N. Shazeer and M. Stern. Adafactor: Adaptive learning rates with sublinear memory cost. In Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 4596-4604. PMLR, 2018. URL https: //proceedings eig.e mlr. press/v80, ppess//880/haaeer118..
swwzeer18a..e.. html.
[58] H.J. M. Shi, T.-H. Lee, S. Iwasaki, J. Gallego-Posada, 7. Li, K. Rangadurai, D. Mudigere, and M. Rabbat. distributed data tarallarlllel pytorch implementation of the distributed Shampoo optimizer for training neural networks at-scale. arXiv preprint arXiv:2309.06-997 202., URL /stps://arxxe org/ 2309.. 06497.
[59] S. L. Smith, B. Dherin, D. Barrett, and S. De. On the origin of implicit regularization in stochastic gradient descent. In International Conference on Learning Representations, 2021. URL httts::/ wew.eewwweeeeeeeeeeeeeeeeeeeee wwttteeetmtiddaeeeoeeoo oor.outiddrr...rrooff......
[60] D. Soudry, E. Hoffer, and N. Srebro. The implicit bias of gradient descent on separable data. In International Conference on Learning Representations, 2018. URL https://openrevial net/forum?id<rqq/nee
[61] Tieleman, G. Hinton, et al. Lecture 6.5-rmsprop: Divide the gradient by running av- erage of its recent magnitude. COURSERA: Neurul nelworks for machine learning, 4(2): 26-31, 2012, URL. https:://// hppp:///www. cs. toronto. edu/~ti httt://sjjeeaeccece///aaaee//eee slides lec6, .df..
15

---

[62] P. Villalobos, A. Ho, J. Sevilla, T. Besiroglu, L. Heim, and M. Hobbhahn. Position: Will we run out of data? limits of LLM scaling based on guman-ggnerated data. In Forty-first International Conference Machine Learning, 2024. URL https::::: htttps://openrvieeett net/ forum?ideVizegDajy..
[63] B. Wang. Q. Meng, H. Zhang, R. Sun, W. Chen, Z.-M. Ma, and T.-Y. Liu. Does momentum change the implicit regularization separable data? In Ad- vances in Neural Information Processing Systems, volume 35, pages 26764-26776. 2022. URL https: https://ppooceeddings..to mewp:oceeeedingg..euiippppp.pppp cctpspprrcppppppppppppppepp fillssfilee///eeeeeeee www.ss/aaeeeereeeeee 2088602222. wwwsraattCoonfeeeeeeeeeeeeeeeeee
pttppppppp///aaaeeeeeee html.
[64] K. Wen, T. Ma, and Z. Li. How does sharpness-aware minimization minimizes sharpness? In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022. URL
[65] L. Xiao. Rethinking conventional wisdom in machine learning: From generalization to scaling. arXiv preprint urXiv:2409. 15156, 2024.
[66] Xie and Z. Li. Implicit bias of AdamW: -nom constrained optimization. In R. Salakhut- dinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, edi- tors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages
PMLR, 2024. URL
mlr ppwpp//22//////pp http///22//xxeeeeeee xie24e..e..eeeeeo... html.
[67] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprinl 1Xiv::611.003333 2016.
[68] Zhang. S. Karimireddy, A. Veit, S. Kim, S. Reddi, S. Kumar, and S. Sra. Why are adaptive methods good for attention models? In Advances in Neural Information P Processing Systems, ptt.//digeeeee..eeeooee//.o...ee neurips cttssper///p////c 0a0 html.
volume 33, pages 15383-15393 2020. URL https: httptttttptpteeeeeeeeeeeeeeeeeee 2020/
[69] R. Zhao, D. Morwani, D. Brandffobrrnner N. Vyas, and S. M. Kakade. Deconstructing what makes a good optimizer for autoregressive language models. In The Thirteenth International Conference on Learning Representations, 2025, URL https://openreeeeeee h/tprr/viee/e/eeeee////e www.:neetfrruou id=2feso8ceqr.
16

---

A Related Literature
Approximating memoryful iteration with memoryless is closely connected with the method of modified equations (sometimes called backward error analysis), where a discrete algorithm like (1) is approximated by a continuous solution of ordinary differential equation stochastic differential equation. Typically, this method can only be applied to an algorithm with no memory, in a possibly enlarged phase space as opposed to RR for example, heavy-ball momentum GD has no memory
when viewed as a discrete iteration (e(*), m (x) in IR2",, where m()) is the "momentum variable". The general technique introduced in this paper can be used to derive a memoryless discrete iteration which can then be approximated by continuous trajectory. Background on the method of modified equations can be found in Ernst Hairer and Wanner [23], Li et al. [42].
Works deriving modified equations for (S)GD with or without momentum include Barrett and Dherin [6]. Smith et al. [59], Ghosh et al. [26]. Farazmand [24], Kovachki and Stuart [37], Miyagawa [50], Rosca et al. [56], Li et al. [42]. In particular, Ghosh al. [26] identified that momentum strongly regularizes the loss function in the case of GD, though their error bounds both have different focus (continuous approximation rather than discrete one), and follow a different approach which appears hard to generalize to other algorithms. Our approach works for a wide class of algorithms. and we recover their main results Section 5. Works approximating adaptive methods with continuous trajectories include Ma et al. [47], Malladi et al. [48], Barakat and Bianchi [5], Compagnoni et al. [17]. More recently, Cattaneo et al. [11] studied the special case of Adam RMSProp. We built on this work to conduct empirical evaluations. Their focus is not on memory but on continuous approximations; in particular, they do not have approximation bounds between two discrete iterations like we do. In addition, their arguments are highly specialized to Adam, and they do not incorporate weight decay. Although we also discuss Adam (with weight decay) extensively, it is only because of its importance in practice, and our results cover a much broader class of optimizers.
This paper is also connected to the strand of the literature studying the implicit bias of optimization algorithms. For example, Xie and Li [66] and Chen et al. [12] prove that weight decay causes Adam and Lion to solve an -orm constrained optimization problem. that, they behave asymptotically like (normalized) steepest descent with respect to -nomm. Bernstein and Newhouse [7] also view Adam and Lion as smoothed-out versions of steepest descent. This perspective is connected to the Moreau- Moreau-Yosida approximation of the loss function [9]: the latter work provides a concrete way to write down popular optimizers (including SGD with momentum, RMSProp and Adam) as a sequence of optimization problems. In addition, large body of work is devoted to the bias of optimization algorithms towards the direction of the max- max--magiin vector [60, 51, 52, 55, 63, 29, 32, 33]. Similarly,
Damian et al. [19]. Li et al. [44], Arora et al. [4]. Wen et al. [64], Damian et al. [20] explore
the sharpness of regions SGD converges to. Gunasekar et al. [28], Arora et al. [3] study implicit
regularization in matrix factorization. Li et al. [43] prove in certain setting that larger learning rate leads to better generalization.
B Broader Impacts
This paper presents general framework for contrasting certain properties of optimization algorithms commonly used for training neural networks, and thus this work can lead to societal consequences as common of deep learning.
C Special Case: (()) as a Function of "Momentum Variables"'
In the examples listed in the introduction, F(n) satisfies more specific form that can be used to give more primitive conditions for Assumption 3.1. The following assumption, which is a special case of Assumption 3.1 by Lemma H.l, may look bit technical but allows for simpler calculation of correction terms.
Assumption C.1 (Special case of Assumption 3.1: F(1) is a function of "momentum variables"). Let {g) (o(")// H be two times continuously differentiable functions D + Rd uniformly bounded along (x+1) with two derivatives. Let {Be) be fixed reals in [0, 1), and (b( Jt=1 be L bounded nonnegative
17

---

((+t1) by X. sequences of reals (for n E Ezo). Assume the function F(1) has the form
Fln) ()) ) == (m (a+1)
(mt1))
..... m
a
with m (n+1) b( 1)
p (n- k) (g(n-b)) E M,
(11)
where M is a bounded open region in E and 2 (( mL): M + Ed is fixed two times continuously differentiable function, uniformly bounded along with two derivatives. In the full-batch case, 9 9r not allowed to depend on
For instance, in the case of AdamW (Example 1.3), Assumption C.1 applies with L =3 3,
91 (0) VL(0):
92(0) (VL(O))² 9g(0) 0,
((+1)
1 B1
- b1 = =1 B1,
- 377
02 (x+1)
1 B2
- b2 = B2,
$2 +
b/ (x+1) = by X, B3 =.
In the case of Lion-K (Example 1.5), the assumption applies with L = 3.
(0) = -v)(O), (2( = -V)( (3(0) = 0,
B1 p2, $2 0, 83 0,
(m+1) = b (1 P2) P1
6% (n+1) = b2 = 1 P1 P2
P2
We used the letter p when defining the Lion iteration avoid confusion with the in the definition of "momentum variables".
Specializing to the setup of Assumption C.I. and for any E Z
F()) =
(g
gi
(o))) where g (a+1) (0) == 6, (n+1)
Σi g (n-b)
(0).
and
OF!") 00 k-k 2)
11+1) gl Fmgi
00,
(gi
(n+1) Ir. .......99
(n+1) (0) v (n (n-k) (n~k)
Therefore, in this special case, the correction term in the memoryless iteration (4) is given by, for r = d
M (0) h
b
(n+1) 0
(g)
(n+1)
(0) (0).....
91
(n+1)
(0)) x
8=1 Omga
k)
0)
Σ
(
(a+1)
(0), (0),....g
91 (0))
(s+1)
(())
Den
In the full-batch case g
(n) (0) = (0), this can be simplified further. Let us assume
(x+1) be-
n-000
where by is constant in n. Then g; (n+1) (0) also become constant in n: specifically, they settle to
()) 6e(1 Bz) - (0). Lemma H.2 then implies that the iteration becomes close to
(n+1) = (n)) @ (Q (O""),........ (0((()) M (m) (0))
with
18

---

04, (1 Be)² Omps
b
()
(g)
(0()) (g, ) 9r. (((
These formulae admittedly look complicated, but we can easily plug in the definitions and calculate correction terms for all examples with little additional algebra. We list these terms in Section D.
D Details for Examples: Correction Terms
For GD with momentum (Example 1.1):
h3
M (m) (0) 2(1 - B)3 VIV
For Nesterov's accelerated GD (Example 1.2):
h
M (3) (0) 2(1-
V V(())
For AdamW (Example 1.3, also discussed in Section 4):
( (0) = h B1(1 - 31) :3((1 - -32))
32(1 - (32
(VIV2(0))).
+t
(|VC(0) 2 +c)
1/2
(VL()) 2 +e) 3/2
For Nadam (Example 1.4):
- -10)) 82)-1 (n) (0) = h (8((1 - (VC(()) + 1/2
82(1 32)
(V1
+
(|VL(()) 2 + +
3/2
For Lion-K (Example 1.5, also discussed in Section 4):
M (1) (0) - h PI V -x0]
1-p2 P2
E
Mini-Batch Training: Details
Let us take the expectation of the correction term with respect to the random permutation of mini- batches, that is, take the average over all re-orderings π of (g()) (("))
1+ n-
E
g go
g (Tin (1(n-)--b)(
A=
k+1n-1
(0)
I (x(n (x(n-1-b))
nn + 1)!
0=
Note that EVg. gr (1) (0) (3) (0) depends only on whether i j or i + j. Therefore,
E[M (*) = g ()) g (1) (0) CC (1) (0)T (0)),
where C3( and (4 are given by
π- Ca( = 3
3
bb+-1
n (1 (1-3) 11 + B)
n-1
k+1
2,32
Ca(3) = B Σ
84
36 Cs(B)
-
2000
(1 3))
k=0 0
1=
h=0
19

---

We can simplify
(0)
(0) g (
(
Vg.(0)' + o1);
(n + 1)m iデj
where g(0) (0) (n + Ex=
n+| g (0) is the average of (0)). on (1) tends to
zero as n > 20.
So, for large n we write
= (000:///0"00010//100000000000000
R (0)
(0) -0) g(0))
B
31-333 Vg. (0) g(0) C, -00
F
Proof of Theorem 3.2
Since, by the assumptions of the theorem,
((++1) 1) Ō(:) -hF(") (n)
)(m))
22 aF(")
n-1
m3)
Σ
F())
(0
)(m))
(12)
x)
-=n-k
we need to show that
(1)
00)
- (0
(n)
(())
OF
(n)
F(o) @ ((")
!....!"") + Ohh?)
h
(13)
kj
k=1
S=R-K
By Taylor expansion with the Lagrange remainder,
F(m)
0 (n)
10)
F
(())
(1)
(m))
OF
(x)
(n)
((O) (n- )(m)
00 nn
02 P(N))
(m-hi) k1)
の Φ(n) T
ki ag(n))n(n)) (C) 0 (n- _p(r)
+ 2 A1 ml
00 (n-nkk
OF
(n)
0 (()) I T(@11- (n
0 ((m) + +hh2)
(14)
k= 00 nn ()
where Ç is some point on the segment between (0 (n)
(0)
and (0(m) ,...., ((n)): in (a) we used
(n)
Assumption 3.1 and 0 (n-kk) (n) hkk (n-
k2)
hk2h) Since the underlined
term in Equation (12) is O11), we have
(m) (()) Σ (0()) g
k
F σ00) + 0(h)
h
s=n-k
--1
Σ
(O (m)
,...,," )0)) + O(K21)),
s=n-k
20

---

where in the last step we used (
( ....,0")) = O((n - s)h), which
follows from Taylor expansion, Assumption 3.1 and 0 g(m+1) - = -hh). Combine this with Equation (14) to get
F (m)
P
(
OF
(1)
mn
E
F FO
)=0)+((())))) + 0(
de (n
aF
n-1
(m)
(n)
(
...,0a) )(m) + 0(h))
= h
00 kg(nnk]
S=n-k k
which is (13), and the proof is complete.
G Proof of Corollary 3.3
We follow a standard argument, e. Ghosh et al. [26], Cattaneo et al. [1]]. We prove the following claim by induction over E Zzo:
|10(n) 0 00 co & diedhnh
||(
(n+1) O(1) m(m) 11o0 dgedanhni
where
dP C1, d2=
d3 = Cid2. Tki
k=0
Because wh < T, Corollary 3.3 will follow.
Base: = 0. It is indeed true that ||0(0) (0)
100 & d₂h² because the left- hand side is zero. It is
indeed true that |je(1) (1) ( + ē 11 & dyh for the same reason.
(0)
Assume E3 and it is true that
[10(a') -0(²() '1 ooo & dheam'
11(xa(+1 - 0(n') + 1 & dne
for all 0 E n' < n 1. Then
0 (2) 10x0 < 110(--1)- ((n-))_((n-)) (11-1) 1000 11(())) ((n) 0(n-1) + ((n-1) 11
by the triangle inequality,
d)) 12
by the induction hypothesis,
d3 da(a- < d1 d2n-111) di
di 1+
by d3 < d1d2
< dg danhp 2
by the inequality
et for all 2 0.
Next, write
(x++1 -0++1)g)))) _ -
g(n)
+ +
(nh ..... ((0)) (g _ -(())
,
21

---

h (ii) ....,,"") (F(m) (0.00,,).)))) ) (0( -0¹") + + (0()) 000))
Then
10(x+1) - -00) - 0((+1) + +
h ( [n]
(0)
F! (0 ()
0 (0)) | + (0(++1) -(()) + +h (m)
000
< h F [n)
F!
(0
0 + Cc
by Theorem 3.2,
aF(")
=h
(c)
0 kn
x/n
+ C
de (n(m Rj
R=
where Ç is a point on the segment between (0 (0(")
000) and (o(m) (
hd
7kl (1
0(n k) 1o + C
k=0
by (3.1) (recall that d the dimension of 0),
< di h
The d2(n + C
k=
by the induction hypothesis and the bound on 110() - 0(1))loo already proven
did
* + Cj
ddanhyp3
k=0
Eds E ddgedent 1,3.
H Auxiliary Results
Lemma H.1 (Memory decays exponentially fast). If ((n)) is a function of "momentum variables" as described in Assumption C.I, then for any n and le & n
@F (n)
max
E Yk.
(15)
and similarly for any n and kı, k2 < n
82 pr(n)
max 1:
00 (n- 1s)
00 -0 kz)
(16)
where } and (o) } are sequences decaying exponentially fast: specifically,
7h = C, {max (max 3.)*, Ta = C. CmAmax 3ekkt k
for some constant C, > 0.
Proof. It is easy see (15) by taking the derivative:
a- k) F(n)
(0()))
0 (0)
22

---

m ( @m (n+1)
2er (m+1)
(m)
imes
((n-k)
1n+1) o 04r
(m) (n+ 1)
m (n+1))
(0 (m)-
and using the uniform boundedness of derivatives of P6s (n-k) and p,. Equation (16) is proven similarly.
Lemma H.2. Let fa and (br Dk be sequences of reals such that Ex=I(aas) + (bxb)) < co. Then
ak
O.
Proof. Fix & > O. Take such positive integer no that for any no & my & 12 we have Eo (1ax) +
[bxl) < E. Then for any n > 2ng the following holds:
n no
0 (lax) + |bx l.
|bal
Σ
a
|ba
8
1=
xm 72
kmn
+o
Since e is arbitrary and Σe= (lax|
16 is a finite constant, the statement follows.
I Corollaries for Special Cases
Lemma 1.1 (Application of Corollary 3.3 to Example 1.1), Let (0(")) Ineāzo be the sequence of
vectors generated by the iteration in Equation (1) with initial condition (()), where F(*)()) (.) is
defined in Example 1.1, and the loss function E(-) defined in an open convex bounded domain D C Rd is three times continuously differentiable with bounded derivatives; also, let > be fixed "time" horizon. Then Assumption 3.1 holds; in particular, by Corollary 3.3 the inequality
maxne[0:[///||100 - 00' 1l < Czh²² holds, where
Ø(n+1) ((()) 1 gn+1
- 3 V)((0")) + +,
3[
(2n + 1)3a(1 - -B) g2n+1]
M m 0
((()) r [1:d].
2(1 - -333
Proof. The fact that Assumption 3.1 holds is already verified in Section C. Next, this case
F(") (0) 1 --+1
1- V,L(O),
OF!")
00 m (0) g" sy C(O).
Therefore,
n d
dF(m)
n-
(m) h
Σ
E
(
!0!n-Ki
$=n-k
- g8+1
h
1 1- 3
23

---

31 (2n (1 (3) 32++1
in ((OVV..CC()
(1- -33
Lemma 1.2 (Application of Corollary 3.3 Example 1.3). Let (0(*)) JnE be the sequence of vectors generated by the iteration in Equation (1) with initial condition ( where F-r)()) is as defined Example 1.3, and the loss function L(-) defined in an open convex bounded domain D Rd is three times continuously differentiable with bounded derivatives; also, let T > be fixed "time" horizon. Then Assumption 3.1 holds; in particular, by Corollary 3.3 the inequality
-0 & C2hh2 holds, where
O,
0(++1) = (1- 11)0(m)) h
+ +M -,(((((()))
(10,
)2 + +5) 1/2
8g
(n+1)97
M (0) h
B1
(n + 1),9+11
82
(n + 1)
1-8
1-83
1- B1
1 1 81
1- B2
1 gu+l
0 (0)(( +
(O))) + (()00(
r E [1:d]
((,,((0))² + 8)1/2
Proof. The fact that Assumption 3.1 holds is already verified in Section C.
Next, in this case
0,C(0) + 20r,
F!" (0) VO,2(0)2 +E
1-8 ((0)
1-82 1000,8))0000)))00,0100
(0) 1-
0g(n-k)
(10,(00)12 + E)1122
(10,((0)) +
Therefore,
d
R-1
(.) = h
Σ
F!
(
(0)
30
20(n-R)
k=
S=R-
C(B)
O,C(0)
- 31
h
10,
k
(10,2(0)}+
(10,
+2/122
91
gn+1
C,,)(0)
0,C(0)
83
10,
+ A0,
k
2= (1,,2(0)2 + E
(10,C(()) + +)
1
3n+1
1=1
B1
(n + 1)
(,,(())
OCC(0)
h
+ +0
1- 87
(10,C(0))² + 1/2
82
(n+ + 1).82
(0,
0,C(0)
+ A0,
1
32
1 1 g8+1
(1,,((0)² ((0,L(0)) + 5)1/2
B
(n + 1) 1
(0, VL000/)).. -(V- (1)=2(0))++)1/2 +
31
1 188+1
32
(n + 1)38 2
(0.110)((011V2((0))==++++
32
1 gn+1
(10,C(0)) 2 +033/2
80 (a+1)an++
B1
(n + 1):9++1
B2
(n (1
1-9:
1-8744
h
+
+
B
1 - gh+1
1- B2
B1+1
12,( +
24

---

( +
x
+
as desired.
Lemma I.3 (Application of Corollary 3.3 to Example 1.5). Let (0(0) InEZzo be the sequence of
vectors generated by the iteration in Equation (1) with initial condition g where F (.) is as
defined in Example 1.5, the function (C). .M + R defined in a open bounded region M C R is three times continuously differentiable with bounded derivatives, and the loss function [()) defined
in an open convex bounded domain DD C I is three times continuously differentiable with bounded derivatives; also, let T 3 be fixed "time" horizon. Then Assumption 3.1 holds; in particular, by
Corollary 3.3 the inequality max (0: [T/N]]]] ( 0
((m) Ioo < CChh² holds, where
Ō(n+1)= = (1- - -m) 11--0,1(-(0 -1 V + ( ())))))
d
d
M (0) hhppp111 p2)
8g ((1)))a))))
n-1 1 k-1
x
(-arK( (11 -110-1p))) (1P2) + X0.)
k=1
8=
PI
1,,, + 10.) + o,,
where on (1) a function o converging to zero uniformly in 0 E D.
Proof. The fact that Assumption 3.1 holds is already verified in Section C.
Next, this case
F (0) -, A0r,
d
(0)
00 n- R)
j=1
Therefore,
12
OF
R-1 Σ
M (0)
(0)
00 n
kml 1=1
smp nー k
hppi (1 p2)
Kg (-(C((11111111)11 (-1--1@)V<())),00
iml
x
P2
Σ
(1 -1 (-ON((-1--P00)VV()))++++
km
Note that
where Ç is on the segment between -(1 (1P3) and - CCO). Applying Lemma H.2 with
P2 1-1 and b, = Pg we see that
ag
+ A0.)
km
$mn= k
k-
+ -0.) + (1) = (-a,((-V2()) + >0.)) + o1),
P2
(1 p2)
1=1
25

---

where On (1) + 0 as - oc uniformly in 0 E D. Using the boundedness of derivatives again, we
also have
hpı(1 P2) Σ
-
j=1
= hpri P2)
and
d d
(0)
- 0,<c--7Ze))a2200000X--VVV00 + 1O.) + (1)
P1
k
P2
==1
as desired.
Empirical Illustrations
As sanity check, we verify that the memoryless iteration (4) that we find is closer than the first-order approximation (the one with no correction from memory: for example, the first-order approximation of Adam is sign gradient descent [47]). We see in Figure that the loo (maximal) norm of the weight difference smaller with the correction term. Note that the learning rates are realistic and weight decay is present.
(a)
0.00175
order memoryless, h=0.0001
1-order memoryless, h=0.0001
2 order memoryless, h=0.0001
2-arder memoryless, h=0.0001
0.00150
1-order memoryless, h=0.0003
1-order memoryless, h=0.0003
0.00125
memoryless, h=0.0003
memoryless, h=0.0003
Weight Dift
Weight Diff
0.0015
0.00100
0.00075
0.0010
0.00050
0.0005
0.00025
0.00000
0.0000
10
Epach
Figure 1: Comparison of the trajectories: -nomm of weight difference between the second-order memoryless method from Theorem 3.2 and the first-order approximation (signGD): (a) Adam, (b) Lion (perturbed by and with bias correction). MLP with GELU activation on MNIST-IOK. learning rates h E {10-1
10 10-4,, weight decay 10 10-3/h, 10-6
As preliminary empirical illustration, train ResNet-50 [31] CIFAR-10 [38] using Adam (with decoupled weight decay) and Lion. We keep the 31 parameter Adam at 0.99 (for stable training CIFAR-10 10 [47, 11]) and sweep the 32 parameter. We plot in Figure 2(a) the test accuracy at a fixed small training loss threshold (controlling for training speed). As predicted in Section 4 and confirming the observation from [11] for pure Adam without weight decay, the test accuracy drops as 32 approaches one. We see that Adam with lower values of 82 can sometimes outperform Lion with default hyperparameters and thus close the generalization gap between these two algorithms, consistent with the theory. We also observe this phenomenon on language task by training Transformer-XX [18] on WikiText-2 [49]. We fix the default B1 0.9 for Adam and sweep 32. plotting the minimal validation perplexity achieved before overfitting; in the vision task, we compare with Lion whose hyperparameters are set at default values. We observe in Figure 2(b) the same trends as above (in large-bate batch training, higher 32 increases the best validation perplexity. that is, hurts generalization; sometimes, taking lower 82 can close the gap between Adam and Lion).
We provide some additional sweeps with different learning rates in Figures and 4.
The code is available https: wttp:/.ccoooobaaaaaeo
26

---

(a) ResNet-50 on CIFAR-10
(b) Transformer-XL on WikiText-2
0.85
155
0.84
Test acc
Val ppl
0.83
145
0.82
0.81
0.90
0.92
0.94
0.96
0.98
1.00
0.75
0.80
0.85
0.90
0.95
1.00
Figure 2: (a) ResNet-50 on CIFAR-I0- 10: test accuracy at training loss threshold 0.05. Full-batch Adam, learning rate = 10-3.5 B1 = 0.99, 10-6, weight decay 0.005. For comparison, we also show Lion with the same learning rate and weight decay (with default #1 = 0.9, p2 = 0.99). (b) Minimal validation perplexity (before overfitting) of Transformer-X XL trained with full-batch Adam on WikiText-2 with learning rate 10 81 0.9, & = 10 6, For comparison, we also show Lion (with default P1
0.9, P2 0.99). All results averaged over three iterations.
(a)
(b)
0.82
0.83
0.81
0.82
0.80
Test acc
Test acc
0.81
0.79
0.80
0.78
0.79
0.77
0.76
0.78
0.90
0.92
0.94
0.96
0.98
1.00
0.90
0.92
0.94
0.96
0.98
1.00
B2
B2
Full-batch Adam, Figure 3: ResNet-55 on CIFAR-I0: test accuracy training loss threshold 0.05.
learning rates (a) = 10-4; (b) h = 5 x 10-5, 31 0.99, & = 10-6 weight decay 5 x 10-6.5 10-66.// /h. For comparison, we also show Lion with the same learning rates and weight decay (with default P1 = 0.9, P2 = 0.99), All results are averaged over three iterations.
J.1 A Note on the Edge of Stability and Comparisons with Lion on Vision Tasks
Cohen et al. [16] notice that in a sense Adam trains at the edge of stability. They view Adam as momentum gradient descent with evolving preconditioner
P = (1- 14t1) diag
V++1 8
+ el
They define "preconditioned sharpness" to be the top eigenvalue of the preconditioned Hessian (P, HH,), where H, the Hessian the loss, and observe that this quantity often oscillates around the stability threshold 2+28, (1-3,)7' where v is the learning rate. (This fraction comes from the fact that if the preconditioner were constant, Adam would become form of preconditioned gradient descent with EMA-style momentum, and this is the ordinary stability threshold of EMA-style heavy-ball momentum on the quadratic Taylor approximation of the loss; we refer to Cohen et al. [16] for details.) They use latch-batch training on CIFAR- --7AAR-101100.. as well, and reproduce this result in Figure 5. We also plot ordinary sharpness ê (H,) (top hessian eigenvalue), which first increases and then decreases. Recall that this an extremely unstable regime of training [47].
train a CNN on CIFAR-10
27

---

(a)
(b)
160
160
155
Val ppl
Val ppl
150
150
145
145
140
140
0.90
0.92
0.94
0.96
0.98
1.00
0.90
0.92
0.94
0.96
0.98
1.00
Figure Minimal validation perplexity (before overfitting) of Transformer- trained with full-batch Adam on WikiText-2 with learning rates (a) h 5 x 10-5; ; (b) h 2.5 x 10-5, weight decay 10 10-$/h. 31 0.9, = = 10 6 For comparison, we also show Lion with the same learning rates and weight decay (with default #1 0.9, P2 0.99). All results averaged over three iterations.
Note that the parameter controlling the exponential forgetting of gradients 31 corresponds the P2 parameter of Lion, so the default P2 0.99 in Lion would match 81 = 0.99 rather than 31 = 0.9 in Adam. If take 31 0.99 which the "smooth" regime training, preconditioned sharpness does not reach the stability threshold (Figure 6). Note also that ordinary sharpness (H,) (top hessian eigenvalue) much lower for small 82 (especially noticeable for 31 < 0.9). This suggests that in large-batch training vision tasks, taking 32 < B1 0.99 strongly regularizes training, moving the model parameters to flatter regions of the loss space. It is promising direction investigate the limits of such regularization: for example, taking 32 near the threshold of divergence may regularize training so much that the default Lion will not be able to match in terms of generalization error.
K Experiment Details and Licenses
Our implementation of ResNet-50 follows the from [11] (small modification of the standard torchvision implementation to allow for training on CIFAR-10 rather than ImageNet). The torchvision repository has the BSD 3-Clause license. CIFAR-10 is released without explicit license. MNIST has the CC BY-SA 3.0 license.
Our implementation of training Transformer-XL. on WikiText-2 follows the one from [41] which is small modification of the codebase" for [18], licensed under the Apache-2.0 License. The WikiText-2 dataset is released under the CC BY-SA 3.0 license.
For Adam (with decoupled weight decay). we use the standard implementation from pytorch. cytorch.optinn Lion is taken from the google/ e/automl repository". This repository is licensed under the Apache License 2.0. The implementations of the optimizers used for comparing the trajectories in Figure of the paper are custom and match exactly our analytical formulas (in particular, Lion has bias correction and the sogt-sign function r + z/ 2 2 + instead of the sign function), given below.
Adam W: memoryless update
The (full-batch) memoryless AdamW approximation
)fm-1) = 5/ - h 1.F/M)) (o(m)) hMf()
where
V, C(0
p(")
+ 1020
((0)2 +
82
(n + 1) 11
V (V,C00))+<)>>
(0 -
32
28

---

leamning 0.00025
Top precandiiorad algenvalue
500000
400000
3500
3000
300000
2500
2000
8.-0.88
8.-0.95
8um0.999
0.999
1500
100000
8.:00.99
EOS
8000
4000
10000
Fpoch
Epoch
learning rate 0,0005
200000
4000
150000
3000
Top procondiloned
2000
100000
Top
1000
50000
pam00
Bam0.95
Ben 999
Bam0
8i-0.90
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Epoch
Epoch
learning rate 0.001
2000
precanditoned hocsian aigenvalue
300000
1750
Top hecean eigenvaluu
1500
m
100000
1000
750
-100000
pam0.8
8:-0 90
FOS
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Figure 5: CNN trained on CIFAR-10 with full-batch Adam, 31 = 0.9, 600 10-6 learning rate 0.001. Left: preconditioned sharpness A1 (P, HH)) oscillates around the stability threshold. Right: the plots of ordinary sharpness \₁ (H.).
B
(n + 1)8 8
VV VVI + C())0))
/
1-
B1
CVV
Lion-K with bias correction The Lion-K algorithm with bias correction is defined in Example 1.5 of the paper except bias correction is added:
F(1) (0())
(0))
V/C(m) (n-1) + mm mm(+t))))
(m+1))
+ m3 mn (n+1)
where m (n+1)
P2
PI
PS [(
1
Pz
n+1
mi
(n+1)
1
P1
V vL((()))
29

---

leamiing 0.00025
aigenvalue
10000
Top hisean elgenvoluus
0000
preconattiona
4000
M
2000
Ba 8
8..0.95
8u-0.999
Pa
EOS
2000
10000
4000
10000
Epoch
Fpoch
learning rate 0,0005
algenzalie
800000
700000
6000
600000
5000
procondirioee
4000
300000
W
Top
2000
200000
Bam0.99 99
ED5
1000
Rum 0.05
Pa-0 0.99
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Epoch
Epoch
learning rate 0.001
Top preconditored aigencalue
400000
350000
2500
eigervalue
300000
2000
250000
1500
1000
100000
500
Ru-0.95
Pa-0.00 0.999
50000
0
0
2000
4000
6000
BOO0
10000
2000
4000
6000
8000
10000
Epoch
Figure 6: CNN trained CIFAR-10 with full-batch Adam, B1 = 0.99, = 10-6 learning rate 0.001. Left: preconditioned sharpness (P, (P,")H)) plots of ordinary sharpness \₂ (H.).
HH,) does not reach the stability threshold. Right: the
m3 (x+1) (n(n)
Lion (perturbed by e): memoryless update
The memoryless iteration is given by
0f1-1) 0 hp (o hM, (0(())
where
((0
F(m) (0)
+ 200,
V V /(()2)
M (1)
(0)
P1
(n + 1)p5p1
1 P2
1 1 p
u+1
30

---

(V)2(0)) + 3/2 V ([VV (VC(O) c()))
K.1 Compute Resources
One sweep of hyperparameter 32 contained about 12 runs, with each run repeated for 3 iterations. Each run took about hours on average on one machine with a devoted 40 GB NVIDIA A100 GPU (though the training horizon was longer than necessary). This puts compute resources at around 12 x 10 x = 360 A100-GPU-hours per sweep. Figure 2, two sweeps were conducted. The experiments truncated MNIST conducted to produce Figure used negligible resources compared to the sweeps described (less than I GPU-hour). Additional compute was used for preliminary experimentation.
31

---

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:
We substantiate all claims made in the abstract and introduction.
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 in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as 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:
We discuss limitations Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create 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 (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to 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 address problems of privacy and faimess.
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?
Answer: [Yes]
32

---

Justification:
We include the proofs of our theoretical results.
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 referenced in 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 are encouraged to provide short proof sketch 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 be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The experiment details are discussed in figure captions and relevant appendices.
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 a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make 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 can also be provided via detailed 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, or other means that are appropriate to the research performed.
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 clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is 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 instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, 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 to eproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
33

---

Answer: [Yes]
Justification: The code, along with instructions to reproduce the results, is released publicly and referenced in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.c ec/
Policyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. cttccc/ppbbc wcc//ublcc//aeccccccccccccccelle wwwpcc/gguieeeeeeee /eoiidSu// iomiissionnl wasssssoliccyyy for more details.
The authors should provide instructions 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 are 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 (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We discuss experimental details in figure captions and the appendices.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We include the error bars in our figures.
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, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
34

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures 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 to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide compute resources in the appendices.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 as well as 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 't make it 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 https: / htt////nurrpp.ppe httpppp///errppp.ppppptttt////// htwp://thihiuieeeeeeeeeeeeeeeeee
Answer: [Yes]
Justification:
We have checked that we conform to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We include short note on broader impacts in Section B.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal 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.
35

---

The conference expects that many papers will be foundational research and not tied to 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 does not pose any non-trivial risks of misuse.
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: [Yes]
Justification: We provide the license information in Section K.
Guidelines:
The answer NA means that the paper does not 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 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.
36

---

If this information is not available online, the authors are encouraged to reach out to the asset'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:
We do release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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. Crowdsoureing 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:
We do not conduct crowdsourcing experiments with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 the main paper.
According the NeurIPS Code of Ethics, 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:
We do not conduct crowdsourcing experiments with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 sho Id clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and 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 the institution conducting the review.
16. Declaration of LLM usage
37

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: We only used LLMs for code completion, reformatting assistance and brain- storming.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https : /ttp///eissp///eeee /ttp///ips.c.ooooeeeeeeeeeeeeeee /ttp:////cceeeenne//2////111 for what should or should be described.
38


Reviews:
[{"review_id": "HxX8e6spkA", "reviewer": "Reviewer_WQ9W", "summary": "The paper contains a theory to show how gradient-based algorithms with momentum\nterms, and more generally optimization algorithms that have a non-local in time\nupdate rule but whose dependence on past-in-time information decays exponentially,\ncan be approximated by a local-in-time update rule. The paper gives a general\nclosed-form derivation of this memoryless update rule.", "questions": "1. Equation (6), if I interpret correctly, is obtained in the limit\n$n\\to\\infty$.  But how can we be sure that the initial iterations do not\nsubstantially change the trajectory in the parameter space, giving us\nsubstantially different methods?\n\n2. It is well known that gradient descent with momentum (and all the other\nmodern gradient-based variations like Adagrad, Adam, RMSprop etc) can be\ninterpreted in terms of a sequence of optimization problems; this is the\ntypical view that theories like Minimizing Movements, proximal methods and\nmirror descent offer. See for instance section 3 of this work\n\nBetti, A., Ciravegna, G., Gori, M., Melacci, S., Mottin, K., & Precioso,\nF. (2024). A new perspective on optimizers: leveraging Moreau-Yosida\napproximation in gradient-based learning. Intelligenza Artificiale, 18(2),\n301-311\n\nDo you think that there could be direct connections between these two\nmethods, for instance between the modified \"effective\" loss that you compute\nand the regularized loss that is used to define GD with momentum in this\nframework?\n\n3. Can you comment on where the condition in Eq (7) is used? Is it used in\nthe direct derivation of the method or in the approximation bound result?\n\n4. It is not clear to me how this analysis and the error bound could carry\nover to the stochastic counterpart of the described optimization algorithms\nthat are fundamental in ML.\n\n5. In the derivation of GD with momentum in section 2 and in the general\ncase, it is not completely evident why in the equation after line 127 the\nterm $\\sum_{k=0}^n O(k^2 h^2)$ could not give contributions of order $O(1)$\nfor big values of $n$ and $k$. How can we be sure that we can discard these\nterms?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The article is extremely well written and clear, and the contribution, to the\nbest of my knowledge, is novel. Even though it does not present a new model\nor optimization scheme, it provides interesting insights into interpreting\nwell-known and widely used optimization algorithms.\n\nIn particular, it seems to offer a useful theoretical tool to better\nunderstand and highlight different behaviors of a class of optimization\nalgorithms. On the other hand, if I understand correctly, it does not provide\nan alternative, implementable, viable relaxation or approximation, since the\nmodified loss or the correction term typically contains higher-order\nderivatives that are hard to compute numerically (Eq. (6) and Eq. (9)).\n\nThe analysis of AdamW and Lion in Section 4 is interesting.\n\nThe comments in Section~6.1 are particularly appealing to me, as they seem to\nindicate (and please correct me if I have misunderstood) that, for instance,\nthe Heavy Ball method can be approximated (in the continuous limit) by a\ngradient flow in which the \"energy function\" already contains the gradient of\nthe original loss.\n\nI liked the paper and am willing to further raise my rating after the\nrebuttal period, based on the answers to my comments and questions.", "was_revised": true, "final_justification": "I've raised my rating as a result of the answers provided by the authors. I have carefully read the authors’ rebuttal as well as the comments from the other reviewers and the AC. I did not find any additional major issues raised by the other reviewers. For these reasons, I recommend acceptance of this work.", "rebuttal": "Thank you for your careful reading of our paper and valuable comments. We answer each of your questions below.\n\n**Q1.** It is a very good point which we thank you for making. Technically, it is impossible to obtain an $O(h^2)$ global approximation of GD with momentum by an ordinary GD independent of $n$. This is why our iteration given in Equation (4) depends on $n$. However, qualitatively, the dynamics becomes close to a fixed ordinary GD, and the goal of neglecting $o_n(1)$ coefficients was only to simplify the description of this qualitative behavior, as common in the literature (in particular, [22] discusses heavy-ball momentum). This is related to the fact that momentum methods can be approximated by gradient flow on an exponentially attractive invariant manifold but not everywhere, as discussed in Section 4 of [31]. As you point out, the trajectories are not the same, and we will add into the Appendix precise lemmas with the $o_n(1)$ terms given explicitly. The lemma pertaining to heavy-ball momentum is as follows:\n\n*Lemma.* Let $(\\boldsymbol{\\theta}^{(n)})\\_{n \\in \\mathbb{Z}\\_{\\geq 0}}$ be the sequence of vectors generated by the iteration in Equation (1) with initial condition $\\boldsymbol{\\theta}^{(0)}$, where $\\boldsymbol{F}^{(n)}(\\cdot)$ is as defined in Example 1.1, and the loss function $\\mathcal{L}(\\cdot)$ defined in an open convex bounded domain $\\mathcal{D} \\subset \\mathbb{R}^d$ is three times continuously differentiable with bounded derivatives; also, let $T \\geq 0$ be a fixed \"time\" horizon. Then Assumption 3.1 holds; in particular, by Corollary 3.3 the inequality $\\max\\_{n \\in [0:\\lfloor T / h \\rfloor]} \\big\\\\|\\boldsymbol{\\theta}^{(n)} - \\tilde{\\boldsymbol{\\theta}}^{(n)}\\big\\\\|\\_\\infty \\leq C_2 h^2$ holds, where\n$$\n  \\tilde{\\theta}\\_r^{(n + 1)} =  \\tilde{\\theta}\\_r^{(n)} - h \\bigg(\n    \\frac{1 - \\beta^{n + 1}}{1 - \\beta} \\partial\\_r \\mathcal{L}\\big(\\tilde{\\boldsymbol{\\theta}}^{(n)}\\big)\n    + M\\_{r}^{({n})}\\big(\\tilde{\\boldsymbol{\\theta}}^{(n)}\\big)\\bigg),\n$$\n$$\n  M_{r}^{({n})}\\big(\\boldsymbol{\\theta}\\big) =  h \\frac{\\beta [1 - (2 n + 1) \\beta^n (1 - \\beta) - \\beta^{2 n + 1}]}{2 (1 - \\beta)^3} \\partial_r \\\\|\\nabla \\mathcal{L}(\\boldsymbol{\\theta})\\\\|^2,\\quad r \\in [1:d].\n$$\n\n**Q2.** While it is not currently clear how to relate the modified loss with the minimization problem in Eq. (22) in the paper you provided, there are some connections to be noticed. For example, GD with momentum can be seen as a smoothed-out version of GD which is steepest descent with respect to the 2-norm (as written in Eq. (8) in that paper). Our framework informs that memory implicitly penalizes the squared two-norm of the gradient $\\\\| \\nabla \\mathcal{L}(\\boldsymbol{\\theta}) \\\\|^2$ which is the square of $\\min\\_{\\|\\boldsymbol{\\\\delta}\\\\| \\leq 1} \\nabla \\mathcal{L}(\\boldsymbol{\\theta})^T \\boldsymbol{\\delta} \\approx \\min_{\\\\|\\boldsymbol{\\delta}\\\\| \\leq 1} \\mathcal{L}(\\boldsymbol{\\theta} + \\boldsymbol{\\delta})$; the latter is the same optimization problem as the one below Eq. (3) at the end of the column in that paper. The same argument can be made about Adam (smoothed-out version of sign descent, steepest descent under the infinity norm) and a different pair of dual norms $\\\\| \\cdot \\\\|_{\\infty}$ and $\\\\| \\cdot \\\\|_1$. We currently do not have a complete understanding of these coincidences but we plan to add a discussion of this as a future direction and we thank you for pointing it out.\n\n**Q3 and Q5.** Equation (7) is used to control the accumulation of error: intuitively, since memory decays fast enough, past errors also decay fast enough. For the special case of GD with momentum, consider the term $O(k^2 h^2)$ after line 127 you referred to. The $k^2$ factor in the error disappears because $\\sum_{k = 0}^n \\beta^k O(k^2 h^2) = O(h^2)$ by virtue of summability $\\sum_{k = 0}^\\infty \\beta^k k^2 < \\infty$. Equation (7) generalizes this and is used in similar contexts, such as before line 151, in lines 155-156 in our derivation section, in line 663, between lines 668-669 in the proof.\n\n**Q4.** You are correct in pointing out that stochasticity introduces additional challenges. Theorem 3.2 and Corollary 3.3 are applicable regardless of whether the loss function is the same at each iteration or different as in mini-batch training, so the technical approximation result can be obtained for mini-batch training with no additional work. However, one then needs to choose a framework to analyze the results qualitatively, e.g. identify implicit regularization by noise. We illustrate that is possible in Section 6.2 for the simple special case of stochastic GD with momentum. While not in the scope of this paper, we know that it is possible for AdamW as well (although with significantly longer calculations), and we plan to present it as upcoming work.\n\nPlease let us know if we accidentally misunderstood or missed any of your points or you have additional questions or suggestions. Thank you!"}, {"review_id": "y5ItWxzkHQ", "reviewer": "Reviewer_dFWS", "summary": "This paper investigates optimization algorithms using a general update rule:\n\n$$\\theta^{(n+1)} = \\theta^{(n)} - h F^{n}\\left( \\theta^{n}, \\theta^{(n-1)}, \\ldots , \\theta^{0} \\right) \\quad (1)$$\n\nHere, $h$ represents the step size. This formulation is broad enough to encompass numerous well-known algorithms that leverage past gradient information, including methods like Momentum, Nesterov acceleration, Adam, and Lion. The paper approximates (1) with a memoryless algorithm operating on a modified loss function. This modification reveals how memory regularizes the optimization process. The techniques developed are then applied to study the implicit regularization properties of Adam and Lion. This analysis shows that, with certain hyperparameter configurations, Adam can actually anti-regularize the optimization dynamics.", "questions": "1) Can the authors comment on Assumption 3.1 ? How restricitve is to assume that the coefficient decay, is it possible to verify this for example for Adam (or even momentum GD) in some simpler settings ?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\na) One of the strengths of the paper is to provide an unified framework to study the regularization properties of various optimization algorithms that utilize the memory. This makes the techniques applicable to many scenarios. \n\nb) The intuition and the derivation of the result is well incorporated in the main text with an illustrating example of momentum GD. \n\nc) Identifying that the small $\\beta_2$ of Adam leads to better performance is a interesting result and can give some insights into how to  choose the hyperparameters. \n\nWeakness:\n\na) A significant weakness of the results lies in the lack of precise statements regarding the implicit regularization of Adam and Lion within Section 5. For instance, lines 176 and 191 contain phrases such as \"Neglecting coefficients decaying to zero exponentially fast.\" Such statements require formalization to clearly define the regime of applicability for the results. This precision would also facilitate a more direct comparison with prior work, such as [56], which investigates other implicit regularization aspects of Adam. It is highly recommended to include formal Lemmas for the implicit regularization of Adam and Lion, detailing all necessary technical simplifications.\n\nb) The empirical evaluation section presents several drawbacks:\n- Limited Scope of Trajectory Comparison: The comparison of trajectories is exclusively restricted to MLPs. Extending this analysis to other network architectures would provide a more comprehensive understanding. Additionally, the inclusion of error bars for these comparisons would be beneficial for assessing the robustness of the observed trends.\n- Learning Rate in Figure 2: Figure 2 should be further investigated with varying learning rates. This would help determine if the observations concerning $\\beta_1$ and $\\beta_2$ generalize across different learning rate schedules.", "was_revised": true, "final_justification": "The rebuttal from the authors gave me confidence that the paper will be revised to improve technical clarity and also more detailed experimental section. However, given some restrictive assumptions, I maintain my initial positive rating and do not raise it further.", "rebuttal": "Thank you very much for your thoughtful review and suggestions.\n\nRegarding your question and weakness (a), we have added the two lemmas given below (and their proofs) to the next revision. In particular, classical Adam is indeed covered by our framework. The assumption on the decay of memory appears to be mild since usually memory decays exponentially.\n\nThe lemma for Adam is as follows.\n\n*Lemma 1.* Let $\\{\\boldsymbol{\\theta}^{(n)}\\}\\_{n \\in \\mathbb{Z}\\_{\\geq 0}}$ be the sequence of vectors generated by the iteration in Equation (1) with initial condition $\\boldsymbol{\\theta}^{(0)}$, where $\\boldsymbol{F}^{(n)}(\\cdot)$ is as defined in Example 1.3, and the loss function $\\mathcal{L}(\\cdot)$ defined in an open convex bounded domain $\\mathcal{D} \\subset \\mathbb{R}^d$ is three times continuously differentiable with bounded derivatives; also, let $T \\geq 0$ be a fixed ``time'' horizon. Then Assumption 3.1 holds; in particular, by Corollary 3.3 the inequality $\\max\\_{n \\in [0:\\lfloor T / h \\rfloor]} \\bigl\\\\| \\boldsymbol{\\theta}^{(n)} - \\tilde{\\boldsymbol{\\theta}}^{(n)} \\bigr\\\\|\\_\\infty \\leq C\\_2 h^2$ holds, where\n\\begin{align*}\n  &\\tilde{\\theta}\\_r^{(n + 1)} = (1 - \\lambda h) \\tilde{\\theta}\\_r^{(n)} - h \\bigg(\\frac{\\partial\\_r \\mathcal{L}\\big(\\tilde{\\boldsymbol{\\theta}}^{(n)}\\big)}{\\big(\\big|\\partial\\_r \\mathcal{L}\\big(\\tilde{\\boldsymbol{\\theta}}^{(n)}\\big)\\big|^2 + \\varepsilon\\big)^{1 / 2}} + M\\_{r}^{({n})}\\big(\\tilde{\\boldsymbol{\\theta}}^{(n)}\\big)\\bigg),\\\\\\\\\n  &M\\_{r}^{({n})}\\big(\\boldsymbol{\\theta}\\big) =\n    h \\Bigg(\n                           \\frac{\\beta\\_1}{1 - \\beta\\_1} - \\frac{(n + 1) \\beta\\_1^{n + 1}}{1 - \\beta\\_1^{n + 1}}\n                           -\n                           \\frac{\\beta\\_2}{1 - \\beta\\_2} + \\frac{(n + 1) \\beta\\_2^{n + 1}}{1 - \\beta\\_2^{n + 1}}\n                           + \\varepsilon \\frac{\\frac{\\beta\\_2}{1 - \\beta\\_2} - \\frac{(n + 1) \\beta\\_2^{n + 1}}{1 - \\beta\\_2^{n + 1}}}{|\\partial\\_r \\mathcal{L}(\\boldsymbol{\\theta})|^2 + \\varepsilon}\n                           \\Bigg) \\frac{\\big(\\partial\\_r \\\\| \\nabla \\mathcal{L}(\\boldsymbol{\\theta}) \\\\|\\_{1, \\varepsilon} + \\lambda [\\nabla^2 \\mathcal{L}(\\boldsymbol{\\theta}) \\boldsymbol{\\theta}]\\_r\\big)}{(|\\partial\\_r \\mathcal{L}(\\boldsymbol{\\theta})|^2 + \\varepsilon)^{1 / 2}},\\quad r \\in [1:d].\n\\end{align*}\n\nThe lemma for Lion is as follows.\n\n*Lemma 2.* Let $\\{\\boldsymbol{\\theta}^{(n)}\\}\\_{n \\in \\mathbb{Z}\\_{\\geq 0}}$ be the sequence of vectors generated by the iteration in Equation (1) with initial condition $\\boldsymbol{\\theta}^{(0)}$, where $\\boldsymbol{F}^{(n)}(\\cdot)$ is as defined in Example 1.5, the function $\\mathcal{K}(\\cdot): \\mathcal{M} \\to \\mathbb{R}$ defined in a open bounded region $\\mathcal{M} \\subset \\mathbb{R}^d$ is three times continuously differentiable with bounded derivatives, and the loss function $\\mathcal{L}(\\cdot)$ defined in an open convex bounded domain $\\mathcal{D} \\subset \\mathbb{R}^d$ is three times continuously differentiable with bounded derivatives; also, let $T \\geq 0$ be a fixed ``time'' horizon. Then Assumption 3.1 holds; in particular, by Corollary 3.3 the inequality $\\max\\_{n \\in [0 : \\lfloor T / h \\rfloor}] \\big\\\\|\\boldsymbol{\\theta}^{(n)} - \\tilde{\\boldsymbol{\\theta}}^{(n)}\\big\\\\|\\_\\infty \\leq C\\_2 h^2$ holds, where\n\\begin{align*}\n  &\\tilde{\\theta}\\_r^{(n + 1)} = (1 - \\lambda h) \\tilde{\\theta}\\_r^{(n)} - h \\big(- \\partial\\_r \\mathcal{K} \\big(- (1 - \\rho\\_1 \\rho\\_2^n) \\nabla \\mathcal{L}(\\tilde{\\boldsymbol{\\theta}}^{(n)})\\big) + M\\_{r}^{({n})}\\big(\\tilde{\\boldsymbol{\\theta}}^{(n)}\\big)\\big),\\\\\\\\\n  &M\\_{r}^{({n})}\\big(\\boldsymbol{\\theta}\\big) = h \\rho\\_1 (1 - \\rho\\_2) \\sum\\_{i = 1}^d \\sum\\_{j = 1}^d \\partial\\_{j r} \\mathcal{K} \\big(- (1 - \\rho\\_1 \\rho\\_2^n) \\nabla \\mathcal{L}(\\boldsymbol{\\theta})\\big) \\partial\\_{i j} \\mathcal{L}(\\boldsymbol{\\theta}) \\sum\\_{k = 1}^n \\rho\\_2^{k - 1} \\sum\\_{s = n - k}^{n - 1} \\big(- \\partial\\_i \\mathcal{K} \\big(- (1 - \\rho\\_1 \\rho\\_2^s) \\nabla \\mathcal{L}(\\boldsymbol{\\theta})\\big) + \\lambda \\theta\\_i\\big)\\\\\\\\\n  &\\quad = h \\frac{\\rho\\_1}{1 - \\rho\\_2} \\sum\\_{i = 1}^d \\sum\\_{j = 1}^d \\partial\\_{j r} \\mathcal{K} \\big(- \\nabla \\mathcal{L}(\\boldsymbol{\\theta})\\big) \\partial\\_{i j} \\mathcal{L}(\\boldsymbol{\\theta}) \\big(- \\partial\\_i \\mathcal{K} \\big(- \\nabla \\mathcal{L}(\\boldsymbol{\\theta})\\big) + \\lambda \\theta\\_i\\big) + o\\_n(1),\\quad r \\in [1:d].\n\\end{align*}\nwhere $o\\_n(1)$ is a function of $\\boldsymbol{\\theta}$ converging to zero uniformly in $\\boldsymbol{\\theta}\\in \\mathcal{D}$.\n\n----------\n\nRegarding weakness (b), we are conducting sweeps with more learning rates; in addition, we would like to refer to Section 2 ``Additional Experiments'' in the supplementary material (file `supplemental_appendix`) where two more learning rates for each of the tasks (vision and language) are provided; we will expand the sweeps and present them more noticeably in the paper. For the trajectory comparison in the weight space, we have run additional simulations with a small CNN and a simple Vision Transformer, following your suggestion. In the CNN case, the corresponding weight difference $\\infty$-norms for Adam with $h = 10^{-3}$ after $1, \\ldots, 5$ full epochs are as follows:\n```\n1-order: [2.9802322387695312e-08, 2.261623740196228e-05, 6.423518061637878e-05, 0.00012150406837463379, 0.0001912824809551239]\n2-order: [2.9802322387695312e-08, 1.644715666770935e-06, 7.167458534240723e-06, 1.864507794380188e-05, 3.791600465774536e-05]\n```\n\nand $h = 3 \\times 10^{-4}$:\n```\n1-order: [2.9802322387695312e-08, 2.08243727684021e-06, 6.068497896194458e-06, 1.1827796697616577e-05, 1.9203871488571167e-05]\n2-order: [2.9802322387695312e-08, 4.470348358154297e-08, 1.4156103134155273e-07, 3.9674341678619385e-07, 8.754432201385498e-07]\n```\n\nFor the ViT, Adam with $h = 10^{-4}$:\n```\n1-order: [5.960464477539063e-08, 9.341537952423096e-05, 0.00017436407506465912, 0.0003153085708618164, 0.00037641823291778564]\n2-order: [5.960464477539063e-08, 3.9421021938323975e-05, 0.00014676153659820557, 0.0004404708743095398, 0.000798331166151911]\n```\nand $h = 3 \\times 10^{-5}$:\n```\n1-order: [5.960464477539063e-08, 1.2260396033525467e-05, 3.2086391001939774e-05, 4.717335104942322e-05, 6.285309791564941e-05]\n2-order: [5.960464477539063e-08, 2.4118926376104355e-06, 8.469447493553162e-06, 2.0730774849653244e-05, 3.071478568017483e-05]\n```\nWe will also add error bars to Figure 1 as you helpfully suggested.\n\nPlease let us know if you have additional comments or follow-up questions which we will be happy to address. Thank you!"}, {"review_id": "bJAf9zXM7h", "reviewer": "Reviewer_Fq9j", "summary": "The paper presents a unified theoretical framework that connects various memory-based optimizers. Through further analysis, the authors demonstrate how a memory-based optimizer can be reformulated as an equivalent memory-less update augmented with an explicit correction term.\nBy collapsing the historical dependence $F^{(n)}(\\theta^{(n)}, \\ldots, \\theta^{(0)})$ \nOnto $F^{(n)}(\\theta^{(n)}, \\ldots, \\theta^{(n)})$  and adding a first-order Taylor remainder \n$M^{(n)}(\\theta)$, the authors:\n\n* Show that momentum in gradient descent (GD) implicitly adds the penalty \n    $\\frac{h \\beta^2}{(1 - \\beta)^2} \\| \\nabla L(\\theta) \\|^2$, explaining its “flatter-minima” bias.\n* Derive a rigorous one-step and an $\\mathcal{O}(h^2)$ global error bound between the real and memory-less trajectories.\n* Apply the framework to AdamW and Lion. They prove that AdamW’s two-moment memory contributes an anti-regularization term, whereas Lion’s sign-based memory does not, offering a theoretical reason Lion usually generalizes better.\n* Provide empirical checks (MNIST, CIFAR-10, WikiText-2) showing that the memory-less approximations track the real optimizers more closely than first-order baselines, and that the predicted generalization trends indeed hold.", "questions": "* Your bound yields an $O(h^{2})$ global error, yet typical Transformer training uses  $h \\approx 10^{-4}\\!-\\!10^{-3}$.   Could you plot trajectory error vs. learning rate to illustrate where the approximation breaks down?\n* Optimizers such as AdaGrad or Shampoo employ a time–varying matrix pre-conditioner.  Do the fast–decay and Taylor arguments still hold when $F^{(n)}$ contains a changing matrix $P^{(n)}$?  A brief discussion (or lemma) would broaden the framework’s scope.\n* Appendix~G derives an extra noise-regularization term, yet the main experiments are full-batch.  A small-batch comparison of AdamW and Lion (e.g.\\ CIFAR-10 with batch 128) would directly verify this effect.\n* Section 4 suggests lowering $\\beta_{2}$ mitigates AdamW’s anti-regularization.   Could you provide a simple rule of thumb (e.g., $\\beta_{2} \\le 0.9$ when $\\beta_{1} \\ge 0.9$ that practitioners can adopt?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "__Strengths__\n* Presents a clear, unified framework that links optimizer memory to an explicit correction term, turning theory into a practical tool for understanding momentum and adaptive methods.\n* Delivers rigorous one-step and global \\mathcal{O}(h^{2}) error bounds with consistent, well-structured notation.\n* Includes an intuitive worked example (Heavy-Ball) and concise tables that map popular optimizers—AdamW, NAdam, Lion—into the framework.\n* Provides empirical checks on ResNet-50 (CIFAR-10) and Transformer-XL (WikiText-2) that mirror the theoretical predictions.\n* Offers a principled explanation for Lion’s stronger generalization relative to AdamW and reveals its connection to Signum.\n\n__Weaknesses__\n* All proofs rely on the small-step limit h→0; the approximation gap at realistic learning rates is not quantified.\n* While the theoretical analysis is strong, the experiments are restricted to small-scale benchmarks (e.g., CIFAR-10, WikiText-2). Larger or more diverse benchmarks (e.g., ImageNet, LLaMA-style pretraining) would strengthen the claims.\n* Comparative advantage of memory vs. memoryless formulations is discussed but not deeply quantified—e.g., what happens when the correction term becomes unstable or insufficient? This could benefit from clearer numerical illustrations.\n* The analysis focuses only on exponentially decaying memory; optimizers with long-range memory or non-exponential kernels (e.g., RMSprop or AdaBelief variants) are not covered.\n* Some mathematical expressions (e.g., nested sums in Eq. 9) are dense; a schematic diagram would improve readability.\n* Experimental plots lack error bars, limiting the reliability of the empirical support.", "was_revised": true, "final_justification": "Given the technical novelty of the work, the constructive nature of the rebuttal, and the fact that the raised concerns have been addressed effectively, I have raised my recommendation to support the acceptance of this paper.", "rebuttal": "Please accept our gratitude for your careful evaluation of our work. We answer each of your questions below.\n\n**Q1.** Thank you for your suggestion. Since we are unable to insert pictures, please refer to the list of $\\\\|\\cdot\\\\|\\_{\\infty}$ norms of the weight differences as a function of learning rates $10^{-4}, 2 \\times 10^{-4}, \\ldots, 10^{-3}$, after four full epochs. The weight decay was chosen as in the paper ($10^{-3} / \\text{lr}$).\n```\nAdam, 1-order: [9.332224726676941e-05, 0.0003106476506218314, 0.0005798707134090364, 0.0007627895683981478, 0.001006735023111105, 0.0013587186112999916, 0.0015425472520291805, 0.0017450712621212006, 0.0020120255649089813, 0.0022523682564496994]\nAdam, 2-order: [3.123283386230469e-05, 0.0001106560230255127, 0.00033054023515433073, 0.0004508025012910366, 0.0007957816123962402, 0.0010535456240177155, 0.001970142126083374, 0.001563912257552147, 0.0022364631295204163, 0.0025330185890197754]\n\nLion, 1-order: [8.964911103248596e-05, 0.0003637117915786803, 0.0005911120679229498, 0.0008356142789125443, 0.0012425384484231472, 0.0017505818977952003, 0.0017895549535751343, 0.0022158119827508926, 0.002560459077358246, 0.0030463594011962414]\nLion, 2-order: [2.2292137145996094e-05, 7.791072130203247e-05, 0.00027696078177541494, 0.0003433115780353546, 0.000695347785949707, 0.0009671555017121136, 0.0017019212245941162, 0.0012936657294631004, 0.0019430406391620636, 0.0027693919837474823]\n```\nThese numerical results indicate that the first- and second-order approximations become the same scale at the end of the range at $h=10^{-3}$ , but we do not expect the approximation to break down within this range of learning rates.\n\n\n**Q2.** Thank you for this important question. Usually, algorithms of the AdaGrad family use exponential moving averages of past gradient matrices (arXiv:2309.06497). For example, Shampoo can be defined as\n\\begin{align*}\n  \\boldsymbol{L}\\_t &= \\big(\\beta \\boldsymbol{L}\\_{t - 1} + (1 - \\beta) \\boldsymbol{G}\\_t \\boldsymbol{G}\\_t^T\\big) / (1 - \\beta^{t + 1}),\\\\\\\\\n  \\boldsymbol{R}\\_t &= \\big(\\beta \\boldsymbol{R}\\_{t - 1} + (1 - \\beta) \\boldsymbol{G}\\_t^T \\boldsymbol{G}\\_t\\big) / (1 - \\beta^{t + 1}),\\\\\\\\\n  \\boldsymbol{W}\\_{t + 1} &= \\boldsymbol{W}\\_t - h \\cdot \\boldsymbol{L}\\_t^{- 1 / 4} \\boldsymbol{G}\\_t \\boldsymbol{R}\\_t^{- 1 / 4},\n\\end{align*}\nwhere $\\boldsymbol{G}\\_t$ is the gradient matrix, $h$ is the learning rate. Because of the exponential moving averaging in $\\boldsymbol{L}\\_t$ and $\\boldsymbol{R}\\_t$, memory decays, and given sufficient smoothness of the loss this algorithm is indeed covered by our theory (similarly to Adam).\nWe did not include such algorithms in our examples for the reasons of space, and since a complete qualitative analysis of the resulting approximation is non-trivial, likely warranting a separate article. However, we will make sure to add a discussion of this in the relevant section, following your suggestion.\n\n**Q3.** Although mini-batch Adam is automatically covered by Theorem 3.2 and Corollary 3.3, our Section 4 is devoted to full-batch comparisons because the qualitative analysis of the mini-batch noise effects on Adam and Lion in this framework requires extensive calculations. We have largely completed them and plan to present it soon as upcoming work. A summary is as follows: while in the large-batch case memory of Adam with $\\beta\\_2 > \\beta\\_1$ always anti-regularizes, this is no longer true for smaller batches, and in fact increasing $\\beta\\_2$ can improve generalization if the noise is sufficiently large. We predict that the threshold of the batch size at which this shift happens is of the same scale as the critical batch size (arXiv:1812.06162). We are conducting extensive experiments verifying theoretical predictions in this setting. Empirical verification of the extra regularization by noise in the simpler setting of GD (with or without momentum) can be found in earlier works [22, 51] devoted to stochastic training: they have a different focus theoretically and different proof strategies, but our interpretation is consistent with their experiments. Thank you for pointing out this issue; we will add a discussion of this.\n\n**Q4.** In Section 2 of the supplemental appendix, we provide additional evidence that taking $\\beta\\_2 < \\beta\\_1$ can strongly regularize large-batch training on vision tasks, moving the model parameters to much flatter regions of the loss space. However, overdoing this can cause divergence. As a simple rule of thumb, we would suggest taking $\\beta\\_1 = \\beta\\_2$ (e.g., $0.9$) as a first conservative option for large-batch training.\n\nPlease let us know if we inadvertently missed something in your original review and/or if you have follow-up questions or suggestions that you would like us to further address. Thank you!"}, {"review_id": "ZRJv9ThpWv", "reviewer": "Reviewer_CQS8", "summary": "This paper introduces a general framework to study how the memory (which is usually the momentum term) affects the implicit bias. Specifically, for each algorithm, such as Adam and Lion, they propose a memoryless version by introducing a correction term. This correction term can be associated with a regularizer, which corresponds to the source of implicit bias. As an application, they show Lion does not have the kind of implicit anti-regularization induced by memory that AdamW does, which might be the reason why Lion performs better than Adam in practice.", "questions": "- In Lion-K's original paper, as well as shown in other papers, algorithms such Adam and Lion themselves have an implicit regularization. In this paper, they show that the memory has an additional implicit bias. Is it possible to combine them to derive the total implicit regularization effect?\n\n- Can you provide a simulation to see whether Lion penalizes more than Adam on the L1-norm?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n- The paper is well-written. The derivation of the memoryless variant and the way it relates to an implicit regularizer is well-presented.\n- The results on Lion and Adam are new and interesting. \n\n**Weaknesses:**\n- Probably more examples, such as Muon could be added.", "was_revised": true, "final_justification": "I maintain my original score.", "rebuttal": "We greatly appreciate your assessment and feedback. Your questions are addressed below.\n\n**Q1.** This is a very important point which we thank you for raising. By the original Lion-$\\mathcal{K}$ paper and the related work [56], full-batch AdamW and Lion, just like their first order approximations (sign descent), converge to a KKT point of the constrained minimization of the loss subject to $\\\\| \\boldsymbol{\\theta} \\\\|\\_{\\infty} \\leq 1 / \\lambda$. Our analysis suggests that AdamW is approximately preconditioned gradient descent whose loss is rescaled and perturbed by the function $\\\\| \\nabla \\mathcal{L}(\\boldsymbol{\\theta}) \\\\|\\_1 + \\lambda \\nabla \\mathcal{L}(\\boldsymbol{\\theta})^T \\boldsymbol{\\theta}$. The KKT points of the optimization problem are precisely those that satisfy the constraint and minimize this function, that is, $\\\\| \\boldsymbol{\\theta}^{\\star} \\\\|\\_{\\infty} \\leq 1 / \\lambda$ and $\\\\| \\nabla \\mathcal{L}(\\boldsymbol{\\theta}^{\\star}) \\\\|\\_1 + \\lambda \\nabla \\mathcal{L}(\\boldsymbol{\\theta}^{\\star})^T \\boldsymbol{\\theta}^{\\star} = \\min\\_{\\\\| \\boldsymbol{\\theta} \\\\|\\_{\\infty} \\leq 1 / \\lambda} [ \\\\| \\nabla \\mathcal{L}(\\boldsymbol{\\theta}) \\\\|\\_1 + \\lambda \\nabla \\mathcal{L}(\\boldsymbol{\\theta})^T \\boldsymbol{\\theta}] = 0$. Thus, these two frameworks are distinct but consistent with each other: one deals with the implicit bias of weight decay in versions of sign descent, and the other identifies the effect of memory. Intuitively, memory does not change the optimization problem but changes the way the algorithm solves it (and near the solution the loss perturbation is at a minimum).\n\n**Q2.** We have plotted how the one-norm behaves as a function of the epoch during the training run as in Figure 2(a), and will include the figure into the revised version of the work. (We apply exponential moving averaging (`pandas.DataFrame.ewm(alpha=0.1)`) to smooth out the curves.) Since we are forbidden from including pictures, we resort to a description here. For AdamW, the one-norm decreases rapidly during the initial ~120 epochs, after which it starts increasing again, peaks at around epoch 350-400, and further decreases. The peak values increase as $\\beta_2$ increases:\n\n```\nadam β₂=0.9: peak one norm=618.1 at epoch=389\nadam β₂=0.9342066775342432: peak one norm=802.9 at epoch=364\nadam β₂=0.9567123871891694: peak one norm=1017 at epoch=333\nadam β₂=0.971519641315642: peak one norm=985.8 at epoch=355\nadam β₂=0.9812618257713962: peak one norm=1188 at epoch=363\nadam β₂=0.9876715326055794: peak one norm=1190 at epoch=348\nadam β₂=0.9918886916921031: peak one norm=1174 at epoch=370\nadam β₂=0.9946633007687937: peak one norm=1231 at epoch=352\nadam β₂=0.9964888082657849: peak one norm=1214 at epoch=348\nadam β₂=0.9976898702999168: peak one norm=1250 at epoch=333\nadam β₂=0.9984800889170471: peak one norm=1277 at epoch=352\nadam β₂=0.999: peak one norm=1324 at epoch=358\n```\n\nThe one-norm of the network parameters trained with Lion does not contain such pronounced hills but rather has rapid significant jumps. Apart from jumps, the Lion one-norm curve stays below the Adam curves, reaching value ~650 by roughly epoch 300.\n\nPlease let us know if you would like to discuss any additional points or you have further questions or comments. Thank you!"}]

Author rebuttal:

Meta-review: This paper studies the impact of the dependence on past iterates (such as momentum), i.e. memory, in optimization algorithms.
In particular, it is shown that an optimization with memory can be approximated by a memory-less one by introducing an additional correction term, which can be interpreted as a perturbation of the loss.
The authors apply the proposed framework to analyze various optimization algorithms, including AdamW, Lion and Signum.

The paper is well-written and provides insights for understanding the role of memory in optimization algorithms, receiving unanimous support from the reviewers.
Decision: Accept (poster)