Understanding Accelerated Gradient Methods: Lyapunov Analyses and Hamiltonian-Assisted Interpretations
Authors: Penghui Fu
Zhiqiang Tan
Venue: Accepted by TMLR ()

Abstract: We formulate two classes of first-order algorithms more general than previously studied for minimizing smooth and strongly convex or, respectively, smooth and convex functions. We establish sufficient conditions, via new discrete Lyapunov analyses, for achieving accelerated convergence rates which match Nesterov's methods in the strongly and general convex settings. Our results identify, for the first time, a simple and unified condition on gradient correction for accelerated convergence. Next, we study the convergence of limiting ordinary differential equations (ODEs), including high-resolution ODEs, and point out currently notable gaps between the convergence properties of the corresponding algorithms and ODEs, especially regarding the role of gradient correction. Finally, we propose a novel class of discrete algorithms, called the Hamiltonian-assisted gradient method, directly based on a Hamiltonian function and several interpretable operations, and then demonstrate meaningful and unified interpretations of our acceleration conditions in terms of the momentum variable updates.

Published in Transactions on Machine Learning Research (03/2026)
Understanding Accelerated Gradient Methods: Lyapunov Analyses and Hamiltonian-Assisted Interpreta- tions
Penghui Fu
penglui@Cuhk.edu edw.
School of Data Science
Chinese University of Hong Kong, Shenzhen
Zhiqiang Tan
ston wutget.tttttttss...mm edu
Department of Statistics
Rulgers Universily
Reviewed on OpenReview: openrevvee... net/ forum? id= 0jug4MI #40
Abstract
We formulate two classes of first-order algorithms more general than previously studied for minimizing smooth and strongly convex or, respectively, smooth and convex functions. We establish sufficient. conditions, via new discrete Lyapunov analyses, for achieving ac- celerated convergence rates which match Nesterov's methods in the strongly convex and convex (not necessarily strongly convex) settings. Our results identify, for the first time, concrete sufficient condition gradient correction for accelerated convergence. Next, study the convergence of limiting ordinary differential equations (ODEs), including high- resolution ODEs, and point out currently notable gaps between the convergence properties of the corresponding algorithms and ODEs, especially regarding the role of gradient correc- tion. Finally, we propose a new class of discrete algorithms,, called the Hamiltonian-assitee gradient method, directly based on a Hamiltonian function and several interpretable oper- ations, and then provide specific interpretations of our acceleration conditions in terms of the momentum variable updates]
1 Introduction
Optimization plays a vital role in machine learning, statistics, and many other fields. In the optimization literature, there exists a striking phenomenon where after suitable modifications of first-order method the convergence guarantee can be improved, often attaining the complexity lower bound, with similar compu- tational cost before. Such acceleration has been widely studied since the seminal work of Nesterov (1983 which improves gradient descent for minimizing smooth convex functions. Examples include constrained optimization (Nesterov) 2018), mirror descent with non-Euclidean norm (Krichene et al. 2015), composite optimization with a proximable function (Beck & Teboulle 2009), primal-dual splitting [Chambolle & Pock
2011), stochastic gradient methods (Zhang & Lin 2017 Allen- Zhu 2018 and others.
Despite extensive rescarch, the scope and mochanism of acceleration remain to be fully understood, even including the original acceleration of gradient descent for smooth convex optimization. Typically, class of algorithms is constructed, and their convergence proofs are provided using suitable techniques. Among them, Lyapunov analysis has been prevalent approach for studying convergence properties of discrete algorithms, once those algorithms are defined. In fact, Nesterov (1983) used potential function or
!Code for numerical results is available https: btops://githhnn wwt. http//fpphhhcccoggg Firrstorrdrr methods refer methods using hunction rely the Hessian matrices their approximations.
gradlents only, second-order methods additionally

---

Published in Transactions on Machine Learning Research (03/2026)
Lyapunov function to establish the convergence of an accelerated algorithm, although Nesterov's later work turned to the technique of estimate sequences for studying gradient methods (Nesterov) 1988 2018). See Bansal& & Gupta (2019) and d' d'Aspremont et al. (2021) for overviews of Lyapunov- proofs for gradient methods. The central stop in Lyapunov analysis is to construct an appropriate Lyapunov function that is used to deduce the desired convergence. Recently, a promising framework for constructing Lyapunov functions systematically is via linear matrix inequalities (LMT) and semidefinite programming (SDP) techniques. The core idea is to transform the existence of a quadratic Lyapunov function into the feasibility of an SDP, which involves solving for positive definite matrix subject to linear matrix inequalities. Currently, there are two distinct methodologies under this framework, namely the performance estimation problem (PEP) and integral quadratic constraints (IQC). The PEP method is motivated by finding an objective function for which the given optimization algorithm has a worse performance, and has been adapted for Lyapunov analysis (Taylor et al. 2018 Taylor & Bach 2019: Upadhyaya et al. 2025). On the other hand, the IQC mothod motivated from a control-thcorctic perspective of optimization algorithms, as originally proposod in Lessard et al. (2016) and later extended by [Fazlyab al. (2018). More recently, the IQC method has
been leveraged to analyze family of Nesterov optimization methods by [anz Serna & Zygalakis (2021)
whose results are further improved by Dobson et al. 2025).
Although being a major technical tool for establishing convergence rates, Lyapunov analysis itself may not explain conceptually when and how acceleration can be achieved. Various efforts have been made for the latter purpose. For example, geometric formulations are proposed by coupling gradient descent and mirror descent (Allen-Zhng & Orecchia 2017), and by averaging two minimizers of an upper and a lower quadratic bound for the objective function (Bubeck al.] 2015; Drusvyatskiy et al., 2018). Another useful approach is to relate discrete algorithms to their continuous limits as ordinary differential equations (ODEs), obtained by letting the stepsize in the discrete algorithms lend to zero. ODEs are usually more traciable to study than their discrete counterparts by exploiting a rich set of analytical tools from continuous-tims dynamical systems and control theory. The analyses and propertics of the limiting ODEs can provide insights about those of the original discrete algsrithuss, for example, to facilitate the construction of Lyapunov functions for the discrete algorithms (Qian] 1999 (Su et al., 2016 Vang et al.] 2018 |unn et al.] 2020: [hhi et al., (022). Recently, stochastic differential equations (SDEs) are leveraged to understand the interplay between the learning rate, gradicnt noise, and gradient compression in distributed stochastic gradient methods (Compagnoni et al. 2025a bj. Conversely, ODEs can be directly formulated, and then their numerical discrelizations are studied (Wibisono et al.] 2016 Wilson et al. 2021 Sanz Serna & Zygalakis 2021). It has been argued that acceleration can be attributed to suitable discretizations of ODEs, such as the Runge Kutta integrator and
its variants Zhang et al.
2018
Dobson et al. 2025 and the symplectic integrators (Shi et al. 2019: França
et al. 2020 Muehlebach & Jordan 2021).
However, the approach based solely on ODEs is insufficient to account for whether acceleration is achieved. For example, for minimizing strongly convex functions, both Nesterov's accelerated gradient method (NAG- SC) and Polyak's 's heavy-ball method (HB) admit the same limiting ODE, but only NAG-SC achieves ac- celerated convergence while HB provably does not (Goujaud et al., 2025 To address this limitation, Shi eet al. (2022) proposed a new approach based on high-resolution ODEs. These ODEs are derived by relaining certain terms from the discrete algorithms that would otherwise vanish in the continuous time limit as the stepsize tends to zero. In particular, the high-resolution ODE for NAG-SC includes an additional Hessian term, which is absent in the ODE for HB. The Hessian (erm stems from the gradient correction term in the NAG-SC algorithm, which is defined as linear in the difference between the current. and previous gradients. By translating the Lyapunov analysis of high-resolution ODEs back to their discrete counterparts, Shi et al.) (2022) established accelerated convergence for NAG-SC and non-accelerated convergence for HB. Their anal- ysis suggests that gradient correction plays a crucial role in achieving acceleration. This raises two interesting questions. First, can we quantify the magnitude of gradient correction for achieving acceleration by discrete algorithms? Second, can high-resolution ODEs themselves provide insight into such a quantification?
We take direct approach to studying the scope and mechanism of gradient correction for acceleration of discrete algorithms. Our work has three main contributions, summarized as follows. See Appendix A for detailed comparison of our work and the literature, including LMI/SDP techniques, Sanz Serna & Zygalakis 2202I,, and Shi et al. (2022).
2

---

Published in Transactions on Machine Learning Research (03/2026)
We formulate two general classes of algorithms and establish sufficient conditions for when the algorithms achieve accelerated as well as non-accelerated convergence for the strongly convex and convex settings, respectively (see Sections concrete sufficient condition on the magnitude of the gradient correction term to achieve acceleration, thereby answering the first question raised above. Our proofs are based on hand-crafted Lyapunov analysis relying on neither connections with ODEs nor the LMI/SDP framework. See Section 6 for comparison of our and existing Lyapunov analyses.
2 and 3). Our results, for the first time, identify a
We study high-resolution ODEs derived from our classes of algorithms and compare convergence rates of these ODEs with those of their discrete counterparts. We find that high-resolution ODEs from our classes converge at the same rate, even though the corresponding discrete algorithms exhibit different acceleration behaviors. This provides new evidence that even high-resolution ODEs may be insufficient for explaining acceleration, thereby suggesting negalive answer to the second question above. See Section for more detailed summary.
To provide further understanding of the sufficient conditions on gradient correction, we propose a new class of discrete algorithms called the Hamiltonian assissed gradient method (HAG), which leads to specific interpretations for these conditions terms of momentum variable updates in both the strongly convex and convex settings. See Section 5.2 for a more detailed summary.
Before discussing our main technical findings, we introduce necessary notation that is largely adopted from Nesterov (0118) For a smooth and convex function f : IR" + IR, consider the minimization problem
min f(x). ZER"
(1)
Throughout this paper, we assume that the minimum in 11 is finite and attained, i.e., arg minzeR" f(z) + D. Denote by x² arg minzer" f(x) one of the minimizers, and f* f(x)). When I is strongly convex, x² uniquely exists, so that f* is always finite and attained. For m 2 1, let Jm be the set of functions that are R". Moreover,
convex and times continuously differentiable that f is L-smooth, that is, the gradient ff is L-Lipschitz continuous, [|V Vf(=)]] S L - x/| for v. y E R", where L > 0 is the Lipschitz constant and || denotes the Euclidean norm. For p > 0 we define STh F which further requires that f is j-strongly convex, that is, f(v) 2 ((x)+(V(())) for x, v,y E R". Let S FL n S For additional properties of smoothness and strong convexity, readers are referred to, for example, Appendix A in d' Aspremonn et al. (2021). Throughout this paper, we use denote a fixed step size in discrete algorithms.
define FL" C FFmm which further requires
+ 2/1
Our main technical findings are highlighted by the following two propositions, stated in a self-contained manner. Further interpretations of the technical results are provided in Section [.2) In the strongly convex setting, Proposition | can be deduced from Corollary D to give sufficient conditions for a simplified class of algorithms to achieve an accelerated convergence bound matching NAG-SC.
Proposition 1. Suppose that f: 1 + RR is function in St,L for 0 < a L. Let taxt be the iterates from the following algorithm:
Tk+1 Ik- sVx( + (1- cI/ IK-1) 82 s s(Vf(z)) vf(xx-1)), for k 2 1,
where Iı xo fzo); er and Đ scalor parameters. Then there erist constants Co, C1 0, depending only Ct and ō2, such that for 0 < < Co/ L, the iterates {xa} satisfy the bound
[(xx) / (L x x0 CIy(u))))
provided that c₁ > 2 and 82 J.
The conditions Proposition are terms of e and oq which controls the momentum term Fy Fh-1 and the gradient correction term f(V fx(x=))), respectively. To our knowledge, this is the first time that explicit conditions have been established for the acceleration of general class of algorithms in
3

---

Published in Transactions on Machine Learning Research (03/2026)
the strongly convex setting. In addition, Corollary indicates that when 0 - < an algorithm in the above form is proved to only have convergence rate matching the vanilla gradient descent. Previously, such comparative results were only known for two specific algorithms, NAG-SC and HB (Shi et al. 2022). For a numerical illustration, Figure | (a) presents the optimality gap by applying the iterative algorithm in Proposition | an ill-conditioned quadratic funcciio, with 0.1, z0 = c(1, 1), 4 = > 2, and varying 02. It can be seen that using &2 2 1/2 significantly improves convergence.
10a
re2 5 =0
18a9
13
1663
10
12
200
1080
500
1000
1500 2003
(a) f(z) - 5x 10
(b) f(x) = 20 Em expl(a]== b.)/20}
Figure 1: Optimality gaps in minimizing strongly convex and convex objectives with varying coefficients of gradient correction. Parameters a; 2200 and b, E R in the log-sum-cxp function are i.i.d. draws from the standard Normal distribution. The minimum f* of the log-sum-exp function is approximated by the minimum value that the algorithm achieves.
In the convex setting, Proposition can be deduced from Theorem 4 to give sufficient conditions for simplified class of algorithms to achieve accelerated convergence bound matching NAG-C (the analogue of NAG-SC in the convex setting).
Proposition 2. Suppose that f: R - R is function in Ft with L > O. Let {rx} be the iterates from the following algorithm
Ik+1
2% sV fzzz) 0xt1 Ik-1) ok+122 100-1122s((((F) s(Vf(zt) vf(xx=1)), for k: x> 1,
where F1 zo sVo( is scalar parameter; xk+1 (a+ 1)/0x+1, and fax 0} with op 1 is scalar sequence such that a₃ = Iik),, au+1(ax+1 - 1) I ag {ax+1/oR} is monotone (either non-increasing or non-decreasing) in k and lim ax41/a4 = -1. Then for 0 < I Co/L with Co = = 262-1 the iterates
20g
{ satisfy the bound
I x²1
f(xx) - ((
8/22
provided that 02 >
Proposition 2 is more general than the related result in Shi et al. (002 corresponding to specific choices of og k+r and a++1 = kir+1 with r 2 For a numerical illustration, Figure 1 (b) presents the optimality gap by applying the iterative algorithm in Proposition 2 to the log-sun-exp function, which is convex but not strongly convex, with
1, 2o 0, 2, and varying o2 Similar to the strongly convex case, it is observed that using & > 1/2 significantly improves convergence.
By comparing Propositions and we observe a common condition requiring 22 the coefficient for gradient correction s(Vf(xx)) V f))x,1)) to (asymptotically) surpass an explicit threshold of 2. Such a unified condition on gradient correction is identified for the first time for acceleration. remains an open question study whether this condition is also necessary for acceleration. After presenting the main results Sections we present. further numerical results to illustrate different. performances of the algorithms whose and 3

---

Published in Transactions on Machine Learning Research (03/2026)
parameters either satisfy violate the sufficient conditions for acceleration. It is found that algorithms with parameters satislying (or lying on the boundary of) these conditions exhibit better performance. Overall, the numerical results align well with our theoretical findings, All proofs are deferred to Appendix C
Asymptotic Notation. Given two sequences {ag} and {ba}, we write C C> 0 and K 2 1, such that ag S Cbb for & 2 K. Similarly, we write ag = (2(b)) ) if au 2 Cbb for k > K. We write a = (bb)) if both ag = [((b)) and ag = =Obb), and write ag ~ by if lim, /x/by- = More generally, for a set of pairs (g, h), we write g = (hh) or g S if there exists a constant
Obb.) ) if there exist constants
0 such that g S Ch for (g. h). Similarly, we write g = (h) or g 2 g 2 Ch for (g, h). We write g x h if both g S and g 2 h.
For convenience, summary of the notation used is provided in Table 3
(Appendix B
2 Acceleration for strongly convex functions
In this section, we first give background several algorithms for minimizing smooth and strongly convex functions. Then we study general class of algorithms.
2.1 Review of accelerated gradient methods
A basic method for solving I is the gradient descent (GD):
Øk+1 = Zk fVx(,,, for h 20
(2)
with an initial point To and stepsize In this section, study the case where Sr is smooth and strongly convex. See Section 3 for the case where f is smooth and convex.
For f St L.LL GD can be exponentially convergent in k, and the convergence rate depends on the condition number k L/μ. In fact, the GD itcrates (2 satisfy that for 0 < s & 2/ Nesterov 2018
L Li - =11
1 11-
2ps
f(æx) - fr
+ 1/K
When L/L, the rate is (17//))
2 for + co. When s 2/(L + μ); the rate improves
to (1=1/2) ~ (1 1 For both choices of the stepsize, the iteration complexity for f(xx) - f S is O (x which has linear dependency k.
Nesterov 1988 proposed an accelerated gradient method (NAG-SC) of the following form with additional extrapolation step: for h 2 0,
M/+1 = T3. xVf(sx);
(3a)
Tb+1 Vk++1 + o(1641 - yk),
(3b)
with zo = 9o and the momentum coefficient 1- where g us, a shorthand to be used throughout 14/9"
this paper. Equivalently, (3) can be expressed in a single-variable form:
Fh+1 VZ() + t -
as -VVV(()))VV for k > 1,
(4)
gradient descent
gradient correction
with To and z0 2VVi(z)) Compared with GD, the iterate (4) involves two additional terms, called Itv7
the momentum and gradient correction. For < s < 1/L, the NAG-SC iterates satisfy f(xx) f* = 0(11-7) When 1/L, the bound reduces to 0 (1111///m) 1//m))*))) )), and the itcration complexity lowered to O(VKlog( ()), with a square-root dependency on k. Drori & Taylor (2022) established that a lower bound for minimizing general Sh is f(xx) f 2( 1/vx)=**, where ) are iterates of any black-box
5

---

Published in Transactions on Machine Learning Research (03/2026)
first-order method Therefore, NAG-SC is optimal up to constant factor of 2 in terms of the iteration complexity.
There are several finst-order methods eractly reaching the lower bound (1 - 1//x) for instance, the information-therrett exact method (ITEM) (Taylor & Drori 2023) and tripl-mommntum method (TMM) (Van Scoy al. 2017). While ITEM involves time-dependent coefficients, TMM is defined with time- independent coefficients d'Apprmmott et al. 2021): for k 0,
Mk+1 Ih sV((s));
(5a)
2k+1 Vq 2 (f(Oo) + (1 -V)))kk
(5b)
2
2 zk+1 + (1-- I+ vūg yk+1,
Ik+1
(5c)
I+ /
with zo = 20. The sequence {2t} } in TMM 5 is auxiliary. See Appendix
C.1 for an equivalent form of (5)
containing {yk+1} and (m++1) only, where Zk+1 be recovered by
1 V 2k+1 + (1 (1- 1+ V
2k41
2 Mk+1
(6)
2
Nevertheless, { plays vital role in the existing analysis of TMM. Van Scoy al. (2017) showed that {*x} achieves the lower bound, i.e. f(zx) f O((1 2/) when
1/L. To knowledge, it
remains open question whether {# also achieves the lower bound.
In the Lyapunov analysis of NAG-SC in Bansal & Gupla 2019), & similar auxiliary sequence { as above is introduced by defining
+ V 2k+1 +
1+ V
2k+1
Uk++,
(7)
Vq
Vq
and the NAG-SC iterates in 3 together with are equivalently reformulated as: for k 2 0,
Uk+1 vVf(x))
(8a)
2641 Vi
+ (1 (1-v4)=H IR (((()) P
(8b)
V
(1- V 1+ yk+1,
Tk41 1+ vg 2k+1
(8c)
2n- See Appendix C.1 for derivation, provided for completeness. By comparing TMM with NAG-SC (8), they differ only in how #a+1 is defined in (5c) and (8e Bansal & Gupta (2019) constructed a new Lyapunov function to simplify the convergence proof for NAG-SC, and showed that { achieves the
with no 2n-
bound f(x)) f* = O((1 - 1/VR)** when == 1/L. By some additional arguments, similar convergence bounds can also be deduced for { and {xx}.
For comparison, we also mention the heavy-ball (HB) method PPolyk 1964), defined as
Fk+1 = 2z -Vf((() + oIx - Ik-1), for k 2
(9)
with o 1-v0 as in 3 Note that 99 differs from NAG-SC 4 only in the absence of gradient correction.
Following Shi al.
2002 algorithm
slight modification of the original method Polyak 1964
where the momentum coefficient o = (1 2 If s is small, the two coefficients (1 g² and I- are close. The original heavy-ball method, with the specific = 4/(VT. vTJ), achieves an accelerated convergence rate (1-1/// 22k for quadratic f (Polyak 1987). However, when minimizing functions in S that are not necessarily quadratic, it shown Goujaud
I+y7
(2055) that for any s and o, the worst-case
Black-box that prior knowledge of (e.g.. f quadratic) available except for the class belongs For Fl. the available information only the Lipschitz constant. L.

---

Published in Transactions on Machine Learning Research (03/2026)
Table Existing algorithms covered by our analysis
Method Formulation
Convergence
(10) or [11 with --
Accelerated rate by Theorem (ii-d)
NAG-SC
Accelerated rate by Corollary (ii) lim- iting case when 4
[44 with co L, C1 2, and C2 33/2
10
or [1] with = 1, 2
Accelerated rate by Theorem (ii-a) Accelerated rale by Corollary (ii)
TMM
with 60 = 2, 61 = 3, and C2 = v2
Non-accelerated rate by Corollary as limiting case when e1 2
HB
14
with co = 1, c = 2, and C2 1/2
convergence rate HB on Sh, L is no better than O((1 ((1))())))))) Therefore, HB provably does not reach an accelerated convergence rate on smooth and strongly convex problems. Goujand al. (2025) further shows that adding more regularity conditions f (e-g., restricting f within those with Lipschitz continuous Hessians) does not result in acceleration either. The failure of HB to achieve acceleration indicates that the gradient correction plays vital role in achieving acceleration.
2.2
Main results
We formulate broad class of algorithms, including NAG-SC and TMM as special cases, and establish sulficient conditions for when the algorithms in the class achieve acceleration, which is defined as reaching an objective gap of O((1 C/ C)) at iteration k, for a constant C > 0. Our work does not aim to find a sharp value of C or address the question of whether these algorithms ezaclly achieve the complexity lower bound corresponding to C (Drori & Taylor 2022). For an overview of prior work on acceleration covered by our analysis of the general class of algorithms, see Table
To unify and extend NAG-SC and TMM, consider the following class of algorithuns: for k 2
0k+1 = IK Vs fZK).
(10a)
2k+1 VV Ik 1 (V(())) + +(1 (1-VVg)=R
(10b)
TV4 Fk+1 I+ / 2x41 + (1- 1+ / 1k+1+
TV9
(10c)
with Zo = 20, where n, F 2 are three parameters which may depend on q. NAG-SC (3 or 8 is recovered by setting (n, 1,), and TMM (5) is recovered by (n,uT)) (1, In this way, the two algorithms differ only the choice r.
Equivalently, algorithm 10 can be put into singlo-variable form in terms of {xx), similarly to
4 for
NAG-SC: for t 1,
v(T + 4 vVf(xx)+ + - ((1-v/)) (xx xE-1) 1 + /q
<n - V (Vf(zz) -aame))-ffoff (z(=-))), (11)
Fh41
1 1+ /9
1 1+ /q
with To and The coefficients in the three termss for f(x), I& 0k-1, and s sVVf(zx) vf(===1)) are highly structured due to the translation from 10
fatur SV where Ç ç 1 (1-11) T) a shorthand used throughout this paper. I
The following result gives sufficient conditions for the convergence of algorithm 10 in the scenario where (1) T) are constants free of g (= ps)..
Theorem 1. Let f: R be function in Sh.r, with K Assume that n fuo Vo, and T 50 for some conslands (no, un 7o), free of pss).

---

Published in Transactions on Machine Learning Research (03/2026)
(i) There erist constants Co, C1 0, depending only on (no, Po. To), such that for 0 < S Cu fo, the iterates
of 10 salisfy
f(xx) 0 x* 1011 -ivVus))
(12)
provided that one of the following conditions holds:
(i-a) vo: To 0, vo + To, and 0 S 7/ MoTo
(i-b) vo To > 2 and 110 = -
(ii) There exist constants Co. C1 > O, depending only on (No, Vo. Tu), such that for 0 < < Co 12), provided that one of the following conditions holds:
the iterates
L
of 10 satisfy
(ii-a) vo: To 0, 1o + To, and n70 20
(ii-b) vo To 2 2 and To0 -
(ii-c) 1 < To and 710 > To:
(ii-d) 0 < To < and 7/0 2 TO-
The constants Co and C₁ in Theorem I can be explicitly specified, although the expressions are complicated and thus suppressed. See the proofs Appendix [ for details. Similarly, the explicit expressions of constants Co and C appearing in other formal statements in this subsection are suppressed well. The convergence bound (12) exhibits two types of dependency on K; determined by how large the stepsize is allowed. A similar phenomenon occurs in the comparison of NAG-SC and HB. Under the conditions in Theorem [[), algorithm 110p achieves usual convergence bound O(11 C/x))* for s x f2. resulting in an itcration complexity O lo)())). Under the conditions in Theorem [ii, algorithm (10) reaches an accelerated convergence bound O((1 - C/VR)* for s x F. resulting in an iteration complexity OVvRlog())) In particular, TMM with (No, P0. mo) = 1, is covered by condition (ii-a), whereas NAG-SC with (No, (O.T). = (1,1, is covered by condition (ii-d). It is interesting that for both TMM and NAG-SC, the choice of (Mo. Vo. To) lies boundaries of the acceleration regions identified in Theorem i Tn addition, although algorithm in class ([O) leads to exactly HB, there are close variations of HB which are in the class [1 with constant
(1), (, 7) and covered by the non-acccleration regions in Thcorem 11)
We next extend the constant case to a more general scenario where (1, are analytical functions of Vq. free of negative exponents like -1/2,, as stated in Assumption | In particular, (1) v) that are polynomials of qq satisfy Assumption
1/2,
Assumption There exist non-ncgative, analytic functions ni),, ii()) and f(-) in a neighborhood of 0 such that 17 = /)())) v ((v)) and t +( ((vg). Then n, v and 7 admit (convergent) Taylor expansions:
8
8 == Σ R(())',
1 = Σ m(VT's == Σ
(13)
1=0
1=0
when 0 g S 40 for some constant /0 > 0.
10 in terms of only the The following result gives sufficient conditions on the convergence of the algorithm constant coefficients, (7o, Po, To), in the expansions 13
4'The TMM choice, no = nn = 1 and To = 2, satisfies Mg * To and nl = MyTu// /2, lying on boundary of condition (ii-a) in
Thoorem j
The NAG-SC choice, NN = ry = nu = 1, satisfies in = To = and Tu, lying on the boundary of condition (ii-d)
in Theorem
Forr any constant 0 < up # 1, taking (g. ,. v²) = (0, 1, vD) in yields the update #1+1 = 24 I+ s vV f(xx)+ 1-20 (#x
Po
I+/4
- 1), which closely resembles HB as MD + and achieves non-acoelerated convergence by Theorem [ Ii-a).
8

---

Published in Transactions on Machine Learning Research (03/2026)
R Theorem 2. Suppose that f: +R R is function in Sh, with 0 μ L and Assumption 1 holds.
(i) For 0 < S Co tz (non-accelerated convergence), the iterates of 10 satisfy
12 with Co. C1 > 0
depending only on the functions (7,, U, f) (independent of q), provided that condition (i-a) in Theorem holds.
(ii) For < <SS Cot. (occelerated convergence), the iterates of 10) satisfy 12 with Co: C2 > depending only on the functions (ń, 1,,) F) (independent of q), provided that condition (i-aa) in Theorem holds.
Theorem 2 serves as generalization to Theorem cases (i-a) and (ii-a). When (n, r) depend g with leading constants My = To > 0 and 7/0 2 T6/ /2, which is not addressed by Theorem 2 the following result gives sufficient conditions on convergence of algorithm [10]. involving the cocfficients (1,
11, T1) of lincar terms in the expansions 13 However, in the degenerate case of constant parameters (1), T), the sufficient conditions in Theorem are more restrictive than those in Theorem
Theorem 3. Suppose that f: R + IR is function in Sy.tt with 0 < p S L and Assumption 1 holds with
Vo To > 0 and no T8/2.
(i) For 0 < S Co tx2 (non-accelerates convergence), the iterates of (10) satisfy (2)), with constants Co, C1 0 depending only on the functions (,5 (independent of q), provided that the Jollowing holds:
(i-a) 110- u-
- < 1), and 2mp <UTT + 2 (2 - 2)
(ii) For < 8 S Cot (accelerated convergence), the ilerales of 10 satisfy 12 with constants Co, C1 > depending only on the functions (q,,0, F) (independent of q), provided that one of the following conditions holds:
(i--a) n1o -2/ 11 71 < To ( - -1), and 20p1 2 Vn +
70 - 2));
(ii-bi) Too > 12/2 and v - < (To 1)70 1);
(ii-c) no th 2 and (To 1)To 11o 11
110 TO
All the preceding results are applicable to algorithm 10 or equivalently its single-variable form 11 with structured coefficients. To facilitate comparison and interpretation, we translate Theorem 2 in terms of
a single-variable form (14) below with unstructured coefficients. It remains an open question to directly analyze (14), for example, via the LMI/SDP framework.
Corollary 1. For f:R² R2 + R in Sh, with 0 < μ S L, consider the following algorithm! m
co - - - = = - (1- -
- 2
(14)
where 31 = Io ( co, C1,02 > are constonts independent of q Rí = =((4), R₂ = O(4), R3 = =([)) and h1 are analytic functions of / around 0.
I with Co. C1 0 depending only (Co, C2) and the forms of (R1, R2, Rs) (independent of q), provided of 4cp and co/4 < o Co.
(i) For 0
S Co anee-accelerated convergence). the iterates of [4] satisfy
(ii) For < s s 7 (accelerated convergence), the iterates of 14 sotisfy 12 only on (Co, C1, C2) and the forms of (R1, R2, Ra) (independent of 9) provided of > 4co and ch 2 Co-
with Co. C1 > 0 depending
To the best of our knowledge, Corollary for the first time, identifics concrete conditions for accolerated and non-accelerated convergence in general class of algorithus [4p. Moreover, the conditions are defined
oThe seemingly unnatural parameterization of the gradient correction coefficient. motivated by the HAG algorithm in
Section 5

---

Published in Transactions on Machine Learning Research (03/2026)
terms of two parameters e and c2, which control the momentum and gradient correction terms, respectively, while the other parameter co can be viewed as a non-essential rescaling parameter. We discuss these two conditions in detail.
First, the condition of 4co for the momentum coefficient due to implicit constraints in the coefficients
of 14h when translated from Theorem 2 in terms of (11). Although NAG-SC (3) and HB (0) can both be
put into [4 with parameters cp 1, C1 2, C2 3/2, and co 1, Cj 2, C2 1/2, respectively, their
convergences are not covered by Corollary | due to that the condition cî 4cg does not hold. Nonetheless, if viewing NAG-SC (3) and HB (9) as the limiting algorithms when C₁ 4 2, then NAG-SC (3) achieves
accelerated convergence by Corollary [ part (ii) while HB (9) achieves a non-accelerated convergence by
part (i). See Table for summary. We believe that of > 4co is technical and can be potentially relaxed
to C1 > 0. See Appendix A for a detailed discussion of the connection with related work in [anz Serna &
Zygalakis (2021).
Second, the condition oे 2 on or co/4 S oे co directly distinguishes between the accelerated or non- accelerated convergence. In other words, the leading constant C2v/o co/2 in the coefficient of gradient correction needs to exceed threshold ca/2.
For numerical illustrations of the theoretical results in Corollary we apply 14 to two quadratic functions on R2, similarly to Su et al. (016)), under different, parameters and step sizes. is particularly of interest to compare the performance of the parameter choices falling inside (or on the boundaries) versus outside the sufficient conditions for achieving accelerated convergence in our theoretical results. Specifically, we take Co fixed at 1, C1 1, (boundary) and 09 = 1/2,1 (boundary), 3/2. All remainder terms R1 R2; and R3 in 14 are taken to be O. Here G 1.2 corresponds to under-damping (cf < 4cg) and critical-damping 1/2, 1/2 corresponds to the leading constant of the gradient correction coefficient in [1] being 0, 1/2, 1 respectively. For NAG-SC 4 c1 = and C2 3/2, and for heavy-ball ( c = 2 and C2 = 1/2, but both with nonzero remainder terms R2 and R3. Hence, the algorithms tested are not exactly NAG-SC or the heavy-ball method.
(c 4oo) respectively, and
From Figure 2 we observe that critical-damping (c1 = 2) results in a faster convergence than under-damping (a = 1). Increasing 02 (gradient correction) also tends to improve the performance, but to a relatively small extent in the ill-conditioned case once C2 2 1. The error plots when 02 1/2 in the ill-conditioned case appear to be a sum of two oscillations. Overall, the numerical results are consistent with our theoretical results in the strongly convex setting. Better performances are observed from algorithms with more friction (i.c., a large e1) and larger gradient correction (i.e., a large 02).
3 Acceleration for convex functions
In this section, we first give background several algorithms for minimizing smooth and convex functions. Then we study general class of algorithms.
3.1 Review of accelerated gradient methods
Consider the unconstrained minimization problem 11 with f Ft. For stepsize < S 1/L, the GD
iterates {f(x)) non-increasing and satisfy f(xx) J* ||00 x=1 (2ks)) [ However, the ((1/k) rate is
not optimal. Nesterov (1888) proposed accelerated gradient method in similar form NAG-SC 3
for & 2 0,
3k+1 sVf(2x).
(15)
Th+1 = Mk+1 + Th+ (yk+1 yk),
with xo = yo and 0x+1 k/(k + 3). Compared with NAG-SC 3 the momentum coefficient 0++1 varies
with k, instead of taking a fixed value depending on the strong-convexity parameter μ.. For 0 < 8 < 1/L.
For stepsize 1/L < 2/L, the GD iterates {f(x)) still non-increasing but satisfies slightly different bound
0 ||ng-- 12) for the objective gap Nesterov 2018
ke(2-Le)
10

---

Published in Transactions on Machine Learning Research (03/2026)
18a
10"
10
10
1.ml.6. -5.
1. m5
43
m3.5
10
Errors for ill-conditioned 0.01).
(b) Errors for well-conditioned f 0.01).
10a
105
10
10a
10
10
10
10
10
m1.5
10
-1.5
202
400
600
800
1000
202
200
330
400
500
Itaradnn
Iteraiio
(c) Errors for ill-conditioned f 0.05)
(d) Errors for well-conditioned
0.05)
10
10
10
(6) -x]-1
20
10"99
20
41
(e) Errors for illconditioned f = 0.1)
(I) Errors for well-conditioned / (s = 0.1)
Figure 2: Minimizing strongly convex functions by 14 The left column for ill-conditioned f(x1, 22) 10-323 xf + x3, and the right column for well-conditioned f(11, 10-1x? + 23.. Fix Co The initial iterates are xo (1,1) and I 20 22 yus).
11

---

Published in Transactions on Machine Learning Research (03/2026)
the NAG-C iterates {f(z)) may not be non-increasing but satisfy
- - = - | - 1²
(16)
8k2
Comparod with GD, the itcration complexity for f(xx) f" I reduced from O(L/c) to O(vI/c) when
taking s = L/L. Notably, the convergence bound in (16) matches with the lower bound of black- box first- order methods for minimizing functions in FE when (the dimension of x) is relatively large compared with k (Nesterov 2018
The single-variable form in terms of } for NAG-C
15 is: for k 2 1,
TR+1 = Zb (V)()) + Ox+1(E
- TR-1)
x+t 8 -V
(17)
gradient descent
momentum
gradicnt correction
with 20, Ii 20 fxro) and 0k+1 +
The iterate 17 involves additional momentum term
and gradient correction term similarly in (4) for NAG-SC. Shi et al. (2022) studied NAG-C by relating 17] to high-resolution ODE (see Section 4.2 and obtained new result on the squared gradient norm: for stepsize 0 << < 1/(LL,
|| - x1 =
[1:0-~111
min OSiSk
[V(())
s2 ( <
(18)
The inverse cubic rate 18 cannot be obtained directly from 16
Morcover, Shi ct al. (2022 extended the 0k+1 = k/(k + r + 1) and 0s+138
coefficients in the ummentum and gradient correction terms in
respectively, and showed that the two bounds 16 and 18 remain valid for any r 2 2 and ,3 > 1/2.
The form of momentum coefficient 0 can be made more general. For instance, popular scheme is to set 0k+1 (ax - 1)/ak+1, where }ay} is scalar sequence to be chosen. It is known Beck 2017) that for any sequence {ax) satisfying a = (kk and a recursive conditior
30+1(0041 - 1) S a
(19)
the corresponding algorithm
15 achieves the optimal bound 16) For the well-known accelerated proximal
gradient method or FISTA BBck & Teboulle 2009), {ar} defined recursively as ai+1 = (1+ / 4x/)
with og = 1, i.e. 19 holds as equality. It can also be verified that {ax = (k+ +)/rr satisfies (19 IFF 2 2,
with corresponding x++1 k/(k+r +r
3.2 Main results
We formulate a broad class of algorithms including NAG-C (15) and existing variations (Beck 2017 Shi et al.
2022) and establish sufficient conditions for when the algorithms in the class achieve both the optimal bound (16] for the objective gap and the inverse cubic rate (18) for the squared gradient norm, similar to NAG-C.
To unify and extend existing choices of the momentum and gradiont correction terms related to NAG-C, we consider the following class of algorithms: for k 2 0,
Vk+1 Tk B&8V f (xx);
(20)
1b+1 mb V Ca.Vf(le f(xx) + 0 -k)),
where 2o yo. 0k+1 = =(a%- 1)/ou+1; and {aw), { and (ne) are three scalar sequences. The equivalent
single- vagialveriable form of (20) is for k 2 1,
Fk+1 = Fk - (7k + (Bk - B 8 ((xx) + 0xti(aK xx-1) O2tIBx-1 1 (VV(())) - (f(xx-1) 1));
(21)
starting from vip and Fi = z0 - (70 (an - 100-1))///ul (1 (1) (())) For an overview of prior work on acceleration
covered by our analysis of the general class of algorithms (20) or (21). see Table 2 To highlight the main
points, Proposition was stated in Section 1 for special case of 21 with constant * = 1 and Br ēz.
8Teh recursive condition 190 implies that 0441 5(1 V 4022 ok 1, and hence ag (kk).
12

---

Published in Transactions on Machine Learning Research (03/2026)
Table 2: Existing algorithms covered by our analysis
Method
akk
Jk+1
Convergence
NAG-C 15
(17
1
(k + 2)/2
k/(k +
Acceleration by Theorem Acceleration by Theorem
Beck 2017
1
1
any ag satisfying 19
(ax: 1)/ax11
Shi et al. 2022
1
(I + r)/r for 2
k/(k: r
Acceleration by Theorem
Motivated by the Lyapunov analysis of NAG-C in Su ct al. (0066), introduce the following throe-variabl
form of (20). Define 2g 0422 + (1 ag )yk for O, which is reminiscent of 5bb and 7 in the strongly
convex setting. Then 20 can be equivalently reformulated as: for h: 2 0,
M6+1 = Ih S3.VV (2x);
(22a)
2x+1
24 V (xx))
(22b)
xt+ ac++1
1
2x+1 + 1 (1- 0c++1
(1-1) yk+1:
(22c)
starting from 2o 20, where ā₂ = Byax + (1%- Be)as+1. See Appendix D for a proof. By definition, given [8c] and {ox > 0}, there is one-to-one correspondence between {7kk and (āx}: 7 (āi Bx (a ak+1))/aR+1. Hence, algorithm (20) or (22] can be considered to be directly parameterized by the three sequences {ax}, { and {āş]. The three- Shrce-variable variable form (22) is introduced mainly to facilitate our Lyapunov analysis, which is presented in Section The 2 update (22b) appears to differ from (10b) in the strongly
convex case, although (22c) resembles 10ch in the sense that the weight of žμ. or yı the update æe goes
to or respectively as Oi + 00 in 22c or
in (10c).
Our main result gives sufficient conditions when algorithm in both the objective gap and gradient norm, similar to NAG-C. We discuss interpretations of the conditions from the perspective of HAG in Section
20 or 22 achieves accelerated convergence
Theorem 4. Let f: Rd + IR be function in Ft. with > 0. Assume that the following conditions jointly hold:
(i) limg 3k 3 and lim 7kk = with 3 > 7/2 0;
(i) {ox > 0} salisfies that og = (2k), lime 0 = 1, a.+1 (a 1) S a
(Mi) (āx/ox} is monotone (either non-increasing or non-decreasing) in
21 or (22 satisfy the bound (66) for the objective gap and the inverse cubic rate 18 for the squared gradient norm.
Then for << Co/L with Co = 2-7/2 ^ > O, the iterates { from 20
For Theorem 4 the existence of the limits, limg 3, B, lim 7h = and lime 01+1/04 = 1, are introduced mainly simplify the sufficient conditions and may be relaxed even with the same Lyapunov function in our proofs. The monotonicity condition (āx (ax) may also be relaxed by using other Lyapunov functions. In the setting of 3g 8 and 7h 7, we have āz/az B + (y- 8)ax+1/ax Then the monotonicity condition is equivalent to either requiring 3 = without any additional constraint on {aa} or, if 3 * 7 requiring that {a4+1/au} is monotone. The latter condition is satisfied by both the linear choice ag = (k + r)/r and the iterative choice 0u+11 = (1 + /1 4a with og- = in FISTA.
We also point out that the conditions in Theorem are general enough to allow the absence of a limiting ODE for (20). As described in Section a necessary condition for the existence of limiting ODE of 20 is that limg k(1 0841) exists. However, provide an example where the conditions in Theorem are satisfied, but lim; k(1 ok+1) does not exist.
13

---

Published in Transactions on Machine Learning Research (03/2026)
Lemma 1. Consider the sequence {axt defined by alternating two rules: if is even,
+ rk/r Okk (1 (1+ V 40 1/2. if is odd,
with og = Then for uny r 2 2, condilion (ii) in Theorem 2: along {K3 {2k} and {k"} {2k + 1}, we have
holds. Bul limy k(1 ok+11 does not erist if
lim (1 0x++1 = 33/2 lim (1 0x*41) = r/2. +00
400+00
Lemma shows that accelerated convergence can be achieved by algorithm 20 independent of whether limiting ODE exists Hence, convergence of discrete algorithms may not always be explained from the ODE perspective.
For numerical illustrations the theoretical results Theorem we apply 21 to various objective functions under different parameters and step sizes. is particularly of interest to compare the performance of the parameter choices falling inside (or on the boundaries) versus outside the sufficient conditions for achieving accelerated convergence in our theoretical results. Specifically, we consider a quadratic objective f(x)
x² 2 + a and the log-sun-exp objective [(x) = p log 2000 exp((af< (xp((af=-b:)/r)) b:)/p), following Su al. (0016 The quadratic function strongly convex but with μ = 0, and the log-sum-exp function is not strongly convex. For algorithm parameters, set 7 1, 0++1 I+r+I for
1.2 (boundary) and 3 0.0.5
(boundary), 1. In particular, NAG-C corresponds to 2 and 3 = 1. In the log-sum-exp case, the minimizer has no closed form, so we approximate f* by running NAG-C, which converges fast in hundreds of iterations using a relatively large step size.
Figures 3 and present the traces the scaled optimality gap and the scaled squared gradient norm. In both Figures 3 and for fixed 33, increasing r = to r significantly accelerates the convergence of f(xx) - f* and minosisk [x:)))] In particular, it can be observed in Figure 3 (b), (d), and (f) that the bound minggigs fx;))l = 0(1/k²) may fail when r = since the product (k 1)3 minogsge fx;))) appears to increase in unbounded way as k increases. From Figure 4 for fixed increasing 3 markedly improves the performance in decrcasing f(xx) f" and minogigk | 1 especially when the step size is large as in Figure 4 (e). A similar beneficial effect of a larger 3 can be observed from Figure 3 in decreasing minogiss [x,)(= but the effect there is less obvious in decreasing f(xx) f*, where all algorithms exhibit oscillations during iterations, and the oscillations become stronger as the step size increases. Overall, the numerical results are consistent with our thcoretical results. Better performances are observed from algorithms with more friction (i.e., larger r) and larger gradient correction (i.e., larger (3).
4 ODE connection and comparison
As the stepsize vanishes to in discrete algorithm, the limiting ODE (if exists) can be studied under-
stand the behavior of its discrete counterpart (Su et al. 2016 Shi et al. 2022). We study the convergence rates of limiting ODEs of algorithms in Sections 2 and and compare them with the discrete results.
We briefly review how the limiting ODEs from NAG-SC [4] and NAG-C 17 exhibit interesting differences
from that the vanilla gradient descent (2), as discussed in Su et al. 2016). On one hand, by taking At 8 and It = (()))= = X(ks) for a continuous- trajectory X, = X ((), the limit of gradient descent 2 as 0 is the gradient flow
X V((x)) 0,
(23)
(23 has unique solution X,, which satisfies that ((x,) - fr < ||ح x² 1|2 (26) and when f ULzuS) L. [(x,) - f < 2utt (f(xo) - ))) ). By relating X, to Is (i.e., taking t = ks for small s), the former rate O(1tt) translates into ((1(kss)), which is exactly the discrete rate of gradient descent in the convex setting. The second rate O(e 2ur) resembles O((1 2
with X0) = zy- It is known that when f E ULSOFL, L.
9 A similar conclusion can be found for algorithm discussion.
in the strongly convex case. See Appendix for detailed
14

---

Published in Transactions on Machine Learning Research (03/2026)
10a
10a0
15a.
10a
10
10.
10a
10
10a
500
1500
2500
500
2000
2500
Haaradoo
Iteaaion
(a) Scaled errors (s = 0.05/|| |||))
(b) Scaled gradient norms (s = 0.05/||[|[]
10a
10"
10a
10
10
10
10a.
m0.5
m0.5
mm
S00
1000
1500
2020
2500
3505
500
1000
1550
2000
2500
3000
Iteredion
Iteratoon
(c) Scaled errors (s- 0.1/||A|]]
(d) Scaled gradient norms (s 0.1/1IAl))
10a
10a
30 --1
10
10
10
10a
10
10a
mm
500
1000
1500
2000
2500
3300
500
1000
1500
2000
2500
2000
(e) Scaled errors (s 0.3/|||||]
(1) Scaled gradient norms (s 0.3/||4|])
Figure 3: Scaled errors and squared gradient norms in minimizing f(x) = 1 Ax + v by 29 under
different step sizes, where A = BT B for E 5000x000, b E 5000 All entries in and are i.dd. draws from Ú0, 1), and ||^||| is the spectral norm of A. We take 7 = 1, o++1 ker+1 for 1.2 and 0, 0.5.
29
15

---

Published in Transactions on Machine Learning Research (03/2026)
10"
10
10a
10"
10
10a
10
mm
llbradon
Ittradon
(a) Scaled errors (s 0.5)
(b) Scaled gradient norms (s 0.5)
197
10a
10a
10'
54 (1))
10
10'
13"
mm
m.055
10
T-2
-1
T=2
200
400
800
800
1000
200
400
500
820
1000
(c) Scaled errors (s 1)
dd Scaled gradient norms (s 1)
10
19a
197
10a
10a
[w] B
16
10
10
10
200
(e) Scaled errors (s = 5)
(f) Scaled gradient norms (s = 5)
Fz-b
Figure 4: Scaled errors and squared gradient norms in minimizing f(x) = p log Σ e by (29 under
different step sizes, where A [a],.... a200) E R50x2000 b E R200 and p 20. All entries in and are i.d, draws from N(O, 1). We take 7 1, ok+1 - for 1,2 and 9 0.5, in 29
16

---

Published in Transactions on Machine Learning Research (03/2026)
2ps )nr for gradient descent in the strongly convex for O, which is similar to the discrete rate O(11 1+1/x) setting.
On the other hand, by taking At v and Ih = ((1)) = ((kvs) for a contimuous-time trajectory
X, = X(),, the limit of NAG-C 17 as s + 0 is for t > 0,
3 Vf(()) O,
X, 1
(24)
with initial conditions X(0) zo and (x) 0. When E Ur.SoF 24
I.
has unique solution X,, which
satisfies that f(X,) - f s 2 - 13//. The limit of NAG-SC 14
is
X, 2/ + VS(X.) 0,
(25)
with initial conditions X(0) xo and (0) = O. When f S 25 has unique solution Xx, which satisfies that f < - (f(xo) - f²). For a fixed t, X1 can be approximated by the discrete iterate 2e with t= t= kvs for a small 8. Using / = kvs, the former O(1/(²) rate translates into O(1((s))), which is
for NAG-SC, In these cases, the convergence rate of the contimuous-time trajectory X, x(t) matches that of the discrete iterates }
the discrete rate for NAG-C. The latter O(e-v()) rate matches the discrete rate
The overall findings of our study can be summarized as follows.
For minimization of strongly convex functions, the ODE convergence bounds do not directly inform the range of feasible stepsizes, which are crucial in determining whether acceleration achieved.
For minimization of cither strongly convex or convex functions, the gradient correction term vanishes in the (low-resolution) ODEs. Although this term is explicitly retained in high-resolution ODEs, these ODEs can still converge at the same rate with without it.
In conclusion, the convergence properties of limiting ODEs, including high-resolution ODEs, fall short of informing whether discrete algorithms achieve acceleration. Our work provides explicit convergence bounds for the low- and high-resolution ODEs through new Lyapunov analyses. These results complement and enrich the existing literature on the connections and gaps between discrete algorithms and ODEs.
4.1 Strongly convex setting
For strongly convex f, we compare the convergence of algorithm (1] and related ODEs. By taking At V and Fi.- ((4) = X(kv))) the limiting ODE of (14) as 0 is
X. ei VTX, + VXX))
(26)
with initial conditions X()) = zo and ((( = O. This can be viewed as a Newtonian equation of motion in a viscous medium in the potential field eof with co as the rescaling constant, To The damping coefficient is o /i, resulting from the momentum coefficient 1 1-c1 v in (14). For convenience, the three settings of 4co, of = 4co, or of < 4cg are referred to as over-damping, critical-damping, parameter 62 associated with the gradient correction vanishes. Nevertheless, for any smooth and p-strongly convex I and any cn, C1 > O, we show that the solution X, uniquely exists, and f(X,) converges to I* exponentially fast with a decaying rate proportional to va. To state the result, we use CP CP(1RR")) to denote the class of th contimuously differentiable maps from an interval I to R.,
under-damping, respectively. The
Proposition 3. Let f: R" + R be a function in ULZ I.I. with > O. Then the ODE 26 with initial has a unique solution X, 010,00);; Moreover, for any Co, Ci the solution Xt salisfies that s(X,) / O (((1))
conditions X X() xo and x(0)= -() for a conslant C = e1 -co Otherwise (either co 50 0 or c < 0), X, may fail to converge to x= as t + 20.
11
2
10 suffices to establish convergence for (26 for og then all other cases with co 0 be recovered by time rescaling.
The constant in Proposition 3 can be improved using the IQC methods (Sanz Sema Zygalakis 2021). However, our analysis is based concise Lyapunov analysis, and our goal not find the sharpest constant. See Appendix for details.
17

---

Published in Transactions on Machine Learning Research (03/2026)
The dependency on μ in the bound above is improved to vd, compared with the 2(t)) bound for gradient flow (23). A direct translation by L = 8 suggests that discrete bound of ( may be expected for suitable discretizations of (6)) as opposed to O((1 Cus))) for gradient descent 2 However, there are notable gaps between such results suggested by ODEs and our results for discrete algorithms. First, the bound Proposition 3 only requires <o, 61 > 0, which much weaker than the over-damping condition of > 4cg in Corollary | The condition oî > 4cg may be only technical and can be potentially relaxed. does not directly inform whether 8 x 1/L (equivalently q x 1/k) or p/L² (g x 1/x²), corresponding to different orders of time interval in discretizing the ODE. The former leads to acceleration while the latter does not. Third, the gradient correction term from algorithm (14) vanishes in the limiting ODE 266 so that the ODE does not capture the effect of gradient correction.
Second, the bound -(1-Cyuss)
To complement the preceding discussion, we study the high-resolution ODEs for NAG-SC (4 and HB 99 which are proposed to reflect the gradient correction or lack of the two methods (Shi et al. 2022). The high-resolution ODEs are derived by retaining ((v3) terms that would otherwise vanish in the limit of
0. By laking Al = v and Fy X(4) ((kv/), the low-resolution ODEs for NAG-SC (4) and HB
9 are the same equation in 25 The high-resolution ODE for NAG-SC is
X, 2 + VsV
(1 + Vf(,) =
(27)
with initial conditions (() = zo and x() = - 2/a V (a The high-resolution ODE for HB is I-vus
X, 2/ (1 + V(x) 0,
(28)
with the same initial conditions. For NAG-SC, the gradient correction results in an additional Hessian term, v in (27). However, the convergence rates of those two high-resolution ODEs are the same. The following result is qualitatively similar to Theorems 1 and 2 in Shi el al. (2022). but involves sharper rate due to a new Lyapunov analysis.
Proposition 4. Let f: R" R be function in ULZ H.I. with p > O. Then each of the ODEs 27
and (28) with initial conditions X() = zo and (() = -VV3V((2o)/LL + /as) has a unique solution X, E CCO oo); R"). Moreover, for both ODEs, the solutions X, sulisfy that s(Xi) S < Vie-vas
where the constant Vo = (1+ (f - f+) + +llVT( - x*) v8 l-vis v [(x))] for (27) and Vo =
I+vus
(1 + (Ja) - (t) 1 x²) I+/as
2/- VS(=o)]2 for (28).
Unfortunately, despite explicitly incorporating the gradient correction (or not), high-resolution ODEs do not exhibit differences in convergence rates and therefore fail to capture the effect of gradient correction.
4.2 Convex setting
For convex f, we compare the convergence of algorithm (21 and related ODEs in the setting where Yh = 3x = 8, and o% = ktr 12 By rescaling the stepsize s to 8/7, the parameters and B can be reset to 1 and
3/7 respectively. In this setting, (21) reduces to the sub-class in Shi et al. (2022), with two parameters r and 3/y:
B
Jk+1 = Fh sVf(x)) + OR+I(TE 1K-1) Tk+1
s (VF(x)) - (f(xx-))),
(29)
where 0k+1 = 0=-1 & for t > 0,
By taking At = V8 and I3 = xx(t)) = (kk/)), the limiting ODE for 29 is
01+1
k+r+1
X,
X, VS(X) 0,
(30)
with initial conditions (() = 20 and (0) = 0. This can be viewed as a Newtonian equation for a particle moving in the potential field f with friction. The damping coefficient r+1 t resulting from the momentum
coefficient d+I Su et al. 2016)) showed that if f U1>oFF, 330 with the specified initial conditions has
12 general sequence {o4), algorithm 21 may admit a limiting ODE, as shown in Lemma
18

---

Published in Transactions on Machine Learning Research (03/2026)
unique solution X (10, n C (O. oo): R*). Moreover, the convergence of X2 exhibits phase transition at = 2, the choice in NAG-C 15 TI' r 2 2, then f(X,) - f = 0(1/(2). But if r < 2, the rate O(1/t) may fail as illustrated by counterexamples For ag = k+r it can be directly verified that the recursive condition ax+1(ax+1 - 1) f a in Theorem 4 holds if and only if 2 2. Therefore, the condition
on the momentum term for acceleration of (29) is well captured by the limiting ODE.
The ODE 30 however, does not reflect the parameter 3/7 associated with the gradient correction in which is similarly observed in the low-resolution ODE (26) for algorithm (14 in the strongly
algorithm
29
convex setting. The gradient correction term, of order O(vE), can be incorporated in a high-resolution ODE
(Shi et al.
2022 By taking to = (++1vs and tx = to + l / for algebraic convenience, the high-resolution
2
ODE for 21 is for 1 to > 0,
1 X1 L (() + (1+ (r 11+1 Vf(X)) 0,
X
(31)
2t
with initial conditions ((t)) = zo and ( established the existence and uniqueness of a solution X, E o0); R²). The general case with r 2 2 is
=
When f E ULSoFf and r =
r 2, Shi et al. (2022)
beyond the scope of this paper. If a solution exists, the following result gives convergence bounds of (31 for
both r > 2 and 2 via new Lyapunov analysis. Shi et al. 2022 provided similar bounds only explicitly in the case of r > 2.
Proposition 5. Let f: + R be a function in F2, Suppose that Xt is solution to 31 with initial conditions X(to) = To and (to) = - ( I 2 2 and $ 7 > 0, then there exists a time point 1 1o with / / depending only on r and 3/7, such that X, satisfies the bounds:
V/ p
|VS(X1)1 - (
VVe (88(B-- - +5)
[(x.) - -
inf 4SSS!
In addition, if 2 2 and 3 = O, then the first bound still holds. Here Ve, is the value that the continuous
Lyapunov function takes at t1: V = (t+ (v+ ( (() f+)+ ++ov= 21lr(X, (()
+ +t(X++
βy ((x))) where C C= if 2 and C 2
If we replace by = + Kv3 \ then the first bound above translates into the accelerated bound ((1(ss))) the objective gap in (16) and the second becomes ((1/(>?1²)) the squared gradient norm as in 18). These two bounds above are exactly the continuous analogs of the associated bounds for algorithm (29 However, compared with the condition 3/7 > 1/2 in Theorem A the condition in the continuous ODE setting is much weaker: B/7 is allowed to be arbitrarily small, and even 0 (no Hessian term) if only the ((1/t)) rate for the objective gap is desired. The latter case corresponds to a discrete algorithm without the gradient correction, similar to HB (9) Therefore, even when a Hessian term is included as a continuous counterpart of the gradient correction, the convergence propertics of the high-resolution ODE are currently not fully matched by those of algorithm (29). This remains to be further studied as an open question, as also mentioned in Shi et al. (022)) Section 5.1.
5 Hamiltonian-asister interpretation
As observed in Section the low-resolution and high-resolution ODEs do not fully capture the convergence properties of the algorithms studiod. Alternatively, we directly formulate broad class of discrete algorithms, HAG, based on a Hamiltonian function with position variable and momentum variable, and demonstrate that the conditions from our convergence results in Sections 2 and 3 can be interpreted through HAG in a unified manner in both the strongly convex and convex settings. This development is motivated by related
formulation of Hamiltonian-assister Metropolis sampling (HAMS) (ong & Tan 2023 2022
1eee the proof of Proposition Appendix
F.4 for an explicit expression for f1-
19

---

Published in Transactions on Machine Learning Research (03/2026)
5.1 HAG: Hamiltonian-assin gradient method
For / E Ft, consider the following unconstrained minimization problem:
H(x, u) - : f(x) f(x) 1 +
min R,
where (xr, can be interpreted as a Hamiltonian function (or total energy), with x position variable and u a momentum variable. The above problem is equivalent to the original problem (1). If x and are updated separately, then there is no possible improvement compared with solving ( directly. However, we
show how x and u can be updated in a coupled manner to derive a rich class of first-order algorithms, which
include perresnttatie algorith from the classes (14) and (21) studied in Sections 2 and 3
Gradient descent with a linear constraint. Given initial points (zo, 20), consider minimizing (or decreasing) (xx, u) subject to a lincar constraint x 8u Zg - -up for some 8 > 0. By substituting +un the problem with respect to x becomes minimizing (or decreasing) f(x;; zo, un) [(x) +
20 |I 20 + svoll? Consider updating 2n by gradient descent with stepsize - 1+0z, which, by
8²
the standard characterization of gradient descent, is equivalent to minimizing quadratic surrogate function of f at zo (with surrogate smoothness parameter being for f) as follows:
F arg min (VI(z)), x -xo) + |a xo11² + 25 10 - xo + 8uoll2
Then un is updated by solving Iı - dun = -0 duo.
The resulting update is
8²
d
F To
vf(o))
1+ 82 No:
1 82
5 ff(o))
U1 un
1 82 Up.
1+8
The function f(r; Fo, un) has a smoothness paramoter L = L + F.. If < 8 S 1, then L, s 2/2 2 and s < so that the above GD update is well-behaved and f (as well as H) is non-increasing (see the footnote
Momentum negation and extrapolation. The above update can be repeated on (æ1, uz), but the constraint x - du = xj - dun = xo - ōug will remain the same, so that all subsequent updates also satisfy the same constraint and, in general, cannot converge to a minimizer of H(x, u). To resolve this issue, we negate u at the beginning of each iteration. In other words, given (2o, uo), we first negate uo to Uu, and then implement the above update. The negation of does not change the value of H, but keeps the constraint changing from iteration to iteration.
An illustration is provided in Figure 5 For 1-dim x, the linear constraint becomes a straight line in R². x² When f(xx) -² the level sets of (xr, = of 2 are circles, and the gradient descent update is exactly the minimizer along the line. Then the update without negation gets stuck after the first iteration. Negating the momentum changes the linear constraint, and then the updates keep moving toward the minimizer (0, 0).
When f(x) 2², the level sets of H u) x² + o are ellipses, and the gradient descent update is not exactly the minimizer along the line. Nevertheless, without negation, all the iterates will stay the same line, hence failing to converge to the minimizer (). The momentum negation is also essential to the HAMS algorithm and related under-damped Langevin sampling algorithms, where negation of the momentum is required to achieve generalized reversibility (Neal 2011 Song & Tan 2022).
x²+
In addition, we introduce an extrapolation step before the negation of uo for p 2 0. This leads to the following update given the initial points (æo, uo):
[1 + p)8²
(1+ p)d
Z0
1 82
V f +
1 82 No.
(1 p)8
1 P
01 -1g
(xp) +
1+ 82 Ug.
1 82
20

---

Published in Transactions on Machine Learning Research (03/2026)
momentum
position (x)
positio (x)
(a) f(x) 2 without negation
(b) f(x) a with negation
momanuum (1)
momenium
position (x)
position (x)
(c) f(x)
-² without negation
(d) (x) x² with negation
Figure 5: An illustration of the gradient descent with linear constraint and the effect of momentum negation when x E R. The first two iterates are plotted without or with negation, for f(x) x² /22 in the first row and f(x) x² in the second row. The initial point is 1) and the global minimizer is (0,0). We fix 8 = 1/2. The black solid circles and ellipses correspond to different level sets of the Hamiltonian functions.
By setting (1+p)62 14d= and 1ife, the above can be put in clean form
3 To a V (xoo + Vabuo,
u0 f + bug-
The parameters p) can be determined from (a, b) as 8 = aab and p= p-a+b-1.
Gradient correction. The above updates of æ1 and in are parallel, so that in uses only the gradient information Fe. but at the newly updated 21. To exploit the gradient information at ø1, we incorporate gradient correction into the update:
I = In aV (x)) + Vabuo.
#1 240 vobV + buo (V)((z))- vx())))
for some scalar p. Lastly, we allow a, and ø to vary from itcration itcration and consider the following class of algorithms, called Hamilloniannassiiseee gradient method (HAG): for k >
Fk+1 = Fy. an (((x)) + v Varbaue
(32)
Us+1 = -4 - (xx) + beu Ox (V(((())-1) - vf(xx)),
21

---

Published in Transactions on Machine Learning Research (03/2026)
starting from (Zo, un). Notably, the overall contribution from gradients remains unchanged in the update for 14+1- Instead, they are re-weighted:
uk+1 = (bk= 1u ((V agbb 26 V + V V
(33)
ro-weighted gradient
The larger de i8, the larger weight. is assigned to the new gradient V(((44))).
To facilitate comparison with algorithms in Sections 2 and 3 the HAG algorithm 32 can be put into varile-variable form involving } only (sce Appendix for k 2 1,
Tk+1 = Ik 0(0-11
ak-11/
agbr
+ ax
Vf(IN) + (bx-1 (b2-1-1) V
agbb
(Ix - xk-1)
Ok -
aR bk-1
OL- - -0 1k-11
On
(Vf(Ix) (FR--))) (34)
Ok-1bb-1
starting from 2o and I1 = z - ag V + Vagbiug. The parameter { only appears in the gradient correction in (34), and in the case of agbb being constant in k, the parameters {az} and {br} fully determine the gradient descent and the momentum terms respectively. For convenience, the term of 24 - -x-1 is still referred to as the momentum term in single-variable forms, which is not to be confused with the momentum variable Ug.
5.2
Interpretation from HAG
32 or 34 are general enough to represent various algorithms studied in Sections 2 and 3 by choosing the parameters {ox], {bx} and {6x} accordingly. We examine our convergence results from the HAG per- spective and obtain unified interpretations of sufficient conditions for achieving acceleration in both strongly convex and convex settings. Our findings are summarized as follows.
HAG
The parameter O acts as a re-scaled stepsize s. The parameter by, which controls the momentum term the single-variable form, has a leading constant 2, and the gap - by is 22 (q())) with = us or (()) in the strongly convex or convex setting, respectively 14 In terms of (ōx. Pk) ) in the HAG derivation, this indicates that ôg ~ /
The 2 and 1-pk ~ b- Therefore, 6ş is of order / (comparable to At in deriving ODEs for NAG-SC and NAG-C), P has a leading constant. (indicating symmetric extrapolation), and the gap 1 Pk is (VV or ( in the strongly convex or convex setting.
The parameter 6 is of order v and controls the gradient correction, such that in the re- weighted gradient for the momentum update (33), the new gradient V (((++)) fully dominates with its weight greater than the total weight, whereas the old gradient Vf(xx) has a negative weight. The boundary case of a zero weight for Vx(x)) is also allowed in the strongly convex setting. Such heuristic interpretations are not feasible from the single-vare variable forms.
Currently such interpretations are derived from convergence results for classes of algorithms 14 and It remains an interesting question to analyze HAG directly and study further implications.
22
Strongly convex setting. For f E Sl we set
as a== Co +0(Vg)ss, by = ===bb2-- - O(gg,
o, = ==== (c2 +
where Co, C1 02 > 0. Then HAG 34 reduces to 14 exactly:
Fk+1 = Fs 2a ( + (b 1) -n- ( a) (((n-)))
24 (co (1= (1- xt-1)
(35)
(02//o 8o - -( Vf
The orders, v and 1, be match cach other, because the accelerated algorithms and their continuous limits are linked via = /s's in Section 4 and hence /s can be viewed to be in the order of è as > 0 or k co.
22

---

Published in Transactions on Machine Learning Research (03/2026)
In the following, interpret the conditions in Corollary through HAG.
The parameter (2 + +(Vg))s plays the role of a re-scaled stepsize The parameter = 2-c /4+
controls the momentum term (Ix - -x--1) in 335. The leading constant of b is 2, which ensures the existence of a limiting ODE as s + 0. In terms of C1. Corollary requires the condition of > 4cv, which as mentioned earlier may be potentially relaxed, for example, to ci O. This would lead to a condition b 21 (v))) as In terms of (6, p) in the HAG derivation, the preceding discussion also gives
= aa/b = 20==2v20 5
--p=2-b- a= 22 ((v9))
(36)
We observe that 8 is in the order of v5, similarly as At in deriving the ODEs (5 and 26 and p is close to (symmetric extrapolation) but with a gap being P(yus))
The parameter (ce + ((v))v controls the gradient correction (VS(x*+1) vf(())) in 335 The
re-weighted gradient in the momentum update (33) for ug+1 becomes
(Voo - c2 + + + +VV
(37)
For accelerated convergence in Corollary [ the condition ož 2 co indicates that the new gradient V (f(4411 fully dominates with its weight, c2v5, no smaller than the total weight veys, whereas the old gradient ((())) has zero or negative weight. For non-accelerated (sub-optimal) convergence Corollary the condition co/4 v c2 < co indicates that both the new and old gradients have positive weights, but fz
contributes no less than (=x) Interestingly, such interpretation cannot be obtained from the single-
variable form 14
35 even though a similar re-weighted gradient can also be identified there
Convex setting. For f E FF,, we set
Co by
by = 1 + Ok+2, ak
s, Øk = C2V3,
(38)
where co, C2 and, as before, 0k+1
ax-1 for some sequence {ax}. Then HAG 34 reduces to ax-1
Tk+1 = Co ( bk- bk
+ 1 1) sV sVf(z)) + ORtI IK-1) (oevoo co b
s(Vf(rx)
vf(xx-1))
(39)
which falls in the class
21 with Th and 35 varying in k, whose convergence property can be readily deduced from Theorem We choose ag varying in le such that agb, is constant in k, mainly to simplify the coofficients from 33
Given any } satisfying a 12kk) and aat1 + O we have a++1 at
0x-1
O by
1 2 0(2), ax = ee (co + (/ and the preceding HAG algorithm (39
is further simplified
to
Th+1 = T2k (o + sV SV +om 2k-1) covvo - co -o()) s s(Vf(xx)- vf(xx1)),.
-
(40)
which resembles algorithm 35 in the strongly convex setting, in all the leading constants involved. Algorithm
40
can be put into
21
with % + y = Co and 3% + 3 02v/00 -. Note that (39 or 40 is more complex
18
14
or
35
it seems reasonable to consider the weighttt gradient as
(co (L))))
co +OW
(c2voo + ((V)))VV((L)) + (-c2v +O(7))sV/(a(--)
However, the condition oj 2 ca indicates that the weight of ( is no smaller than cco, whereas the weight of V f((=-1) is larger than re,, with total weight cos. Therefore, the conditions bear no meaningful interpretations.
23

---

Published in Transactions on Machine Learning Research (03/2026)
than 29) with constant 7% and Bg studied in Shi et al. (2022) and (ii) in Theorem 4 through HAG for the choice 04, k-r
In the following, we interpret conditions (i) The technical monotonicity condition (iii) can be verified for this specific choice (see Appendix for proof).
Similarly to the strongly convex setting, the parameter as = (cu + s plays the role a re-scaled stepsize 8. Moreover, the parameter by = + 0k+2 controls the momentum term (aq - xą-1) 440) and has its leading constant being 2, which is necessary (but not sufficient by Lemma ! for a limiting ODE to exist as - O. For the choice 0₃ ker and dx+11 x the recursive condition 04+ (a 1) S a
is equivalent to 2 2. Then it implies a condition 2 - by = (r + 1)/k - O(1/k²) = 12(1k) as & + oa (or 1/ke2 + 0). In terms of the deeendenn (6k, pk) in HAG, the precoding discussion gives
1 /000 O(s), 1 Pk by - an ( 2 c05
6% = V
(41)
We observe that dy is in the order of V3, similarly as At in deriving the ODE 244. and Ps is close to 1 (symmetric extrapolation) but with gap being ( The conditions, (36) and (11. for the strongly convex and convex settings respectively, are of similar forms, with v v and exchanged with each other.
The parameter Φu = =2v/ plays similar role of controlling the gradient correction term (=(
in 4. as does 6 -(c2 + +(vD))& in the strongly convex setting. The re-weighted gradient in the momentum update 33 for u is similar to 437; 1
-2)
With = co and 3 = =2/00 - 2, the condition 8 > 7/2 in Theorem 4 reduces to oj > co, which indicates that the new gradient (xx++1) fully dominates with its weight, C2vs, greater than the total weight vlus, whereas the old gradient V/(ws) has negative weight. This is the same as the condition, og 2 co, for
accelerated convergence in the strongly convex setting except that the boundary case og = co excluded here. As discussed earlier, the single-variable form 40) does not admit meaningful interpretation for the re-weighted gradient.
6 Outlines of Lyapunov analyses
We outline Lyapunov analyses to prove the convergence results for the discrete algorithms in Sections 2 and See Appendix D for our Lyapunov analyses for the convergence of ODEs in Section 4 Compared with existing ones, our Lyapunov functions are constructed to handle more general algorithms and ODEs or to achiove more concise analysis and sometimes sharper results. Before giving the outlines of our analysos, we summarize the comparison of Lyapunov analyses. The comparison restricted among analytic Lyapunov functions, excluding those constructed by the LMT/SDP framework, which require additional numerical
solvers (Lessard et al.] 2016 Fazlyab et al.) 2018 Taylor et al. 2018 Taylor & Bach] 2019
Sanz Serna &
Zygalakis 2021 Dobson al. 2025).
Strongly convex setting. We construct the discrete Lyapunov 43 to establish the convergence of algo-
rithm 10) including NAG-SC and TMM as special cases. The auxiliary-energy term ul|zx411 1 || [| 2 in (43)
is also used in Bansal & Gupta
(2019) for NAG-SC and in d Aspremont et al. (2021) for TMM. However,
the potential-energy term in our Lyapunov is (2x) whereas the one Bansal Gupta (2019) is {ye)-
The potential-cnergy term of the Lyapunov in d'Aspremont et al. (2021)
{*x) like ours, but is not
lower-bounded by [xxx)_f so that their analysis only establishes the convergence for {za]- In addition,
compared with the analysis of NAG-SC in Shi et al. (022)) our Lyapunov function 43 has fewer terms,
and our analysis is much more concise.
Our continuous Lyapunov function to analyze the class of low-resolution ODEs 26 for Proposition is extended from the one proposed in Wilson et al. (2021) for (co, c1) = (1,2) (i.e., the low-resolution ODE of NAG-SC). Furthermore, we construct suitable Lyapunov functions analyze the high-resolution ODEs of NAG-SC and HB. Compared with the ones used [Shi et al. (002),, our Lyapunov functions lead to a sharper convergence bound for NAG-SC and HB (Proposition
24

---

Published in Transactions on Machine Learning Research (03/2026)
46 to establish the convergence of (20) equiva- lently 222 including those in Beck (017) and Shi et al.
Convex setting. We construct the discrete Lyapunov
(2022) as special cases. The auxiliary-energy term
(2022) for (29 a sub-class of 20 with 74 = 1, 3x = 3/y,, and ag: = (k r//r for r 2 2. However, the potential-energy term in our
1
xx
112/2 in 46) is motivated by Su et al. (2016) for NAG-C and Shi et al.
Lyapunov (46) differs from the related ones [uu et al. 2016 and [Shi et al. (2022). Moreover, [Shi el al.
(2022) analyzed the three cases, r = and / S 1,
and B > 1, and > 2, separately. It scems difficult
extend their case-by-case analysis to cover the more general results in our Theorem [
The contimuous Lyapunov function for the class of high-resolution ODEs 31 is the same as in Shi et al. (2022) when r > 2, but involves technical modification when r = 2. The modification helps to establish the convergence bounds in Proposition 5 for both r > 2 and r = 2, whereas similar bounds are provided in Shi et al. 2022 only explicitly for r >
6.1 Strongly convex setting
We provide a Lyapunov analysis to establish Theorems 3 for the class of algorithms 110 Proof details are presented in Appendix [ Although our Lyapunov function, like most existing ones, is manually designed, our analysis proceeds in several structured steps.
Step 1. Bounding the differencing of an auxiliary energy. The sequence {2x} plays key role in our formulation of (10) in three-variable form. We identify Ellax x²12 as auxiliary-energy term and bound its differencing, -ーr 2 51lz+11 12 E - 11..
-
Lemma 2. Let f: IR. + RR. be a funccion in Sp For any & > 0 such that 0 S ns S 1 v 2 0, 1- 0, T T>0 and Ç = 1 + (1 T 2 0, the iterates of (10) satisfy that for k 2 1,
c 72 (T+ 1- vVa) 1-
VV7 (f(x)) f³)
vs
51 T
[Vf(2>)]
1
1
| x011
2
---
1- vV
マz (T (TL(a) (f(#=-1) fr
n 2
Vf
4 - x11 (42)
2
Step 2. Constructing a discrete Lyapunov function. We define Lyapunov function simply from the right-hand-side of 42 for k 2 0, SV ( + (nVT) (s(n)) f V 72
178 (T)(())))
+
#2 "1 - 1=1
11
(43)
We refer to the first term above as a potential energy, involving both f(xx)= - f and
V f7(((x))) (12, and the second term _ - x² as an auxiliary energy. The negative term - 2/2 || [ I|2 in 43) is a technical
adjustment and can be traced to [2. A similar term can be found in our Lyapunov (16 in the convex setting. By Assumption 1 for smoothness of ii(-) near 0, a sufficiently small Co E (0, Amp
can be picked with
1/o > 0 such that when 0 < S Go, we have 0 < μs S Co, 7) 7(vg)) < 21)o, and I < 2n 5 Then Ca by the L-smoothness of f, we have [(xx) f
for 0 < 8 < %.
ne [( (1 [[L=) (+) Z
{(((z)) - ft). More details are given in Appendix C.3 The negative term in 46 is handled similarly in
Appendix D.3
Step 3. Identifying sufficient conditions for Lyapunov contraction. As expected from 42 we further bound V - (1 V V and identify conditions such that a contraction inequality holds for the Lyapunov function: V (1 - v V S..
Lemma 3. Define and II as polynomials of / T,, v and T (hence functions of vQ) taking the following forms: (reeall that Ç + (1 - (1-T) ())
I = <u(T + < - ?
= T(V -0- + unn -(( -1)) 2np(r 1)g + mu(l 1)20g
(44)
II = T(UT - 2(r) + (n(UT= - -(n)
= T(UT- - 27) + ( DT + 2T(T 1)) + 17(7 1)(2n vT)q - 27 - -1)2g3.
25

---

Published in Transactions on Machine Learning Research (03/2026)
Under the condition in Lemma 2 if one of the following (mutually ezclusive) conditions holds: (t) I>>>> 0 and It /qll < 0, or ((i) I>> 0 and (1/m)I + /gll < 0, or ((i) I 0 and II S 0, then we have the contraction inequality VR+1 S (1 - P V for 2
Step 4. Verifying the contraction conditions and completing the analysis. For completing the analysis, the final step is to show that the sufficient. conditions for Lyapunov contraction Lemina are satisfied under the conditions included in Theorems This step can be algebraically tedious, and the details are left to Appendix [
The contraction inequality, if verified, directly leads to a convergence bound O((1 - -ii as stated in 12 However, to fulfill the conditions in Lemma 3 we find that two ranges of stepsize (or q) are allowed: 0 <<> 8 S 1/L2 (or 0 < S 1/k²) and 0 < 8 x 1/L (or 0 < S 1/K). As discussed after Theorem | the upper bound of feasible determines whether the vanilla or accelerated convergence is achieved, in terms of the dependency on K.
6.2 Convex setting
We provide a Lyapunov analysis to establish Theorem 4 for the class of algorithms 20 or equivalently (22) Proof details are presented in Appendix D Our analysis procoeds in several structured stops, similarly as the strongly convex setting (Section 6.1
Step 1. BBounding the differencing of an auxiliary energy. From formulation of the 2| - x² 112 as an auxiliary-cnergy term and bound its differencing, | x
form 22 we identify
2
-
Lemma 4. Let f: R R be function in FL. Then for each k 2 such that ar 2 1 and āi 0, the iterates of (22) satisfy
0z.s
afāxs(((IL) f*)
2 [f(x))11 -=122411 --14411--111 x=
S ān 1)s (f( - (2 Bk Ls) [
+ 1 + (
x11 (45)
Step 2. Constructing a discrete Lyapunov function. We define a Lyapunov function simply as the seft-hand-side of 45) up a scalar sequence {wk}: for k 2
1 Vi+1 = wh+1 (fxā)s(((x)) az 1V 112111=0111
(46)
The sequence {wx} is introduced to later deal with the mismatching of coefficients on two sides of 45 Similarly as in Scction 6.1 refer to the term involving f(xx) and [[](())]] as potential energy, and the term = x 12 as an auxiliary energy.
Step 3. Identifying sufficient conditions for Lyapunov contraction. As expected from 45 we further bound Vx+1 Vi and identify conditions such that a contraction inequality holds for the Lyapumov lunction: Vt+1 V& S 0 or V V V -k2 (
Lemma 5. Define and II as follows:
I = wp 0t-1 - wk+ W 1),
II 11410+(01, 1)3
Br- 1 L.s) wr
For any k 2 such that 0g 2 1, 0 2 0, we 2 wh+1 12 0, and II > 0, the Lyypunoo funclion
440 salisfies
Ve+1 < Vg. If further II B12CK Ch2 for a constant C > 0, then V - V < C
2 2 (
Step 4. Verifying the contraction conditions and completing the analysis. The final step show that the sufficient conditions for Lyapunov contraction Lemma are satisfied under the conditions included in Theorem A The details are left to Appendix
26

---

Published in Transactions on Machine Learning Research (03/2026)
The contraction inequality VA+1 V& leads to the convergence bound [16) for the objective gap, whereas
the contraction inequality VE+1 V& X ( leads to the inverse cubic rate (18) for the
squared gradient norm. Unlike in the strongly convex setting, the stepsize can be simply set in the range s S 1/L to fulfill the conditions in Lemma
7
Conclusion
Our work contributes to understanding the acceleration of first-order algorithms for convex optimization. We directly formulate discrete algorithms as general as we can and establish sufficient conditions for accel- crated convergence using discrete Lyapunov functions. We point out currently notable gaps between the convergence properties of the corresponding algorithms and ODEs. We propose the Hamillonian-assistee gradient method, HAG, and demonstrate unified interpretations of our acceleration conditions, especially those for gradient correction. Future work is needed to address various open questions, including the ex- tent to which our sufficient conditions are necessary, improving analyses using the LMI/SDP framework, and further understanding the gradient correction and its relationship with existing explanations, such as symplectic integrations.
References
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18:1-51 51, 2018.
Zeyuan Allen- Zhu and Lorenzo Orecchia. Linear coupling: An ultimate unification gradient and mirror descent. In 8th Innovations in Theoretical Computer Science Conference (ITCS), Schloss Dagstuhl- Leibniz- Zentrum fuer Informatik, 2017.
Nikhil Bansal and Anupam Gupta, Potential-function proofs for gradient methods. Theory of Computing, 15:1-32, 2019.
Amir Beck. Firsl-Order Methods in Oplimizalion. SIAM, Philadelphia, 2017.
Amir Beck and Mare Teboulle. A fast iterative shrinkagg--hrreshokinng algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2:183-200 202, 2009.
Sébastien Bubeck, Yin Tat. Lee, and Mohit Singh. A geometric alternative to Nesterov's accelerated gradient descent. arXie preprint 1rv: N00.0000.08187, 2015.
Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with appli- cations to imaging. Journal of Mathematical Imaging and Vision, 40:120 145, 2011.
Enea Monzio Compagnoni, Rustem Islamov, Frank Norbert Proske, and Aurelien Lucchi. Unbiased and sign compression in distributed learning: Comparing noise resilience via SDEs. In International Conference on Artificial Intelligence and Statisfics, pp. 4087-4095. PMLR, 2025a.
Enea Monzio Compagnoni, Tianlin Liu, Rustem Islamov, Frank Norbert Proske, Antonio Orvieto, and Aurclien Lucchi. Adaptive methods through the lens of SDEs: Thcoretical insights on the role of noise. In The Thirteenth International Conference on Learning Representations, 2025b.
Paul Dobson, Jesus M Sanz-Serna, and Konstantinos C Zygalakis. On the connections between optimiza- tion algorithms, Lyapunov functions, and differential equations: theory and insights. SIAM Journal on Optimization, (5(1)5537-566, 2025.
Yoel Drori and Adrien Taylor. On the oracle complexity of smooth strongly convex minimization. Journal of Complecily, 68:101590, 2022.
Dmitriy Drusvyatskiy, Maryam Fazel, and Scott Roy. An optimal first-order method based on optimal quadratic averaging. STAM Journal Optimization, 28:251-25 2211, 2018.
27

---

Published in Transactions on Machine Learning Research (03/2026)
Alexandre d' A'ppremoot,, Damien Scieur, and Adrien Taylor. Acceleration methods. Foundations and Trends in Optamizalion, 5:1-245, 2021.
Mahyar Fazlyab, Alejandro Ribeiro, Manfred Morari, and Victor M Preciado. Analysis optimization algo- rithms via integral quadratic constraints: Nonstrongly convex problems. SIAM Journal on Optimization, 28(3):2654 2689, 2018.
Guilherme França, Jeremias Sulam, Daniel Robinson, and René Vidal. Conformal symplectic and relativistic oplimization. Advances in Newral Information Processing Systems, 33, 2020.
Bapliste Goujaud, Adrien Taylor, and Aymeric Dieuleveut. Provable non-accelerations of the heavy-ball method: B. goujand et al. Mathematical Programming, pp. 1-59, 2025.
Walid Krichene, Alexandre Bayen, and Peter T. Bartlett. Accelerated mirror descent. contimuous and discrete time. Advances in Neural Information Processing Systems, 28, 2015.
Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57 95, 2016.
Michael Muehlebach and Michael Jordan. Optimization with momentum: dynamical, control-theoretic, and symplectic perspectives. Journal of Machine Learning Research, 22:3407 3456, 2021.
Radford M Neal. MCMC Using Hamillonian Dynamics, chapter 5. Handbook of Markov Chain Monte Carlo. CRC Press, Boca Raton, 2011.
Y Nesterov. method for solving a convex programming problem with convergence rate 0(1/k²). Soviel Mathematics Doklady, 27:372 376, 1983.
Yurii Nesterov. On an approach to the construction of optimal methods of minimization of smooth convex functions. Ekonomika. Mateaticheskie Metody, 24:509 517, 1988.
Yurii Nesterov. Lectures on Convez Optimization. Springer, Berlin, 2018
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathemalics and Mathematical Physics, 4:1 17, 1964.
Boris Polyak. Introduction Optimization. Optimization Software, New York, 1987.
Ning Qian. On the momentum term in gradient descent learning algorithms. Newral Networks, 12:145 151, 1999.
Jesús María Sanz Serna and Konstantinos Zygalakis. The connections between Lyapunov functions for some optimization algorithms and differential equations. SLAM Journal on Numerical Analysis, 59(3): 1542-1565, 2021.
Bin Shi, Simon S Du, Weijie Su, and Michael Jordan. Accelertion via symplectic discretization high- resolution differential equations. Advances in Neural Information Processing Systems, 32, 2019.
Bin Shi, Simon S Du, Michael I Jordan, and Weijie J Su. Understanding the acceleration phenomenon via high-resolution differential equations. Mathemalical Programming, 195:79 148, 2022.
Zexi Song and Zhiqiang Tan. On irreversible Metropolis sampling related to Langevin dynamics. SIAM Journal on Scientific Computing, 44:A2089-A2123 2022.
Zexi Song and Zhiqiang Tan. Hamiltonian-assiste Metropolis sampling. Journal of the American Statistical Association, 118:1176-1194, 2023.
Woijic Su, Stephen Boyd, and Emmanuel J Candès. A differential equation for modeling Nesterov's ac- celerated gradient method: Theory and insights. Journal of Machine Learning Research, 17:5312-5354. 2016.
28

---

Published in Transactions on Machine Learning Research (03/2026)
Boya Sun, Jemin George, and Solmaz Kia. High-resolution modeling of the fastest first-order optimization method for strongly convex functions. In 59th JEEE Conference. on Decision and Control (CDC). TEEE, 2020.
Adrien Taylor and Francis Bach. Stochastic first-order methods: non-asymptotic and computer-aided anal- yses via potential functions. In Conference on Learning Theory, pp. 2934 2992. PMLR, 2019.
Adrien Taylor and Yoel Drori. An optimal gradient method for smooth strongly convex minimization. Mathematical Programaming, 199:557-594, 2023.
Adrien Taylor, Bryan Van Scoy, and Laurent Lessard. Lyapunov functions for first-order methods: Tight automated convergence guarantees. In International Conference on Machine Learning, pp. 4897-4906. PMLR, 2018.
Manu Upadhyaya, Sebastian Banert, Adricn B Taylor, and Pontus Gisclsson. Automated tight Lyapunov analysis for first-order methods. Mathematical Programming, 209(1):133 170, 2025.
Bryan Van Scoy, Randy A Freeman, and Kevin M Lynch. The fastest known globally convergent first-order method for minimizing strongly convex functions. IEEE Control Systems Letters, 2:49-54, 2017.
Andre Wibisono, Ashia C Wilson, and Michael I Jordan. A variational perspective accelerated methods in optimization. Proceedings of the National Academy of Sciences, 113:E7351-E7358, 2016.
Ashia C Wilson, Ben Recht, and Michael I Jordan. A Lyapunov analysis of accelerated methods in opti- mization. Journal of Machine Learning Research, 22:5040-5073, 2021.
Lin Yang, Raman Arora, and Tuo Zhao. The physical systems behind optimization algorithms. Advances in Newral Information Processing Systems, 31, 2018.
Jingzhao Zhang, Aryan Mokhtari, Suvrit Sra, and Ali Jadbabaie. Direct Runge- discretization achieves acceleration. Advances in Newral Information Processing Systems, 31, 2018.
Yuchen Zhang and Xiao Lin. Stochastic primal-dual coordinate method for regularized empirical risk mini- mization. Journal of Machine Learning Research, 18:2939 2980, 2017.
A Comparison with the literature
A.1
Comparison with the LMI/SDP techniques
We compare our methodology with the LMI/SDP techniques in Lessard et al. (2016) Fazlyab et al. (0018)
Taylor et al. (2018). Taylor & Bach 2019) and U Upadhyaya et al. (2025)
As mentioned in Section I the LMI/SDP techniques, including the PEP methods and the IQC mothods, are powerful tools for constructing Lyapunov functions systematically. Duc to an inherent optimization procedure, the LMT/SDP techniques generally produce sharper bounds for optimization algorithms. When applied to existing algorithms like NAG-SC and TMM for minimizing strongly convex objectives, the LMI/SDP techniques may produce a larger constant C' in the convergence bound O((1 ([(1-C/w))) C/VR)*) than our hand-crafted Lyapunov functions in Section 6.1 Nonetheless, as mentioned in Section 2.2] our goal is not to find the sharpest convergence bound. Instead, all algorithms with bound O((1 - C/ (/)R)) for any C > 0 are considered to be accelcrated, and are not further differentiated in our work.
The LMI/SDP techniques may rely on numerical solvers to find the Lyapunov function Icading to the sharpest bound, whose results are less interpretable. However, our goal is to understand the mechanism behind the acceleration phenomenon. To that end, we analyze general and representative classes of algorithms as 10) and (20p. Although our Lyapunov functions are manually constructed, they lead to concrete sufficient conditions on the gradient correction for acceleration that have interesting interpretations.
29

---

Published in Transactions on Machine Learning Research (03/2026)
A.2 Comparison with Sanz Serna & Zygalakis (2021)
Sanz Serna & Zygalakis (0021) leveraged the IQC methods in Fazlyab et al. (2018) to analyze family of
Nesterov optimization methods, which is subclass of the algorithm (14). Although their analyses yield sharper bounds duc to the control-theorotic framework, the subclass of algorithms has a fixed gradient
correction term, and thus do not inform the effect of gradient correction on acceleration.
To be more specific, [aazz Serna & Zygalakis (202)) studied algorithm (3) whose single-variable form is With a momentum coefficient
ci vq + R2, algorithm (3 is special case of (14) with oo 1, R 0, 02 = 3/2, and R3 -1 -Q + Rg. Notice that the leading coefficient of gradient correction is fixed at c2vec0 co/2 =. Sanz Serna & Zygalakis (2021) shows that, for 0 < S I. the iterates of (3) or (4)
satisfy the convergence bound [(zx) - = 0 (11 C1 ()))) for 0 < C1 S 1 as long as ((g) is bounded by
-_ (oo))
+ R2 S C1),
where
To (g. G)= =1 1 V - C + Ci Vq O
C2
As C1 0, the linear term coefficients 1=V1-C7+C? goes to 0 and co respoctively, which implics that o(g) ed 1-61 / with any Ci > 0 always bounded by a- and 04 for some Ci and @ small enough. Therefore, achieves an accelerated convergence rate O ((1 O(L/O(1/)))))) which
for any 01 > 0, the subclass
is weaker than our condition
4co.
The subclass 14, however, uses a fixed gradient correction so that its convergence rate does not inform the impact of gradient correction on acceleration. The later work by Dobson et al. (2025) established sharper results on C under more complicated conditions on the momentum coefficient a. However, because the same class of algorithm implications on acceleration.
3 or (4) is studied, a sharper constant C₁ does not lead to qualitatively broader
In terms of the ODE part, the limiting ODE of under o = 1 C1 4 Ro is
Xe + cI CIVTX, + Vf(x, 00
which is the same as equation 26 with co 1. Interestingly, if e depends 8, then the algorithm 4 with an accelerated convergence may not have limiting ODE as ei is allowed to oscillate between
1---- 1+V1-09+09 A similar observation is made the convex case. See Lemma 1 for details. C
C
When C1 is constant, Sanz Serna & Zygalakis (2021) used the IQC methods to prove that f(X)) - O(cxp(-CvTatf(enn - f*)]) for sharper constant C' than that in our Proposition 3 If S! The with bounded Lipschitz constant L, Dobson el al. (2025) shows that the constant C' can be Turther improved.
Unlike Sanz Serna & Zygalakis 2022 | and Dobson et al. 2025), our goal is not to find the sharpest constant in convergence bounds. Instead, we would like to characterize algorithms with accolerated convergence. Nonetheless, the IQC methods remain powerful tools that can be leveraged to refine our analysis on gradient correction in future work.
A.3 Comparison with Shi et al. (2022)
We compare our results with those in Shi al. (002 below.
In the strongly convex setting, Shi et al. 2022 leveraged the high-resolution ODEs to establish accelerated convergence for NAG-SC and non-accelerated convergence for HB. Their analysis links the acceleration to the gradient correction term, which is present in NAG-SC but absent in HB. However, it remains unclear in what scope the gradient correction leads to acceleration. Our work bridges the gap between HB's non-acceleration and NAG-SC's acceleration by showing that as long as the gradient correction coefficient surpasses an explicit threshold, the acceleaation guarantced. Remarkably, the same condition is also observed for the convex setting. Therefore, for the first time, our analysis establishes a unified condition for acceleration in strongly convex and convex settings.
30

---

Published in Transactions on Machine Learning Research (03/2026)
In the convex (not necessarily strongly convex) setting, our results are mainly technical refinements of those in Shi et al. 20022 The class of algorithms in (20) is more general than the one studied in Shi et al. [0022]. See Table
for details.
Another question left by Shi et al. (2022) is whether the high-resolution ODE that explicitly re- tains the gradient correction can explain the difference between discrete algorithms. We show that the high-resolution ODE perspective, albeit remaining a useful analytic tool, fails to explain the difference between accelorated and non-accelorated algorithms (especially regarding the gradient correction term) in either the strongly convex the convex settings.
To summarize, our work substantially extends Shi et al. 2022 in understanding the effect of gradient
correction on acceleration.
B
Notation
The notation used in the main paper and the remaining appendices are summarized in Table 3
C Technical details in Section 2
C.1 Reformulation of NAG-SC and TMM
First, we show that NAG-SC with can be reformulated as i.c.. 10
with 17 = 7 -1.
Apparently 3a is the same as Sa It sullices to derive 8b
and
Sc from
3
Because 2o yo 20.
also holds for 2p- Therefore, for 0 we have
/ Th +
+
yk / /
1
which implies
/9
1
+
1 v M/
(47)
!
and
Uk = (1 + T v=k-
(48)
Eq. 47
with & replaced by k + becomes Sch Substituting Fh+1 from 47 into
3b
we have
1 /
2k+1 + - /q
Uk+1 u + 1 1 /9
(t++1 yk),
which yields
/4
1k+1
uk+1
yk.
/
Substituting 1 from
3a into the above display, we have
/
Zh+1 =
(Ix sVf(((())
yk
/
which together with 48 gives
1 / ((1 vr - = vo (((xx- v0(xx= VV((T)) +1 -V))
26+1 =
(ok -s vV(()))
/9
#
which is 8b
31

---

Published in Transactions on Machine Learning Research (03/2026)
Table 3: Notation
Section
Notation
Meaning
Objective function be minimized
x**
One of the minimizers of f Minimum of f
f*
L
Smoothness parameter of f Strong convexity parameter of Condition number L/μ Iteration number gradient methods Step size in discrete algorithms Convex and times continuously differentiable functions from R to R Functions in Fm that are additionally L-smooth
General
K
k
fm
Fy.
Syn
Functions in F that are additionally p-strongly convex Functions in FL n
u.b
Shorthand for jus Momentum coefficient
11, u, and
Three parameters in algorithms (10 and 11 that may depend q Non-negative, analytic scalar functions in Assumption I such that 7) ((v)), (V()), and 7 = F(vg)
0, and F
Strongly convex
{nh (us) {
Coefficients in the Taylor expansions
13 of v, in Assumption |
{ co, cI, and 62
Shorthand for + (1 (1-7)g 7)g
Parameters in algorithm 14 consistent with the parameters the
limiting ODE 26 of
Ok+1
Momentum coefficient (possibly varying in k)
001+1
A scalar sequence for specifying momentum coefficient as 0h41 (az: 1)/ax+1
Convex
A scalar for specifying as (k: + r//r. consistent with the parameters
in the limiting ODEs (30) and (31 of 21
Bg and 7
Two parameters in algorithms 220 and 21 that may vary with k
B and y
Limits of B% and 7h, respectively, consistent with the parameters in the
limiting ODE (31 of [21
ODE
X,
Solution X(t) for ODEs
u and
Momentum variables in the Hamiltonian function and the associated discrete algorithms, respectively
and p
The linear constraint parameter and the extrapolation parameter, re- spectively, in deriving the HAG method
HAG
αk by, and de
Three parameters in the HAG methods (32 and 33
a, b, and &
Constant aj, bk, and Ok, respectively
Second, show that TMM 5 i.e., 49ch same as for Zk+1:
10 with and 2, can be reformulated follows, with
Vk+1 T3 [z(()))
(49a)
Ik+1 = Ik - -2 - Vf(k) + (1 2
1+ / (8k+1 - yk),
(49b)
2k+1 = 1+ / Fk+1 + (1
1+ /
Wk+1-
(49c)
2/9
2/9
32

---

Published in Transactions on Machine Learning Research (03/2026)
Apparently [5a] is the same 49aa. It suffices to derive 49bb) and 19cc..
Solving (5c for 2k+1 gives 49c
Because 20 yo 20, (49ch also holds for 20. That is, for all k 2 0,
1 / In + (1 2k
1 + /
yk.
2
2
which together with bb yields
1 + vg
In + (1 (1-
1 + VI
1k+1 v Ik
+ + +(1- v1)
y/
1
2/9
2/4
+ q
(1 vq)²
2/7 rhk
1/k.
1
2 2
To derive 49b), substituting the above display into
5cc and using (5a) yields
2
1+ Ik
v
(1 - 7 yb
1 /
1k+1
1 /q yk++
1 /9
2/9
1
2/9
1+9
2s
+ (1- v9)2
(MA-+1 -yh) + //(1 v9)
1 V9 Fh
Vs(zz)
yk+1
1 V
1 V/
+ /9
1+ Th
2s
(1 7
(y/++1 yk) + v v
1+ 4 vf(xx)
(Ik sV
1+ V9
1+ /q
+ /
24 - (2 - VZ + (1- --)
(yk+1 Vk),
1 /q
which is 49b
C.2 Proofs of Lemmas 2+3 in Section 6.1
Proof of Lemma
By 10bl. we have
1
x= x²11
1
1ー || 2s - x² 112
2k+1
/V92 2
2
2
1
1/ /V
V fz²)) - -xx) + (1 - // / - x²)
11
11Ex
x=12
1 - V /
2
2
pM /
1|
x² 111 ww u 7 a²,20 xx
1 V (xrx) - -x*)
v2q
T:k:
1
-V((())
x²*
2
1
/9 2
/
(zk x²) (zx vf(xx) - 2T)||
" /
1
+ - / 2
fxx)
2
Zk ok +
1 [
||
+ + u
Ik -V((()))
xx"
2
(50)
2
P
Next, we bound the two terms in the above display separately. For the second term, by the p-strong convexity of ʃz
f f(En) 2 (VI(zz), x²
xx) + I1l - 1|
11 2
from which we have
Ik 1
1 VVT 2
//
2 bo x= 112 (Ix x-, vf(xx))
+ _ [
(51)
VVT
2n
( ((x))
1 \
+
1 -V-
2/
33

---

Published in Transactions on Machine Learning Research (03/2026)
For the first term, solving (10c) for 2k+1 obtain
1 + (1 - T)
(1-T)v
S
.k+1 3x+1
(x&+1 9k+1) = Ix+1
( -yx+1);
T TV9
7 TV9
which logether with 10a yields
C
2k+1 = 2k+1
(#k+1 - Ik + nsV (xx))
TVq
Hence for k 2 1 we have
1 f(ax))
2 Tk +
2
11
p! "
S
(( + (()())
(IT x2-1)
+
2
T TV
TV
1
(52)
5²v
22222 /
\f "V7 ff
100k- 112
72 T 2
72
2μ
1u a (V - xk-1) -
Çv (Vf())), 22 -k--) <nV
(VV((xx-1) (()(())))))VV((T()
72
By the I-smoothness of f. we have
((xx1)) f(xx)) (V + [f(z)) - vf(xz-1))1;
2L
xn-1) (((mN) S (V/(z==)))) -
L
u x2-1
2
Therefore,
V (VI(Ix-1), 5k-1) 5V (V](Ix)), IK--)
72
nTuva (((xz) f(ak-1) 2/2 1,0k 22-1113)
I.
5V (f(zz) f((xx1) + [f((k) - V/(DA-))P
$ T²
2L
CV ( ( - [((x)) + /2TpU
L
CV 1
||
x6-1"l 1|2 1|2
Vs(xx) V
72 2
2T.
(53)
By the cosine rule,
Snys (V](o=-1), Vf(x))) = Saps
(IV + [V/((1)1 - [V - V/((x-1)1?). (54)
2r
Combining
53 52
and 54 and noting 0 S < 1/L by assumption, we obtain
Wv /9
as + ((W))
2
( 22
CV
(1
nLS)|laX - 22
(1 (1-n1- -
27 //
2rL
SnVS
VVV
(T
(nvO)((((x-)) -f(x))
(T + (
(T + (VVV)\\)
7
272
2μ²
VV7
5
( + (
- -((x))
(T + <\/0
(T [
2-
2μt
(55)
34

---

Published in Transactions on Machine Learning Research (03/2026)
Collecting 50
51
and
55
completes the proof.
Proof of Lemma
3 The three sets of conditions are mutually exclusive because if I >>>> 0 and II > 0, then
I+ VQll > 0 and
I + Vill 0. Applying (42) to the Lyapunov function 43 and using the fact that
27 [f(x))]l S f(x) - H 2 [V we have
Vk+1 - -VVV)V
(V((T)(((M))) - - + +VV)
27
vi (I+ VqII
i 0;
27
v
I vell
if S
27 P
V vql.
+I++ (f(mn) - 5²),
if 1I 0;
72 1
72 / (I (I+ - f*),
if < 0.
The rest is straightforward.
C.3 Proofs of Theorems 13
we show that under Assumption 1 the leading coefficients in the Taylor expansions of I and II /q can be used to verify the conditions in Lemma Throughout, the range q S p²/L² 0 < q a L/L is interpreted as, respectively, constant Co 0.
To prepare for the proofs of Theorems
S Cop² or q S Cop/ L for
Lemma 6. Under Assumption 7 denote the Taylor exponsions of and II as
I= Σ an(v))" =I= Σ 6m (m
where {an Jnzo and (bm Jm20 are real sequences. When I is not constant O, define N as the minimal of n. such that an # O. Define M in similar manner for I1. Then
(i-a) If aN > 0, bas < 0 and M < N-2 2, then I> and VQII S for < k/
(i-b) If aay > 0, by <0, M = N 1,, and the first nonzero element of (an + +bn-1)n2N (i.e.; the first nonzero
coefficient in the expansion of I /qIII is negative or the entire sequence is 0 (i.e., I+ /qIII = 0), then
I> and I+ /qll < 0 for 0 < q S L/L.
(ti-a) Ifa < 0, bus > 0 and M = N, then II and 1. II+ /ilII < for 0 << w3/22
(ii-b) Tfax < 0, bm > 0 and M 2 N 1, then II >> 0 and "I+ /JII < for 0 < n/L.
(iit) If an < 0 (or N does not erist) and by < 0 (or M does not erist), then I < 0 and II < 0 for
0 S//L.
Proof. With 0 < u/L < 1, can be made sufficiently small by picking Co in the range 0 < S Cop² Cop2/L2 or << <<9 4 Cou/L L. Hence it suffices to study the leading terms of I and II.
For (i-a) and (i-b), aN > ensures that IN aN " O. For (i-a), with M+ N and bas < 0, we have I+ vill- basl ( M+1 < O. For (i-b), with M M+1=A N, we have I+ lall = -n= + bn-1) if the first nonzero element of {an b2-1hn2N is negative or the entire sequence is 0.
For (ii-a) and (ii-b), by > 0 cnsures that II ~ b > O. With < 0 and bm > 0. we have that for sufficiently small q > 0, I < (v and II < 2b Hence, #I+ /qll < pax
(VT) +
2L
For (ii-a), M = N and < < C/p2/L imply that +I+ /III < (vΦ)* ZI +ax++ < by picking sufficiently small Co with ax < 0. For (ii-b), M 2 N+1
( M+1 (VT)N 2L + (b9 M (Vg)M+IMM)
N 22 (aN + 4Cbbm) < 0 again by and 0 S Cop/LL imply +I+ VIIl < (VQ)N NaNNea gax (b)((v²)) < (vq)*
picking sufficiently small Co with ax < 0.
35

---

Published in Transactions on Machine Learning Research (03/2026)
The case (iii) is straightforward to verify. If N (or M) does not exist, then I= 0 (or II 0).
We notice that the constant Co in the range of is picked, depending only on {an} and {bm} which are determined by the algorithm parameters vi, i and F.
Next, we show Theorems T 2 and B where Theorems 1 and 2 are the same as Theorems 1 and except with conditions (i-a) and (ii-a) replaced by (i-a*) and (ii-a*) as follows:
(i-a") < Na < Top and S 1oo < 1070/2;
(ii-a") 0 < V/ < Tos and no 2 no
Conditions (i-a) and (ii-a) are the symmetrized (hence weaker) versions of (i-a") and (ii-a"), by allowing either 0 < 14 To or < To vo. To show Theorems ! 2 and g it suffices verify that the conditions in Lemma are satisfied. In fact, the contraction inequality in Lemma 3 directly implies that that for k 2 1,
L (r+ + (1 ()L)) 8*) s Va+1 s s (1-WVT)*V s (1 (1 V
C(((#)) f) <
for some constant C 0, where the first inequality holds by noting no, To > in each condition of Theo- rems D 2 and and picking sufficiently small Co in 0 q Con/L such that, for example, v vo/2. /2, Ta/ S 2To. 1/2, 0 S nss S 1/(2L) (i.e., 0 na m/(2)) with C vo/(1670). Moreover, by the
definition of V1,
V1 x 72 (T + (f - f*) 1
|1 x²11
2
C ( + () (f - f*)
p
In
- x
Vv
v fxxo)l?
2
(56)
2 A||a0 - x 1²1 + 11|200 - x²1 + s|| V f(x)))
$ (L + μ sL 2 ||200 ==1
2 L||m0 - x 11
Then Lemma 3 can be easily verified by noting vo, > 0 and
- which is 12
The conditions in Lemma 2 which are required in
picking sufficiently small Co. Therefore, it remains
to verify the conditions involving I and II in Lemma 3
Proof of Thcorems and 3
We apply Lemma i to verify the conditions involving I and II in Lemma The Taylor expansions of I and II up to Vi-terms are
Tolu - TO) + +|70(11 TI + ni (1o - T)) vo(m - To(TO - -))])+++))+)))))
ao
(57)
II To(PoTo - 27o) +200)+(T0((1 - 2m) T1 -2)) no 1)
1) + 1OTO - [l)
Consider the following scenarios.
Scenario 1: no = 0, < Po, To- Then by = by voT > 0. Because M = 0, only case (ii-a) in Lemma i
is feasible, which holds when N and aN 0g To(Po tO) < 0, i.e. vo To To conclude, if no 0 Po < To. then Lemma 3 holds for 0 9 S 2² 2/33.
Assume To, Up and are all positive. We notice that 0 <. < is necessary. Otherwise, ag = 7o - To) > 0
and N = 0. Then only cases (i-a) and (i-b) in Lemma 0 are feasible, which require M < N - 1, contradicting
0. 0. To proceed, we further split 0 < un S To into Scenario 2 (0 < P0 < T)) and Scenario 3 (0 < un = m))
as below.
Scenario 2: no > 0,0 Pe To. Then an To( TO) < 0 and N 0. We notice that either M does not exist (i.e., II =0,, M exists and has by > 0 bu for some M 2 N 0. Therefore, one of
36

---

Published in Transactions on Machine Learning Research (03/2026)
case (ii-a), case (ii-b), and case (iii) in Lemma 6 is valid. Case (ii-a) holds if and only if M = N 0 and
bM by To 70 21%) > 0, i.e., 7o < 2 Therefore, if 1/0 2 Mata
2 case (ii-b) or case (ii)) holds. To
conclude, if 0 < < vato and 0 < Po < To, then Lemma 3 holds for 0 < S p2/ If n00 2 Mor and
2
< Vo < To: then the range of q is relaxed to 0 < 4/L.
Scenario 3: to > 0, 0 < vo To- In this scenario, 57 reduces to
I To 1/1 - 71 + 1/0 To(To - 1)] - O(g).
II To 2np) bp
(o(L1 - -2m1 (TŌ 2nj) +o (TO 2) 1 -mo0] -10]lv V O(g).
Then Gg = 0 and hence 2 1. We point out that no 2 we
is necessary. Otherwise, dn = To (T - 2n/) > 0
and hence MM = 0. Then only case (ii-a) or (ii-b) in Lemma G is possible, which requires M Z N. But this
contradicts the fact that N and M 0. To proceed, we split noo 2 3.2 (Nl _ based on 17o-
to into Scenario 3.1 (no _ and
Sccnario 3.1: 770
= To. Then by = T 2nj) and M O. Case (i-a), case (i-b) and case (iii) in Lemma G are each possible. We consider several special cases involving only m, in and TI-
< vo =0=
For case (i-a) to hold, even higher-order coefficients are needed, and we skip this case.
For case (i-b) to hold, let M which is equivalent to V T1 + 7o 70 1) > 0. Moreover, let aN + bx-- a1 bo
and av = a1 To [p1 τI + 170 To - 1)] 0.
To 1/1 + 1/u (To 1)/l + To(T] - 2np) Toll1 7 + To nol < 0, which is equivalent to
100 70-
For case (iii) to hold, let a1 = To [n - 1I = - 170 - To(o - 1)] < 0, which equivalent to V1 - n <
To(To 1) 7/0-
To conclude, if z
0 < vo = To. and either To(To 1) < < To or 11 < <To(TO- 1) n70
then Lemma 3 holds for
< $ nu/..
Scenario 3.2: 700-
0 v0 = To- Then 57 further reduces to
2
= (M 1I + To - }) V O(g).
2
a1
To
II = To [1171 - 2m +
To
2) + 0(g).
2
Then dg = bu = 0. We consider several special cases where (71, (1) are enough to determine the conver- gence. Let 01 = To (n - π + (n 7 })) < O, which is equivalent to v1 - 7i + 70(1 T < 0. Then N ==
We distinguish three cases by the sign of b = To 2m + ( - 2)]
If b, 0, then M- and bm < 0, and hence case (iii) holds.
If b, > 0, then M = N = and by > 0, and hence case (ii-a) holds. Note that the range for g is
0 < 0</=""
If b, = 0, then M 2 2 + or M does not exist. M does not exist, case (iii) valid. If M
exists, then either bys > 0 bys < 0. The former satisfies case (ii-b) and the latter satisfies case (iii).
37

---

Published in Transactions on Machine Learning Research (03/2026)
Collecting the results of Scenario 1, 2 and 3 concludes the proof for Theorem and 3
Proof of Theorems 1 When (n) constants, the above analysis still holds, but we unfold
Scenario 3 without imposing strong conditions on (71.21:71 T1). We continue with Scenario 3, that is, assume
1) 2 7² and == r. Then we have the Taylor expansions finite terms:
2
I I= - - (T - 1)r) 21 -
II - -(72-2n) 73 2) 7/ 7(7 1) - (T 1)2g
(58)
I+ Vill -(T v + 1 -)4 + 77 - - (
To proceed, we split Scenario 3 into Scenario 3.1* and 3.2" based on 7
Scenario 3.1":
>>>
= 2 0 リリ== Then bo = r(T² - 2n) < 0, and M = 0.
r >> (hence T < ,² 2 < < 1)).
-
II T(T -), 1), then dn T(1 - 7(7 - 1)) 0 and N M + 1. Moreover, an bo
T(r 11) < 0, and hence case (i-b) in Lemma
6 holds.
If 1) = 7(T - 1), then di = (1) - -(r - 1)) 0, and 02 = -2pT(T - 1) (T - 11) <0 0.
Hence case (iii) in Lemma holds.
If ,² 2 < T 1), then an = -(n T(r 1)) < O. Hence case (iii) in Lemma holds.
T == 2 (hence
- 1) 2). Then I 2(n 2) -) and It VQII 2(2 1) /7+
By 7 > oे2 2, we have 2 - 2) > 0 and + bo = 2(2 7)) < 0. Case (i-b) holds.
0 < < 2 (hence + >
r² T(T 1)). Then 7 > 2 =² implies that > T(r - 1). Hence a1
2
-(--r(f- - 1)) > and N = M +1 = 1. Only case (i-b) in Lemma 6 is possible, which requires the
first non-zero coefficient of I + /qII in 58 to be negative, or I VI
1ソ > r, then I -ill ( - 0 < O.
If イ 7, then I lQll 72 1)4 + 72(T 1)q² - 1) Hence for < T S 1,
I+ /Qll < 0.
If ,
2 <ク < T, then I /qll =
- -) ( > 0, which violates case (i-b).
Scenario 3.2" 1)
²² < リー=ę Then 58 only involves T: I 1=
( (r
II - _ - 1 and I+ /Qll= = - -1
If > 2, then aN = 0 (1 - }) 0, and by = b ( 2) > 0. Hence case (ii-a) Lemma holds. Note that the range of q is < < H²
r = 2, then I = -8q + 4q and == - _ - Hence an = d2 = 8 < and by = 6, = 12 > 0, with M < N 2, which contradicts case (ii-a) and (ii-b) requiring M 2 N. This case is invalid.
If < r < then ay = aj = =1 - 3) > 0. Only case (i-a) or (i-b) in Lemma 6 is possible. But then I+ lQll = 72 5 + Og)) > 0, contradicting the conclusion (i-a) and (i-b). This case invalid.
Collecting the results in Scenario 3.1* and 3.2* concludes the proof for Theorem D
Finally, we derive Thcorems and from Theorems and by exploiting symmctrization in the case of Mn A To due to Lemma 7 in A Appendix C.4
Proof of Theorems 1 and 2 It suffices to only deal with conditions (i-a) and (ii-a) in Theorem 2 which directly implies the conclusions from conditions (i-a) and (ii-a) in Theorem
38

---

Published in Transactions on Machine Learning Research (03/2026)
For ni 77u 2 0, My 0, To 0, and Mo To, by Lemma 7 algorithm {10 can be first put into (59 with R1; R2, R3 and h (ater
1+,4 Next, we keep yo and the remainder terms, but exchange the role of Po
and to by selting P = To and To vo and then translate (59 back to (10) with new parameters vi ~ 100-
Po = To and T To = vo (S also translated to the new (1-1+(1-) and a possibly nonzero h2 ((tur-((ntur) in 20- In other words, the original algorithm d10p can be reformulated such that the =(1-v99) leading constants in y and T are exchanged and the algorithm now starts with zn and possibly 2o + zp-
For the reformulated algorithm, the proof of Theorem 2 remains valid except for the bound V/2 (56) with the new 2g. Nevertheless, an inspection of (56) reveals that V S L|]zo - 2²1 still holds because h2 can be easily shown to be bounded. Hence, the desired result follows by symmetrizing the conditions (i-a*) and (ii-a") in Theorem 2
C.4 Proof of Corollary
To facilitate interpretation of (10) and prepare for the proof of Corollary we study the single-variable form of [10). The following lemma shows that the two forms can be transformed into each other, provided that
the leading constants in and T diller from each other. The initial points need to be aligned because (10
starts from To and while (59) starts from and Z1.
Lemma 7. Let Ç = (1 - T in Lemma (i) Algorithm 10 with tuning parameters n, and 7
under Assumption admits the single-variable form
11 which can be expressed as
Tk+1 = xz (M00 R1 RR)sV(((x)) (vo ro R2)( xk- (110 Rs)s(VS(1L)) - Vf(xx-1))
(59)
with zo, x1 = xo - h1s- where =1= = O(v9), R2 = O(g), Rss O(vT) and h1 It are analytic
Satur
functions of vq around O. (ti) Conversely, given any analytic functions of vq: Rı = O RS O
Rs )( hi, and three scalars 1o 2 0, vo, To > O, vo # To, there crist ~ T7o, v and r ~
satisfying Assumption D such that 59 starting from To and I1 = To - V f(oo) is equivalent to 10
starting from xn and 20 To h2 (x0o) where
Cn+ - (1 vglh1
h
r(1-v/9
Proof. First, we show that
10 admits the singlo-variable form 11 i.c.,
u(T ( Vf()))
5(1 5(1- VVV)
Sn(1 /V/g) 8 <Vf(()) vf(xx-1))
Fk+1 Ikk
(xx xk-1)
1 + /
1+ /
1+ /9
for k 221 starting from Zo and x1 To-
Cyter 1+
v fxx). The calculation for æ straightforward and hence we have for k 2 0,
omitted. To show I1 from 10c
and
10a
+
1 1 v
S (Ix M f(x)))
2++1
TVC xkt1
TV4
T
Substituting the above display with subscript k ++1 and A for h 2 1 into
10b we have
1 + V9
5 5 (1x()(
2k+1
T T
TV
=VVa(ax - + +1 (1- vv (1--oa)
(1
1 /
S
[IK-1
ns (
1
TV
T T
After rearrangement we obtain
39

---

Published in Transactions on Machine Learning Research (03/2026)
1 + V 7 2x+1 = 1+ v
5(1 vV
C(1 VV
+
TV9 3/
2k-1
T TV9
TV9
(1) ( VT
sVf(()) + 5n(1 - vv
vV (
Tvq
TV9
Solving for 22+1 yields 11 Expanding the coefficients in 11 yields 59
Second, we prove the reverse statement. Given R1 = O(vg), R2 = O(),, R3 = 0(v and the leading constants 110, and TO, we determine 7,, V and T by solving the following equations
u(T + ()//7) = (voTO + Ri) + V = 91 ~ vOTo + O(v)),
((-vvo) (1- (m + To) /q + R2) + /q) = g2 1 (mo + To 11))
<n -VT) (no R3) + v
Note that In and 92 above are known. Solving the equations we obtain
1/0 + R3
7 1- (uo + To) / + R2
flo>
(-6
and v depending on as
91
Yo 1/:
V
7 + CIV
and r as a root for the quadratic equation
02 + 01 7 + 0g = 0,
where
a2 = - V - 174,
01 92 + v (g) 2n n9224 - 2nq 1 To O(v7))
(1 91 1122) q (2n) 91 n)22)9 + . v - P0To + 0 (v))).
The discriminant is A = af 4a2 ag g((10 - m0) + +(vg)) For 10 To 0, the root
-01 -V t A/q to + O - - mo) - O(v
vo + TD
+
|ro Tol
== 2- 2-02
-2 -2.02/ /q
2(1 - 179)
2
is well-defined for small The sign is determined by the sign of vn To to make T ~ To An inspection of the expressions suggests that 7, v and are all analytic functions of /q.
Lastly, from the above calculation, the updating formula for 2& has been matched between starting from Z2- The initial points can be aligned by picking suitable 2p such that xi from 10 exactly zn ( The calculation straightforward and hence omitted.
10
and 59
Interestingly, the leading coefficients in the single-variable form (59 for 10 are symmetric with regard to Yo and To- This suggests that the convergence properties of [10) should also be symmetric in Vo and To- Indeed, such symmetrization in the case of vo * To is exploited in our derivation of Theorems from Theorems in Appendix C.3
Corollary I is derived by translating the conclusions from Theorem in the case of vo # To in terms of the leading coefficients single-variable form.
Proof of Corollary 1 Let C₁ = vo + To, Co = MoTo, C2 co/2 = noo and solve for no. vo and To- The conditions of > 4cg and cp. C1 > ensure that 2n and To exist, satisfying vo, To 0 and vo # To- The conditions on C2 can be directly translated into the conditions on nu- The desired result follows by applying Lemma 7 and Theorem 2
40

---

Published in Transactions on Machine Learning Research (03/2026)
D Technical details in Section 3
D.1 Derivation of three-variable form
22
By comparing 22 with 20 the update of 7k+1 the same. Rearranging #++1 = -2+11 11:++++000 +1-00++))9k
we obtain the update Fk41 in (2c It sulfices to prove the update of 2641 in (22b) With (20 place,
we have
1++1 = 0x+1 + (1 ak+1)Uk+++
aK+1 [Tk S fIz)) + Tx+1 0 yx)] + (1 - ax+1)14++1
ax+1 (z' - 3/ s V fxx))) + (ax - 1)(/++1111111 yx) + (1 - ax+1)8x++1
0++1 (I' - 71-8 V + -a - a++ 1k (++1))/++++
(1 ox)yyk
0++1 (27k 71.8 f
(ax- on 10)+1)(02 B/ V (1xx)) oxx)yk
0422 (1 0x) (1604+1 + Ba(ax V fz(x))
= - (zTx)
D.2 Proofs of Lemmas and 5
Section 6.2
Proof of Lemma 22b
Using
we have
2k+1 x= 11 2
2 x²1
12 x² -fpsV((z)))
1| x²
02
-āss - x", Vf(xx))
+
2 [
Substituting 2ạ 36 + (ax - 1)(xx - 4k) into the above display, we have
2 |12441 x²112 1 _112x 111
1
(60)
+ 0z
= --áofa - x², vs(xx)) - Th (ax - 1)8(1x yk, Vf(xx))
|
[V(()))
2
S S)na(J((N)) (*) an 1)s({(())) f()x)) + 0²
| [+x))]
22 s²
=o 1r) + (ap ()s(J((n)= 1*)
[
where the incquality holds because by the convexity of f and the assumption that ãy 2 0 and 2 1. we have (xx x², Vf(x))) > f(xx) - f and (Ix - yk, Vf(xx)) 2 f(xx) - ((x) When 2 1, by the L-smoothness of f and (22a), we have
L
f(u)) fr S f(xx-1) f" + (Vf 1) 3k 1
+ Ilul - x2-1l1?
2
(61)
3x-18 V V
= f((xx1) f - (2 3x Ls)
2
Combining 66 and 66 yields 45 which completes the proof.
Proof of Lemma
By Lemma 4 for any & 2 such that an 2 1, āz 2 0, we have
V V/2 <
(wk Wk+ )| 11
2
(Waak- - w āx ān (ak 1)) - f*)
(62)
(Wi+1uH (ax 1) (2 Br Ls) wx 2
| [[((==1))1
If wk 2 We+1, then -(w wk+1 11)+1)]=== x01/2/2 0.
The rest is straightforward.
41

---

Published in Transactions on Machine Learning Research (03/2026)
D.3 Proof of Theorem 4
To prepare for the proof for Theorem provide simple bound which will be used in the last step of the proof.
Lemma 8. Let f E FL. When 0 <
Co/L for some constant Co > O, the iterates of 22 satisfy that
for any fixed K, there exists a constant C such that s(f(zk) - ) f(*x and | - upper-bounded by Ci| - x=1 The constant C depends only on Co, and the algoritlm parameters {ak), {3x] and {mke..
x=12 -x* are
Proof. For notational simplicity, we assume Co so that < Ls $ 1. First, by the convexity of f. we have
Ls | x² 0²12 2 ||:x x011?
(((x))-1)) 1z)
Second, by the L-smoothness, we have
& (Ls) - 112 S || - x'11?
Third, by 22b and the
incquality, we have
|1 2=11 || x² axsV S 1| 11=x-2111 x1 [Vx(x))1
which together with the preceding bound on f )| yields
1 || - xx | x=1 a || x111
Because 2g = 20, suffices to bound || - x= 1 by |20 - x² up to a constant for general k: 2 The fact that (22 is a first-order method implies that for each 2 1, there exist scalars {cu,} (depending only on the algorithm parameters) for = O....,k such that
Σ C
Then by the Cauchy Schwarz inequality,
|
x=11 ||
Ch s (z;))²
k- 1
[ - 2=1 +
c 8² V fxx))1
< k |za-1 x
- x² -
Because K is fixed, the proof is completed by applying the preceding bound for 1 S k S K.
With Lemma and Lemma in place, we are ready to prove Theorem
Proof of Theorem 4 By the definition of ã and condition (i)-(ii), we have
ā lim 3x + (7M - BB) ai+1 > 0.
lim k-00
k00
Then ag (2kk) implics that ã ((k). By Lemma 5 the key is to bound and II from below for all k
sufficiently large. The beginning Vj can be dealt with by the simple bound in Lemma so they do not affect
42

---

Published in Transactions on Machine Learning Research (03/2026)
the convergence. To proceed, consider two choices of {w&} depending on the monotonicity of { /ax)
Note that {wx} needs to be non-increasing, to ensure that the first term (ww wx+1)| = x² x21 /2 on the right-hand-side of (62) is always non-positive.
Choice 1: W/ = 1. We pick wy simply as constant when {āx/az} is non-increasing. As for I, by condition (ii) we have
@x=1 an(a0 - 1)
2 @k-1
I 10k1 Ci - 1) 02-1
2
0h-l
2 0.
ax-1
kk-1
akk
ak-1
0ek
As for II, we have
II = ag(0x - 1188 Ba-- - -02-1 = =anlax
-1) ()(2))
(at
Bk-1 12 (2 B18-
0
Okk
ax(ax 1)
For < & S (2 (23) with B> >>//2>> 0,
ākk Bk-1
3k-
(2 - 27
0
II 2 Ork (ax 1)
2
28
where the limit of the term in the square brackets
Ok lim 3x-1 k0000 Ok
3x-1
3)) as (a - 1)
0/-1
7(3 2)) 0.
233
Combining the preceding two displays and a = ((kk) shows that there exist constants K and C' > 0 depending only on algorithm parameters such that for 0 < s S (2 (223/B))(22BL) and k # K,
2 (3 II 2
? 2 aax(ax - 1) CK
Choice 2: Wh+1 ax/āk. When {āz/az] is non-derreasing, {wk} is non-increasing In this case we have I= 0z (0 - 1) 2 0. For 0 < 8 s (21)222(/)
II aa 1)3x-1 Ls) ak-100k-1 04-1
ab-1
= =ax(ax - 1) (k-1( - 3ks)
ak-1
ax (x( - 1) ak-
2 an 1) Bk-1 (2 Bk- (2
7
3
2,3
Ok (otk - 1) 0k
(xrk
where the limit of the term the square brackets
3k-1
3))
07-1 0k-l
lim 3k-1 100
>
29
Or. agp - 1) ak
Similarly as in the first choice, there exist constants K and C > 0 depending only on algorithm parameters such that for 0 < s (2-7/81) 2222/2)/(2BL) and k 2 K,
II z (8 2 Dailax (ax - 1) 2 Ck2
Combining the two choices above, we see that when {āk/au} is either non-increasing or non-decreasing in k, there exist constants K and C' C'x0 0 such that for A K, have I 2 0 and info-ssco/1. II 2 Ck?, where
Co = (2-7/8))((28) By Lemma 5
C k2 2 < O.
VE+1 V -
To complete the proof of 16 for the objective gap, it suffices to bound V2 from below.
43

---

Published in Transactions on Machine Learning Research (03/2026)
By convexity of f, we have [[f(())]] < (2L)(f(z)) -f which together with the definition of Va+1 in 46 yields that for & 2 K and 0 < 8 S C./T.
VK Vi+i watilanna ((Ls)s(((zH)) - f*) wa-1aaā (1- C
L8 s(f(2)) -M))
Okk
Because limg we is 1 or 1/7 0 in the Choice 1 or 2 above, and lim, āz/ax = 0, reset K large enough such that the above is further bounded from below as
1 [ A 1) (27)))((((EE) - f*).
VK 2 Va+1 2
By resetting Co
2-2/2 20
17. have that for k 2 K and 0 <<85 Co/L,
Vk 2 Va+1 2 1 _ a (f)x))) - f*). f*).
Using Lemma 8 we have f(xx)- - f O(Vx (VVVx((ak@xs)) = O(Vxx = -11000---1000 - -sk?)) which is the optimal rate 166
Finally, we complete the proof of 18) for the squared gradient norm. For k 2 K and 0 <<s S Co/L, using
Va+1 Vx= s
we have
C
k
C <
8²
min 0Sisk-1
[ff()))
Σ
-V--)- = Vx - VV+11 S VK.
2
2 1=
i K
which together with Lemma implics that for k 2 2K,
2VK
4VK
24Vx
| - x= x=11
min 0sick-1
[+)(()))
< Cs2 St 12
=0
Csa Σ 12
Cs 1) 1)
52k.
which is the desired bound 18
D.4 Proof of Lemma 1
First, we show 04 [(k) When & odd, 0% (1+ /1 40 1/2> (1+20x-1)/2 -1-2--))11--
(k rr+ - 1)/r + 1/2. So for any > 0, 0g = =[((k-
Second, we show 19 on 1) S a for k 2 1. When & is odd, by construction 19 holds. When
k > 2 and A is even, k 1 is odd and k - is even. Then aş (k + r)/r and at-1 (1+ 2/2
(1 + vr2 + 4(k + r - 2) /r) Simple algebra yields
4-r x2
rk+r-2)=+
1
2 r
2
an - 1) 0
(63)
2
When r 2 4,
63 is nogative for all k. For < r < 4, we further rearrange
63
as
(4 - r)=2)222- - 72((((+)))))) (
r- 2
2 (1 r)l: + r (k+r- 2)2 + -t2
r
8(r - 2)/² + 2r - 2)k + p2 ((r - 2) + x
2
r
22 (4-r)k r)k + rrv +r 2) _"2
2
44

---

Published in Transactions on Machine Learning Research (03/2026)
which remains negative for < < 4 but blows up to do as + 0o if 0 < 2.
Third, we calculate lim; k(1 x++1) along {k'} = {2k} and {k"} = 12k + 1}. By the definition of x++1 we
have
lim & (1 1 R++00
k
lim k(1 0k+11 8+000
lim R0000 ax+1
(ak+1 Or 1)-
(64)
ax+1
Along {K' (2k},
2k
4k
4k
4k
lim
lim
lim
lim
0-2k+11
1 1+ / + 4a2z
2012
2(2k: + r)/r
and
1
1 V 1
+ 4azx
lim 02k41 022
lim k++00
02k
1
lim
+ 1+-22
1+
022k
k-+00
2
4a
1
1
lim k+000
2
+ Or2k
1 0
2h
2
02k
2
Using
64
have
lim (11 x2(+1) r(1 + 1/2) 3//2. k+000
(65)
Along {1") = (2k + 1},
2k +1 lim
2k + 1
lim
= =,
10+00
022442
ko
(2k + 2 + r)/r
and
1 / 40
lim 0:2k+2 022411
lim
02k+2
4++00
k-+00
lim 02k+2 2
+
20
+
k+000
4
k-100
lim 022++
2
02k
1 1
0
02k
2
2k
2 +
2k r
lim
k-+00
r
2
1
r 2"
Using 64
we have
(2 =r(-) +1 2
lim k1 - =1(1-0k'41) =
(66)
k" +00
Lastly, combining the limits
65 and 66 gives lim Øk+1 1, which implics that lim 0x41/ax Therefore, condition (ii) holds. The proof of Lemma completed.
45

---

Published in Transactions on Machine Learning Research (03/2026)
E
Technical details in Section 4
E.1
Convergence of ODEs 23 and 25
In the convex setting where f E FF, the convergence rates of gradient flow (23) and the ODE 24 for NAG-C are proved in Su et al. (0116). . For completeness, we present the proofs for the convergence rates stated in the strongly convex setting where Sy.
For gradient flow 23 consider the Lyapunov function V, = ((x)) -*, i.e., the potential gap itself. Then
by 23 have V.
(V)( -II)f( By strong convexity, f(X,) f - 1 [X,))]
24
f f Therefore, V S (f f*) 22 which implies that f(X,) (*).
V1 S Vo.e 2nt 2 (f (f(x))
For the ODE 25 corresponding to NAG-SC consider the Lyapunov function V, - f(X)) - f + +
(u(X, x²) Then Vo f - f + マ/2 100 112 $ 2(f(2o) - f*) by strong convexity. Using the ODE
25
have
dV
(V/(())), X,) (X, + VT(X, - xx), 8, VTX,)
dt
(VV(()), - (X, + v - =2"), VTX, + vf(x.))
=-VA|X,11 V vu(X, - -x")) VPlXx -x', vf(x,).
which together with the inequality (X, x', v((()) 2 2 f + #1 x01 by j-strong convexity suggests that
dV dt S
VB |x VP (((x)) -f + vT(X, + (xxx)1>>111) S -VVV.. -
Hence, ((Xi) l < V/ e Via 2e -e (s(xo) 1
E.2 Proof of Proposition
For the existence and uniqueness of the solution X, to the ODE 26
define
Y,,
X,
Y1
E 1R
Y1
X,
Then the original ODE can be reformulated as
Yr2 -CI co vf(r.))
] F(1, Yz),
Y =
with initial condition Yo (xz, 0)", where
Y2 F(t,Y) -CIVTY - co vf(ri) ].
Because f I-smooth, Vf is T-Lipschitz continuous. Hence, F is Lipschitz continuous in Y. Because F does not depend on i, F is globally Lipschitz continuous in Y. By Picard Lindelöf Theorem, the conclusion follows.
For the convergence rate, consider the Lyapunov function
V = c=xx,) - I.x. + AVA((x--x)))
where À is be chosen later. Using the ODE we have
dV. = cvVVV(())) + (X. A x*), +
dt
46

---

Published in Transactions on Machine Learning Research (03/2026)
co co(Vf(X)) X1) + (X, + - -9) ao V)(())
- V X 1| (c1 VVV.I COAVH(( x², Vf((x.)
CI - X X, 2| - VAlXA + WTT(,
X x2 || x01
((1X,-x''1 -
2
cud/p(( x", vf((x))
9-1 vTlxx112 (9-1
C
-CVVV 2
x111
2
2
x X2 1 || 111 -AOVVM(X - x², vf(()))).
+ +Coovu(((X)) f*) +
which together with the incquality (Xe- - x", vf(x,)) 2 f(x)) suggests that
8 + +1x, - x²1 by j-strong convexity
dV. dt S -CVVV
Ci -
C1 (a-> C
(2
VTl + AVT(X, -
2
2
Au
- -(-x))a -*)
(co (cl X) - ==11
2
Because cp > 0 and et 0, we pick À such that << < a and (er AJA S co- Moreover, we pick C such
that 0 C S (c1 A) A X. Then
dV dt -CVVV = V3 S Vo eo -Cjut
In particular, if of S 4co, we pick A = 0122 and C = c1/2. Tf of > 4co, we pick A 01 of 400 and
C= /03-00 Equivalently, C= 9- (c-V(cc-ocoli > 0. The conclusion then follows by bounding Vo = 2 colf(zo) - -1))+ + - 100 - x+1 & (co + (f(an) - )*) because -||=0 - 11 - f(0a) f*.
2
When co S 0 or c1 5 0. fX,) ff is not guaranteed to converge. A simple counterexample the harmonic oscillator, with f(x) pa²²/2 /2 for IR,
X, + avTx + copu, 0,
(67)
starting from the initial position X(0)= = xn with velocity x() = 0. Since 67 is second-order linear ODE
with constant coefficients, its general solutions admit closed forms. Consider the characteristic equation w² ci /To + cofu 0 with discriminant A = (cî 4co)
If eî = 4co, then there are two identical real roots wr w W22 - / and X, (ag taite) for some real numbers og and o1- By the initial condition X()) = 0, we find an -og.. Then X, ao wi wt
To achieve X, + 0, we need < 0, which means e1 0 and co- of /4 > 0 too.
If of 4cg, then there are two distinct real roots wT - 10a Vi and w2 = -9- -e--ve--o 1cg
Vū, with
2 Wi > u2, and X, at + "2t By the initial condition x = 0, we find aowi +aw = 0. If W2 0, then wi > 0 and hence an = and X, = an = To, which contradicts X, - 0 for any Do # 0. If w2 # 0, then a = - an w/ hawwi/ww /w2, and X, = an w> ==+) with wi * w2. To achieve X, + 0, we also need W/ < 0.
2
Then -c1 / 4co < O, which implies that co > 0 and e₁ > 0.
If c < 4co, then there are two complex roots W1,2 = -c + 40o -ff VT, and X, is linear combination of - vmt/2 x sin( u((cc - ())) and e /T/e/2 cos( h pu4co - ttt/2). We need 6 > make X, + 0.
Then 6p > of/ / too.
47

---

Published in Transactions on Machine Learning Research (03/2026)
E.3 Proof of Proposition 4
The existence and uniqueness of solution were proved in Shi el al. 22022 Proposition 1, and thus omitted. Below, we focus on the convergence rates. For 27 we consider the Lyapunov function
1 2 11x++ VT(X, x²) + (XVS(X))1.
Vi = (1 + (Xx) - 54)
Using the ODE 27 we have
dV: dt
(1 + vus) (V
(X, Vu(X, - x¹) (VVS(()) VuX, VsV
= (1 + V (V)(),), Xx) (X, (XX
VTx. - -1+ ((S)V
=-VAIIX,11- vT((e
VVV (VV(())) (1+ (V VX -²)) + (xV)(X)))
v/ -V"" 1X.11 //
2 -1x: + x1)+ + A/ IIVa x²) + (xVS(X))1
2
2
-(1+ Vus)//((x x' - Vl=) V ((x)(
-VVVV + VM(1 + Vas) (S(,)) - /²) v/
|x,11 + /
| xx x=1 V -x.
2
2
- -Vi(1+ 2 IX))11
By the strong convexily, (X, - xt, Vs((.)) 2
- 1²1
Then the above display yields
dV:
df S - VTV, + VTVTS(((X)) /r) - V8(1 + VAS
2 [V
By the strong convexity again, we have f(x,) -r S 2/ | 11 Hence
dV.
v3 (1 + vus) \f - VuVe 2
dt Vun
The conclusion follows by integrating with t. we consider the Lyapunov function
For
28
11 (fxx) - f*) + 2 1 (p(X,-2*)11
Using the ODE 28 we have
dV:
(1 ps) (V X1) (8, V - x"), X1 + viXii)
dt
= (1 + ( (V, X,) (X, + VX((X,- - x²), VTX + (1 + f(x,)
-V, vi(Xe, M(X, - x²)) Vp(1 + V1s) (X: x,, (X))))
VH -HI
|x.1|
VH
|x + - x²] + 11²2
|X - x' 112 - -vi(1 + vX, - x", Vx(x)))
-
2
2
2
41
S --VPV + VF(11 + (fx)) - f*)
|x 211 vp(1 + vPs vX()))
2
By the strong convexity, (X.- x-, v((x)) 2 2(x))
8 + 11,, x x1 Then the above display yields
dV. dt
< ~vVV 1²² 5
1x 11123 -VVVe
2
The conclusion follows by integrating with 1.
48

---

Published in Transactions on Machine Learning Research (03/2026)
E.4 Proof of Proposition 5
The construction of our continuous- time Lyapunov function is motivated by Su et al, 2016 and Shi et al.
20222.
We consider the auxiliary-enerry term defined
V,A
1 2/2 ,Xx, - xx)+ 2
-(xx-
+ (x++ BV8 v f(xi)) l|
Using the ODE 31 for t 2 to we have
dV
(r(X,-x') x²) + (Xx BV3 VX()))
3
((())) 1(x, + BV3 22 ((x))x))
V
dt
7
7
= (r((X, x²) + +(xx+ +
BV8
v.)))). -
r+1
8
7
2
--((t+
8
(8) (X+ x,, ('xxx)) ((t
-==1
3
Vo) vs(x.))
2
(1 (1 r+1 L |
Let C 2 0 be constant to be chosen later, and introduce a factor of ++Cv for technical adjustment. CVT is decreasing in l, we have Because 1+C//= = -1 1
d
1 C33 CH+ v.a)
d
1+ CV8
V.A (+CV8 dV. 1+
Av.
dt
t t C+3 (1-(1+1
dt t
dt
-
r+1 2 V) v((x)) (68) - (1 C1+ 2 [) (X+ x", VX(x))
(t (Vs)(C))((++++) +1 _ (
To eliminate the term of (X, v(()))), we define the potential-energy term
V.P = (1 (1+CV) r+1 -
--))))(x))))-> 8))
Then
dVF"" di = (2t + + ("+1_ 8 2 - +OW3)(((X)))))))
- 1o) + (t (t+
((
(++1 - 3 -
-V) (69)
Define the continuous Lyapunov function as V, = VPP + + Set 40 2e13= O. Then for 2 to we have V, and
r+1 8 [)5)) (t + CV3)(+++
2 1 1 2
/
(70)
2 4
Combining 668 and 69
obtain
dV.
+ C/3
r +1
2 -X - x. -x,,xx) +2t
r+1 B
+ +0)))(((())) f*)
dt
t
2 γ
3V3 7
(1+
( ++++
_ -/
r+1 B
2
49

---

Published in Transactions on Machine Learning Research (03/2026)
which together with the convexity inequality (X, x², Vf(xi)) 2 f(Xi) f suggests that for 2 0 and
2 l0:
dV.
rCv5 )
r r+1
B V -(f(x)) - -f)
(r
dt
2 7
B (t (++)) r+1 V3VXXI)
(
2
From 770 if 8 0, then II, - 2 0 for 1 10- It remains to deal with L.
When > 2, set C = 0. Then = (r - 2) (r 1) V 0 for t - G) In this
case, we pick 1 = to V ( ( -
/3}
When 2, 1 C (1 - We set the constant C > 2 - (e.g., 2) Then when t is
large (e.g., 2
37 7 V I, 2 0 always holds. In this case, pick 4 = 1o v ( V)
49 8
To summarize, when r 2 2 and 2 0, there exist C 2 and h such that when t 2 h1 dV.
S 0. If further
di
0 0, then dV. 2 8/3 (X))( The remaining proof is similar to the proof of Theorem continuous way. We sketch the reasoning below.
4 but in a
If dV: at < 0, then for 2 t
r+1 3 (
- (f(())- ff),
V. 2 12 = (t+
- -
2
V1 P
which implies that f(X,) - f =
If further de 2 3/3 || (Xx,)) with 9 > then for t1, we have V 0, and
47
7
V1 2 Vo V,- (-V)) - (-Vi,) / d (-Va)du
BV3
4y I" u² (X.))
du
2 3/8 inf
|VS((x))I / uddu
3/ -
inf
|VS(x,))
4y ususe
12%
G
which implies that
12yV,, = =0
(0
VV,,
inf |[ 4: Sugt
B - -it B
F Technical details in Section 5
F.1 Single-variable form for HAG 32
solving the first equation for uk, and plugging the expressions of uy and u&+1 into the sccond equation, we obtain
We derive the single-variable form 34 for HAG. From 32
Øk+2 Db+t + ax+1 Vf(x++1) (by- -1) Tkt1 FA + aA (f(K))
/ Vanba -V/
/0t+1bb41
Varba
Rearrange the above display to conclude.
50

---

Published in Transactions on Machine Learning Research (03/2026)
F.2 Verification of monotonicity condition for (39)
We verify that the monotonicity condition in Theorem is satisfied by (39 Lee, HAG under the configuration First, we notice that (39 can be put into 21 with
38
Bk-1
c2//00
Co
Yk co ( bk-1
1 + ba)
0k+1 - -1k
bk-1
ak+1
When as - we have ak+1 loss of generality, take co 1. Substituting ok+1 we obtain
a--1
k+r+I
b + ak+1
2k+r+1 and Ch11 k+++1, Without k+r+1 ae k+r
act!
bk- and by into the display above and after some algebra,
0+++1
3k
ak+1
-1 1 = 7k
k+r+1
3k k kr
ai
2h + (7 - 202
4r)k + 6 302
Tr C2T + 2n²
(k + (2k +
which is monotone when & 2 K for some K depending only on 62 and
51


Reviews:
[{"review_id": "HxrYN5I5zf", "reviewer": "Reviewer_es1t", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "# Summary Of Contributions\n\nThis paper introduces a class of accelerated gradient-type methods for smooth (strongly) convex optimization. The convergence analysis is conducted via a Lyapunov-based approach, yielding sufficient conditions on the algorithmic hyperparameters to achieve standard $\\kappa$-dependent rates as well as accelerated $\\sqrt{\\kappa}$-dependent convergence.\n\nIn subsequent sections, the authors demonstrate that ODE-based analyses of accelerated methods fail to fully capture their discrete-time behavior. The paper further establishes connections between the proposed class of accelerated algorithms and Hamiltonian-inspired descent dynamics.\n\n## More detailed summary\n\n- The paper studies accelerated first-order methods for smooth convex and (strongly) convex problems. It introduces two classes of discrete algorithms:\n\n    - In Section 2, the authors introduce a three-point scheme (10) for the smooth, strongly convex setting. This scheme is equivalent to the one-line formulation in (11). It is controlled by three nonnegative parameters $\\eta,\\nu,\\tau$, and different choices of these parameters recover various existing optimization methods. For example, NAG-SC corresponds to (1,1,1), and TMM corresponds to (1,1,2). In general, the choice of those constants affects the ratio between gradient, momentum, and gradient correction terms in (11).\n\n    - In Theorem 1, the authors establish convergence guarantees for optimiality gap $f(x_k)-f^*$ under certain step-size restrictions on $s$, together with a specific relation among the parameters $\\eta,\\nu,\\tau$. Depending on how these conditions are instantiated, the resulting convergence rate can be either accelerated or non-accelerated.\n    - Considering a one-line formulation, the relation between parameters $\\eta,\\nu,\\tau$ is summarized in the choice of $c_1 > 2, \\tilde{c}_2 \\ge 0.5$ in Proposition 1. \n\n    - In Theorem 3, the analysis is then extended to the setting in which $\\eta,\\nu,\\tau$ are allowed to depend on $q=\\mu s$. In this case, the constraints are imposed on the coefficients of the Taylor expansions of $\\eta,\\nu,\\tau$ with respect to $q$ (note that under this more general parametrization, the number of admissible choices is smaller than in the previous, constant-parameter setting).\n\n- Next, the authors switch to a smooth convex setting.\n    - Similarly, in the general convex case, they define a class of algorithms (22) parameterized by sequences $\\{\\alpha_k\\},\\{\\beta_k\\}, \\{\\gamma_k\\}$ that covers NAG-C, FISTA-type methods, and variants studied by [Shi et al. (2022)].\n    - In Theorem 4, the authors provide a cubic rate $O(1/k^3)$ for the squared gradient norm under the restrictions on the step-size and the sequences above. The authors also provide examples when the restrictions on the sequences is satisfied.\n\n- Comparing discrete algorithms to low- and high-resolution ODE limits, the paper argues that even high-resolution ODEs fail to fully explain the discrete dynamics. The authors claim that the gradient correction term is vital for achieving acceleration. However, in continuous time, its effect is neglected. Therefore, such models cannot always be used to inform whether the discrete counterpart achieves accelerated convergence.\n\n- Finally, the authors propose a Hamiltonian-assisted gradient method (HAG) (Section 5), derived from minimizing a Hamiltonian $H(x,u) = f(x) + 0.5\\|u\\|^2$. They show that previously discussed algorithms can be seen as particular HAG discretizations, giving a more interpretable view of the role of momentum and gradient correction.\n\n- In Appendix E, the authors numerical simulations to support their theoretical claims.\n\n\n## Strengths\n\n- To some extent, Corollary 1 gives interpretable conditions that are needed for achieving acceleration. The authors claim that if the momentum term ($c_1^2 > 4c_0$) and gradient correlation term ($c_2^2>c_0$) are strong enough, then the algorithm achieves accelerated convergence. If the momentum term is as strong as before, but the gradient correlation term is not ($c_0/4 < c_2^2 <c_0$), then the algorithm achieves only a non-accelerated rate.\n- The authors provide a unified framework to study acceleration that also covers previously introduced algorithms as special cases.\n- The work clearly shows that limiting ODEs (even high-resolution ones) can be misleading: they may accelerate under very weak constraints (e.g., $\\beta/\\gamma > 0$ in Proposition 5), while the discrete algorithms require a much stronger gradient-correction condition (e.g., $\\beta/\\gamma>0.5$ in Theorem 4) to achieve analogous rates.\n- The HAG part of the work provides a mechanical/energy-based interpretation of the momentum (updates of $u$ term), gradient correction (some sort of additional \"friction\" term), and how parameter choices control damping regimes (over/critical/under).\n- The proofs look correct to me; I did not find any critical mistakes. \n\n## Weaknesses\n\n- The authors claim to explain the acceleration mechanism, but their analysis only provides sufficient conditions for achieving acceleration. It remains unclear whether other parameter choices might also yield accelerated rates, or whether all remaining configurations always lead to non-accelerated convergence or divergence. The presentation would be stronger if the authors established some form of lower bounds or impossibility results for the other parameter regimes, demonstrating that their conditions indeed characterize all possible choices that enable acceleration. In the current form, I suggest reformulating the text to align with the actual results. \n- The authors should also provide numerical evidence that they covered all possible configurations that lead to acceleration. \n- I believe it is already known that ODE-based analysis does not recover well the discrete dynamics. What is really important is to show that ODE models are still good at approximating the discrete dynamics in practice or providing changes/modifications to ODE models so that they track discrete dynamics better. For example, [1] make changes to SDEs so that at least step-size restrictions are recovered. Can it be done in this work as well?\n\n    [1] Compagnoni, Enea Monzio, et al. \"On the Interaction of Noise, Compression Role, and Adaptivity under $(L_0, L_1) $-Smoothness: An SDE-based Approach.\" arXiv preprint arXiv:2506.00181 (2025).\n\n\n\n- Experimental results in Figure 3 look strange to me. Algorithms fail to recover the original error. Why do we observe such weird dynamics?\n\n- Overall, the paper is not well structured and is difficult to follow. The notation is extensive, and the reader is required to keep track of many symbols throughout the text. I recommend adding a notation table in the appendix to help with clarity. In addition, parts of the introduction should be rewritten to improve readability and correct several grammatical issues.\n\n- In the convex case, the convergence rates are given for the gradient norm, while a more standard convergence measure is the function suboptimality. I encourage the authors to explain why it is the case.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors provide clear convergence statements and a discussion around the results. The convergence guarantees extend existing ones in the literature in a unified manner, providing more intuition on when the acceleration is possible. The results are made more interpretable using the HAG framework.", "audience_yn": "Yes", "audience_explanation": "Yes, this paper examines the acceleration of optimization algorithms, a crucial research topic as these techniques enable faster convergence and improved performance in many practical applications.", "requested_changes": "## Comments and Suggestions\n\n- Add a table with the results that are derived in this paper in some special cases, and how they align with prior work. For example, for NAG, the paper recovers acceleration of prior work, but the Heavy-ball method is not covered by the framework at all. Such a table would help to give a quick overview of the generality and limitations of the proposed theoretical framework.\n\n- I suggest moving some numerical results to the main part or at least providing links to them to increase the clarity of the work. \n\n- In the introduction, the authors already use the term \"gradient correction\" without introducing it. In my opinion, such a term is not standard in the literature, and it should be defined.\n\n- Please also check the suggestions in the previous sections.\n\n- On page 3, the authors use the term \"meaningful conditions\". I suggest avoiding such wording without giving a precise description. The same applies to the wording \"It seems to be an open\" question \n\n- Can the authors provide other examples in the convex case, where $\\alpha_k$ is not necessarily linear? According to Proposition 2, we should have $\\alpha_k = \\Omega(k)$. Can we choose something else?\n\n- Can the authors provide a discussion on the results in [2]? Does the current theoretical framework cover the results in [2]? I believe that the authors should include the discussion around [2] in the paper. \n\n    [2] Goujaud, Baptiste, Adrien Taylor, and Aymeric Dieuleveut. \"Provable non-accelerations of the heavy-ball method: B. Goujaud et al.\" Mathematical Programming (2025): 1-59.\n\n\n- I suggest not using terms $\\eta_0$, etc, in Theorem 1, as they are later used in Theorem 2 with a different meaning. I would simply say that $\\eta$ is constant\n\n- Is there any reason why the theoretical framework does not cover the original Heavy-ball method? Can the authors elaborate more on this point?\n\n- I suggest adding the definitions of (strong) convexity and smoothness at least in the appendix and referring to them in the theorem statements.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Hruy6qZdx5", "reviewer": "Reviewer_FgrT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Summary.**  \n\nFirst, the authors consider two parametric families of algorithms obtained by augmenting gradient descent with two additional terms: (i) a momentum-like term proportional to the difference between the current and previous iterates, and (ii) a correction term proportional to the difference between the current and previous gradients. For the first family, they derive parameter conditions that guarantee acceleration in the smooth, strongly convex setting. For the second family, they establish parameter conditions that yield acceleration in the smooth, convex setting.\n\nSecond, they analyze the limiting low- and high-resolution ODEs associated with these algorithm families and compare their convergence bounds with the discrete rates, noting that the ODE viewpoint does not directly determine the stepsize regimes that separate accelerated from non-accelerated behavior. They also observe that gradient-correction terms vanish in low-resolution limits and that, even when retained in high-resolution ODEs, the resulting continuous dynamics can converge at the same rate with or without the gradient-correction term.\n\nFinally, the authors introduce and motivate the Hamiltonian-assisted gradient method (HAG), a parametric family of algorithms in the same spirit as the two families above. They show how HAG connects back to those families through specific parameter choices, and use this connection to translate the earlier acceleration conditions into corresponding constraints on HAG’s parameters. \n\n**Strengths.**\n\n- Common Lyapunov framework across several known schemes.\n\n- ODE discussion usefully stresses what it cannot predict.\n\n**Weaknesses/limitations.**\n\n- Key arguments require substantial rereading/cross-referencing.\n\n- The prose leans promotional rather than descriptive; it should be tightened to match the actual evidence. \n\n- The framework-level Lyapunov treatment seems to trade off tightness: constants/results are weaker than what method-specific Lyapunov analyses typically provide.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The central claims appear supported by correct proofs. However, the presentation is not consistently clear (requiring substantial rereading and cross-referencing), contains minor typos, and would benefit from more measured language to better match the evidence; I further elaborate below.", "audience_yn": "Yes", "audience_explanation": "This paper is primarily relevant to the convex optimization theory community, especially readers focused on first-order methods and worst-case complexity. It offers a Lyapunov-based synthesis that casts several classical schemes within a common set of parameter conditions separating accelerated from non-accelerated behavior, and it includes a few negative/limitation observations (notably around continuous-time viewpoints) that can be conceptually useful. For readers already familiar with tight, method-specific Lyapunov analyses and with worst-case optimal schemes, the main value here seems to be the common perspective and clarification, rather than new algorithmic design principles or improved guarantees; correspondingly, the framework-level treatment appears to trade some tightness in constants for generality. Overall, I expect the paper to be of interest to a focused subset of TMLR’s optimization audience.", "requested_changes": "1. [Minor] The term “unified” is used excessively throughout the manuscript (e.g., “unified condition”, “unified interpretations”); consider replacing it with more specific descriptors.\n\n2. [Minor] I also recommend avoiding the term “simple”. What counts as “simple” is subjective, and in several places it can read as advertising rather than exposition. Where you intend to convey ease or accessibility, please replace it with objective descriptors or present the argument without a qualifier.\n\n3. [Minor] The adjective “novel” is not necessarily overused here. However, any meaningful contribution should be novel by definition, so explicitly advertising “novelty” is redundant and can read as promotional.\n\n4. [Minor] Please provide a link to the code used to generate the numerical results (including experiment and plotting scripts).\n\n5. [Minor] Consider using “acceleration” (instead of “Nesterov’s acceleration”) throughout for more neutral terminology. \n\n6. [Critical] Please add explicit sign/range conditions for all scalars appearing in formal statements (propositions, theorems, corollaries, lemmas), so each statement is well-posed without relying on surrounding text (e.g., $L>0$ rather than just $L$, and that $\\\\mu>0$ is such that $\\\\mu \\leq L$).\n\n7. [Critical] In Proposition 1, please define/introduce all symbols before first use (in a logically sequential order), in particular $f^{\\\\star}$, $x^{\\\\star}$, $s$, $L$, $\\mu$, $c_{1}$, and $\\\\tilde{c}_{2}$. A similar issue appears in other propositions/theorems/lemmas/corollaries; please ensure each formal statement is self-contained with respect to notation.\n\n8. [Minor] Use $\\\\star$ (\\star) and not $\\*$ throughout for optimality, e.g., \"$f^{\\*}$\" $\\\\rightarrow$ \"$f^{\\\\star}$\", etc.\n\n9. [Critical] In the smooth and (non-strongly) convex setting, several formal statements and discussions are phrased in terms of a minimizer $x^{\\\\star}$, which implicitly assumes that the minimum in Eq. (1) is finite and attained. Please make this explicit (in all relevant formal statements) by assuming\n$$\n\\\\mathop{\\\\mathrm{Argmin}}\\\\limits_{x\\\\in\\\\mathbb{R}^n} f(x) \\\\neq \\\\emptyset,\n$$\nand, for clarity, fixing notation by choosing\n$$\nx^{\\\\star} \\\\in \\\\mathop{\\\\mathrm{Argmin}}\\\\limits_{x\\\\in\\\\mathbb{R}^n} f(x),\n$$\nso that $f^{\\\\star}=f(x^{\\\\star})$ is well-defined. In the $\\\\mu$-strongly convex setting, existence (and uniqueness) of $x^{\\\\star}$ is implied, so no additional assumption is needed there; however, $x^{\\\\star}$ and $f^{\\\\star}$ should still be clearly defined when first introduced.\n\n10. [Minor] Page 1: “In fact, Nesterov (1983) used a potential function or a Lyapunov function to establish the convergence of the first accelerated algorithm”. I recommend avoiding the word “first” here unless it is carefully qualified (as written, it reads as historically incorrect).\n\n11. [Critical] When stating an algorithmic update rule, please explicitly specify the index range for which it is valid, and separately clarify any initial step conventions when they differ. This small bookkeeping detail makes the scheme unambiguous and easier for the reader to follow, especially when the $k=0$ and $k>0$ cases require different handling.\n\n12. [Critical] I strongly recommend that whenever a function is introduced (e.g., in any formal statement), the authors explicitly state its domain and codomain, e.g., write $ f:\\\\mathbb{R}^{n}\\\\to\\\\mathbb{R}$ rather than referring to it only as $f$. This improves precision and makes the notation easier for the reader to parse consistently throughout the paper.\n\n13. [Minor] There is a formatting typo on page 14.\n\n14. [Critical] Appendix B.3: The “uniform” lower bound should take the minimum of the two possible limits of $\\\\omega_{k+1}$ (since $\\\\omega_{k+1}\\\\to 1$ or $\\\\omega_{k+1}\\\\to 1/\\\\gamma$), so replace $1/\\\\gamma \\\\vee 1$ with $1/\\\\gamma \\\\wedge 1$. \n\n15. [Minor] Page 20, Section 6.2 “Step 3”: “As expected from (45), We further bound ...” → change “We” to “we”.\n\n16. [Critical] Step 1 before Lemma 2, Section 6.1: There is a difference written with a missing square, i.e., $\\\\frac{1}{1-\\\\nu\\\\sqrt q}\\\\frac{\\\\mu}{2}\\\\|z_{k+1}-x^\\\\star\\\\| - \\\\frac{\\\\mu}{2}\\\\|z_k-x^\\\\star\\\\|^2$. The first norm should be squared, i.e., replace $\\\\|z_{k+1}-x^\\\\star\\\\|$ by $\\\\|z_{k+1}-x^\\\\star\\\\|^2$. \n\n17. [Critical] Well-posedness of the ODEs (existence/uniqueness): In Section 4, multiple results refer to “the solution” of ODEs (23), (24), (26), (27), (28), (30), and (31) under assumptions such as $f\\\\in \\\\mathcal{F}^1$ or $f\\\\in \\\\mathcal{S}^1_\\\\mu$. Since $\\\\mathcal{F}^1$ here does not include Lipschitz continuity of $\\\\nabla f$, and since (24)/(30) have a $1/t$ singularity at $t=0$, it would help to add a brief remark (or citation) clarifying the existence/uniqueness (and whether global-in-time) of these ODE solutions under the stated assumptions, and how the initial condition at $t=0$ is interpreted for the singular-damping equations. If additional regularity assumptions are in fact needed for well-posedness, please state them explicitly in the corresponding formal statements (propositions, etc.).\n\n18. [Critical] Note that the constant $C$ in Proposition 3 and in its proof differ by a factor $2$, which might confuse readers. Please update to make it consistent. \n\n19. [Minor] Spelling: “Cauchy-Schwartz” should be “Cauchy-Schwarz”.\n\n20. [Critical] In Sections 1–3, several results assert the existence of positive constants $C_0$ and $C_1$. In a number of cases, your proofs appear to yield explicit formulas for $C_0$ and/or $C_1$; where this is possible, it would be helpful to state those expressions explicitly in the corresponding theorem/proposition/corollary (or in a short remark). \n\n21. [Minor] I suggest writing simply “convex” rather than “general convex” (and, if needed for contrast, “convex (not necessarily strongly convex)”). Motivation: “general convex” is largely redundant/nonstandard, since “convex” already covers the non-strongly-convex case.", "broader_impact_concerns": "I do not see any concerns regarding the ethical implications of this work that would require adding or expanding a Broader Impact Statement.", "additional_comments": "It would be helpful to acknowledge the established line of work that leverages performance estimation problem (PEP) techniques to automatically construct and certify Lyapunov/potential-function analyses by solving convex semidefinite programs, often yielding tight convergence guarantees. This is closely related in spirit to your work and should be cited (and, ideally, briefly differentiated). Suggested references:\n\n   - A. Taylor, B. Van Scoy, and L. Lessard, *“Lyapunov functions for first-order methods: Tight automated convergence guarantees”*, ICML 2018.\n   \n   - A. Taylor and F. Bach, *“Stochastic first-order method: Non-asymptotic and computer-aided analyses via potential functions”*, COLT 2019.\n   \n   - M. Upadhyaya, S. Banert, A. Taylor, and P. Giselsson, *“Automated tight Lyapunov analysis for first-order methods”*, Mathematical Programming, 2025, doi: 10.1007/s10107-024-02061-8.", "extra_scores": {}, "extra_text": {}}, {"review_id": "nfIf8hE2LV", "reviewer": "Reviewer_X4M3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates first-order accelerated optimization algorithms, focusing on how gradient correction affects acceleration. It introduces: 1. Two general algorithmic classes (for strongly and general convex functions) 2. New discrete Lyapunov analyses giving simple, unified sufficient conditions for acceleration 3. Comparative analysis with limiting ODEs (including high-resolution ones), highlighting mismatches between discrete and continuous behaviors. 4. A Hamiltonian-assisted gradient (HAG) interpretation that unifies the roles of momentum and gradient correction.\n\nThe central claim is that a gradient correction coefficient ≥ 1/2 is necessary and sufficient for accelerated convergence—an elegant, interpretable threshold connecting Nesterov’s and Heavy-ball methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The Theorems and propositions in this submission are precise, internally consistent, and compatible with existing theory. The analytical treatment is sophisticated yet careful about assumptions (analyticity, strong convexity, Lipschitz smoothness). The authors has presented all the mathematical proof and analysis in this submission.", "audience_yn": "Yes", "audience_explanation": "This submission provide novel theoretical insights providing the first explicit quantitative condition for acceleration across both convex and strongly convex cases. It identifies the gradient correction term’s magnitude as a key mechanism behind Nesterov acceleration. The authors provided rigorous Lyapunov analysis and the proofs avoid reliance on LMI-based frameworks, showcasing a hand-crafted, conceptually clean Lyapunov construction. The results are broad—covering both constant and analytic parameter cases—and include clear boundary conditions for accelerated vs non-accelerated convergence. The comparison with high-resolution ODEs reveals a discrepancy: ODEs (even high-resolution ones) fail to explain acceleration fully. This observation is theoretically important for researchers relying on continuous analogies to justify discrete algorithmic acceleration. The authors provide the Hamiltonian-assisted Interpretation where the HAG formulation introduces a physically inspired perspective connecting optimization to mechanics. It provides a clear interpretation of gradient correction in terms of momentum updates within Hamiltonian dynamics. This submission is written in clarity and rigor. The exposition is methodical and well-structured, with explicit assumptions, notation, and stepwise derivations. And all the results (Propositions, Theorems, Corollaries) are logically interconnected and self-contained.", "requested_changes": "Here is the changes that the authors should provided in the revision:\n\n1. There are some limited practical implications in this submission. While the theoretical contributions are strong, the paper lacks practical algorithmic takeaways—e.g., how to design or tune new methods in practice. The numerical results (in Appendix E) are not discussed in the main text, limiting empirical validation.\n\n2. There are some notation issues in this submission. The paper is notation-heavy, especially in Sections 2.2 and 3.2. It may overwhelm readers without strong mathematical backgrounds. The authors should introduce small motivating examples (e.g., 1D quadratic cases) before the general theorems could enhance readability.\n\n3. There are some missing discussion of related works in this paper. Recent developments in control-theoretic optimization and variational perspectives (e.g., symplectic integrators, stochastic extensions) are mentioned but not deeply compared. The paper could better clarify how its results differ from or extend Shi et al. (2022) and Sanz Serna & Zygalakis (2021) beyond technical refinements.\n\n4. Hamiltonian section should be expanded more in the paper. The HAG interpretation is promising but underdeveloped. A deeper analytical connection between HAG updates and discrete acceleration (perhaps via an energy decay analysis) would make this section more impactful.\n\n5. The authors need to provide more clarity in physical interpretation. While the Hamiltonian framework provides intuition, the mapping between mechanical analogies (momentum, damping, potential) and optimization behavior could be elaborated.", "broader_impact_concerns": "This is a pure theory submission. There is no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)