Convergence analysis of ODE models for accelerated first-order methods via positive semidefinite kernels
Authors: Jungbin Kim
Insoon Yang
Venue: NeurIPS 2023 poster (2023)
Keywords: convex optimization
accelerated gradient methods

Abstract: We propose a novel methodology that systematically analyzes ordinary differential equation (ODE) models for first-order optimization methods by converting the task of proving convergence rates into verifying the positive semidefiniteness of specific Hilbert-Schmidt integral operators. Our approach is based on the performance estimation problems (PEP) introduced by Drori and Teboulle. Unlike previous works on PEP, which rely on finite-dimensional linear algebra, we use tools from functional analysis. Using the proposed method, we establish convergence rates of various accelerated gradient flow models, some of which are new. As an immediate consequence of our framework, we show a correspondence between minimizing function values and minimizing gradient norms.

Convergence Analysis of ODE Models for Accelerated First-Order Methods via Positive Semidefinite Kernels
Jungbin Kim Scoul National University kjb29520snu. ac.kt
Insoon Yang" Scoul National University insoonyangosnu ac kr
Abstract
We propose novel methodology that systematically analyzes ordinary differential equation (ODE) models for first-order optimization methods by converting the task of proving convergence rates into verifying the positive semidefiniteness of specific Hilbert-Schmidt integral operators. Our approach is based on the performance estimation problems (PEP) introduced by Drori and Teboulle S Unlike previous works on PEP, which rely on finteedimensional linear algebra, we use tools from functional analysis. Using the proposed method, we establish convergence rates of various accelerated gradient flow models, some of which are new. As an immediate consequence of our framework, we show a correspondence between minimizing function values and minimizing gradient norms.
Introduction
We consider the following convex optimization problem:
min f(x),
ZER
where f Fd R is a continuously differentiable (μ-strongly) convex function. We assume that a minimizer x² exists. First-order methods, for example, gradient descent and Nesterov's accelerated gradient method, are popular solving this problem due to their low cost per iteration and dimension-free oracle complexities. These methods can be analyzed by examining their limiting the gradient flow (1) = - (I) Building upon this idea, Su el al. 33 derived the limiting ODE for Nesterov's 's accelcrated gradient method (AGM) [27] and analyzed its convergence rate, offering valuable insights into camentum-basee algorithms. A common approach to establishing convergence rates of continuous-tiin time ODE models involves using Lyapunov functions 23
ODEs. For instance, the gradient descent IA+1 F4 fVx( corresponds
In this paper, we propose a generic framework that builds upon the performance estimation problem (PEP) presented in [ for analyzing the convergence rates of ODE models for various accelerated first- order methods, including Nesterov's 's AGM. The proposed method designed from the Lagrangian dual of a relaxed version of continuous-time PEP. Consequently, our framework transforms the task of proving convergence rate into verifying the positive semidefiniteness Moreover, our framework can also ensure the tightness of the resulting guarantee, meaning that the obtained convergence guarantee is optimal among all possible convergence rates that can be derived from weighted integrals of the inequalities employed in convergence proofs. Using the proposed framework, we confirm the convergence rates of existing ODE models and uncover those of new accelerated ODE models. In traditional convergence analysis of ODE models, it can be challenging to design appropriate Lyapumov functions However, our framework, we only need to verify
specific integral kernel.
"Corresponding author.
"There is line of work focused on systematically finding Lyapunov functions, often with the assistance of computers. See Scction 1.1 for details.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the positive semidefiniteness of a specific integral kemel.. This approach circumvents the need for Lyapunov function design, making our framework more straightforward for analyzing convergence rates.
In the discrete-time setting, the PEP framework has been extensively studied for its ability to systematically obtain tight convergence guarantees 42] and facilitate the design of new optimization However, analyzing PEP is typically regarded as challenging to comprehend due to the involvement of large matrices with complex expressions. In contrast, our framework utilizes integral kernels, which serve as a continuous time counterpart to matrices. The computational process within our approach yields simpler outcomes. Consequently, our continuous- time PEP framework has the potential to offer valuable insights into the analysis of the discrete-time time PEP, similar to how ODE models have helped designing and analyzing saccretetime methods in the literature (20 47). By bridging the gap between the continuous and discrete settings, our methodology enhances the understanding of the PEP framework.
methods [17 18 40)
1.1 Related work
Continuous-time models for first-order methods. The investigation into the continuous timme limit of accelerated first-order methods began with the study of AGM ODE
36
2
3
Since
then, subsequent researches have explored various aspects of the ODE models. These include
generalizations within the mirror descent setup (20). broader family of dynamics derived using
Lagrangian mechanics [4 48 19]. high-resolution ODE models [4] 33 and continuized methods
[9]. Systematic methodologies for finding Lyapunov functions were developed, including deriving them from Hamilton's 's equations [6] or dilated coordinate systems [37]. For obtaining accelerated discrete-time algorithms, several studies have applied discretization schemes, such as symplectic 44 and Runge-Kutta 49 schemes, to discretize accelerated ODE models. [32 showed that applying
multi-step integration schemes the gradient flow also yields accelerated algorithms. A particularly relevant study is [19]. as they present the dynamics in the form of 44) using the H-kernel, which plays a crucial role in our analysis.
Performance estimation problems. The idea of using performance estimation problems to analyze the convergence rate of optimization methods was first introduced by [8]. This concept was further refined by employing convex interpolation argument in [42] and was applied to wide range of settings in [5] 43
44
12
IT
7 16
The idea of performance estimation has been used to construct In particular,
Lyapunov functions in 41 However, their methodology differs from ours, as they employed semidefinite programs of finite dimension. Another closely related approach is based on integral quadratic constraints (IQC) from control theory [24], which were used to analyze the convergence rate of first-order methods in [21]. The IQC framework has been further studied in [14 15 I0 22 31). One practical application of PEP and IQC is the design of novel algorithms by optimizing the convergence guarantees. Some notable
39
23
45
25 analyzes continuous-ting ODE models.
examples include OGM 117. TMM 46). ITEM 40) and OGM-G [8]
Preliminaries and notations
In this section, we review some basic notions from functional analysis that will be used throughout the paper. For a more detailed treatment, we refer the reader to the textbooks [2 30, 28)..
Function spaces. We denote the set of continuous functions from [0, to Rd by C( TIR and the set of continuously differentiable functions from [0, T] Rd by C¹ [J: We de- fine the space [2, IRd) as the set of all measurable functions [0, T] - IRd that satisfy 5 lIf dr < cc. Then, (20, T); Rd) is a Hilbert space, equipped with an inner product and a norm defined by (f. (+( 5 (f(t). g(t)) dt and [P = V (f. 1)
Integral operators. An integral operator is a linear operator that maps function f to another function K given by
(Kf(t) = -[" k(t, ((t)))((T)d) dr.
(2)
2

---

where k [0, + R is the associated integral kernel. Intuitively, an integral kernel can be seen as continuous-time time version of a matrix. integrable, i.e., k E (1, ( R). When & is Hillbrtt-Schmit kernel, the associated integral operator K is a well-defined operator on ( 17; called a Hilbert-Schmidt integral operator. If Hilbert-Schmidt kernel k is symmetric, i... k(t, r) k(T, t) for all t, T E [0, 7', then the associated operator is also symmetric in the sense that fKf.9 g) (f. Kg) for all f.g L2 T]: R Throughout this paper, we will use the term 'kernel' to refer to Hilbert-Schmidt kernel.
Filbert-Schhidt kernel an integral kernel that is square
Positive semidefinite kernels. A symmetric operator K on a Hilbert space is said to be positive semidefinite and denoted by K ž if (K 2 0 for all f. When a symmetric kernel & is associated with positive semidefinite operator K, i.c. fo So k(t,T))(()f(() dtdr 2 0 for all (10, Ti: RR, we say that the kernel & is (integrally) positive semidefinite and denote it by k > 0. For continuous kernels, positive semidefiniteness of k is equivalent to the following condition: D En=1 Geyk(li, 4) 2 0 for any 11,...,4, La [0, T] and , R. given N.
Proposition We summarize some basic properties of continuous positive semidefinite kernels:
(a) For a E
the kernel k(t, T) = a(t)a(T) is positive semidefinite.
(b) For k1, 12 č O, their product k(t,, 7) = k/2 7) is positive semidefiitt.
(c) For & = 0, its anti-transpose (t, H k(T - T, T - t) is also positive semidefinite.
(d) o ('O, T); Rzo) ) is an increasing function on [0, T) then the symmetric kernel defined k(t, r) ( t 2 and k(t, r) (t) for S is positive semidefinite
(e) For k - 0, we have ktt, t) 2 for all [0.T].
3 Continuous PEP for minimizing objective function value
In this section, drawing inspiration from its discrete-timg counterpart 8 42), we propose novel framework for analyzing the convergence rate of ODE models for first-order methods, called the continuous Aattinuuus-timeeeee performance estimation problem (Continuous PEP). To illustrate this framework, we use the accelerated gradient flow as an example. Detailed steps can be found in Appendix Su al. (36] derived the limiting ODE of Nesterov's 's AGM 27 as follows:
3 x
X V t
(AGM ODE)
with initial conditions X(0)= = To and x()) 0. Suppose we want to establish a convergence guarantee of|A ODE in the form of
f(X(T) f(x) - P -0 x* 112.
Here, we observe that the constant P can be seen as an upper bound of the performance of AGM ODE for the criterion (f() (=)))) x 1|2. To formalize this idea, we introduce the
following optimization problem, which seeks to find the worst-case performance of the given ODE
model:
f(X(T)) - f(x))
max fEJo(K"-RR ((.TTa)))))))))
1100 x=1
(Exact PEP)
subject to
X is solution to ODE with X(0)= zo, X()
x² is a minimizer f,
where Fg (Rd; RR) denotes the set of continuously differentiable μ-strongly convex functions on Idd. This problem is useful to analyze the convergence properties of ODE models because the optimal value val (Exact PEP of Exact PEP directly provides the guarantee (3) with val Exact PEP regardless of any particular choice of f.
Proof sketch: The kernel k(l, r) be expressed weighted integral of positive semidefinite kemels ket, o00) + + ((s)) ds.
3

---

3.1 Relaxation of PEP
Exact PEP is challenging to solve due the presence of an unknown function f as an optimization variable. To address this difficulty, we relax the constraint f E ( with a set of inequalities that are satisfied by / (RR R). Before that, we first note that AGM ODE can be expressed as the following continuous-time dynamical system (see [9]
((t) ((t)=-fm J H(())) dr
(4)
by setting Tt, = = Here, Htt, r) is called the H-kernel. We introduce two functions, :p: [0, 7 + and 7: [] + Rd, defined as follows:
(t)) ||/ x11 1| (o(x(0) - (x')) 7(1)
1.0 x²1 VS((()))
Using the chain rule and the convexity of we can derive the following equality and inequality:
((0)) I H((,T((T
0 = +(1)+
(5)
0 2 ptt) + (7(0))u v S. [H (((s))((())sss ds)
where v = (x* xo)/1/20 x| We can now relax Exact PEP by replacing its constraints with the equality and inequality above, resulting in the following problem:
max
(TT)
P...0
(Relaxed PEP)
subject
5 holds for all (0,T).
Since any feasible solution Exact PEP can be transformed into a feasible solution to Relaxed PEP
we have val RRelxedd PEP) 2 val [Exct PEP Therefore, the convergence guarantee (3) holds with
= val RReaxed PEP) when using the proposed relaxation.
3.2 Lagrangian dual of relaxed PEP
To obtain an upper bound on val Relaxed PEP we use Lagrangian duality. We introduce two Lagrange multipliers Å1 ((O, 2]; R) and X2 C([0, TR; where we imposed certain regularity conditions, such as continuity and differentiability, to ensure that the dual problem is well-defined. We then define the Lagrangian function as
C1,,,, 22) (TT) 1'" x1((1 ((()) (#0)) (110), J ((, H(( a
-f >2(t) po(t) + (1()),++ (." f. ((() dt.
When expressed in terms of the inner products in function spaces, we have C(p, y, u; A1, X2) = (T) (A1, (1, () - (A2, 22
(6)
2 Kr 10. (A2(1),, (1))),7())))) (70077):)))
where is the Silbeet-Scchiit integral operator with the symmetric kernel defined by
ktt, (t) X2(1) [ H(s, ds, t2
The dual function is defined as Dual(A1, A2) ) supo, L(p,, T, A2). By weak duality, we have
val [Relaxed PFP) < Dual(A1,>X >2) ) for any feasible dual solution (A1,22). After performing some computations, obtain the following expression for the dual objective function (see Appendix C):
inf iinfve(0.0)) {v. SA - 0} if (0) 0. \T (1 = >x(t)
Dual(A1, A2)
x
otherwise,

---

where Sxnd is symmetric kernel on [0, T7 given by
Sx =v (A + A2(t) J. ((s,)) - (2(()))((T) 12
(8)
We refer to dg,y as the PEP kernel. In Appendix H.2 continuous-time limit of the discrete-time PEP kernel presented in [8].
show that (8) can be viewed as the
To describe our framework, given Mras E (0, x)), suppose that the PEP kernel Ag. is positive semidefinite with appropriate multiplier functions \1 and Xg. Then, Mteas is feasi- ble solution of the minimization problem in 77. and thus Dual(A1, A2) S Vreas- On the other hand, by weak duality, val [Relaxed PEP) inf Dual(>1, Therefore, we conclude that val (Exact PEP < val (Relaxdd PEP) s Dual(A1, X2) Vreas, which implies that the convergence
guarantee automatically holds with = Mieas-
Using this approach, we can recover the known convergence guarantee for AGM ODE in 36 Proposition 2. AGM ODE achieves the convergence rate with p 2/T².
Proof. By choosing the multiplier functions (t) = /2/122 and (2 2t/T²,, we can compute the PEP kernel (8) as AA,,A2, 7) (v # &r Since the kernel (1, + ŁT nonzero and positive semidefinite, we have A2.. if and only if 2 2/T2. Thus, we obtain Dual(A1, 2/T2.
which establishes the convergence guarantee 3 with p 2/T2.
Remark 1. Furthermore, this convergence guarantee is optimal among all possible guarantees obtained through the weighted integral of (). The optimality of this rate follows fromowssrom the fact that (A1, X2) is the optimal solution to the dual problem minx,,22 Dual(X1; See Appendix details.
H. H.
for
3.3 Applying continuous PEP to various accelerated gradient flows
Note that the proposed method is not dependent on the choice of the H-kernel (t, T). Thus, it can be applied to arbitrary dynamics represented in the form of 4 Furthermore, while we have focused on the non-strongly convex case (μ = 0) so far, the following paragraph demonstrates that our method can handle strongly convex objective functions by using a reparametrization technique
Reparametrization from F,, (IR: IR) to (R R). Consider a fu-strongly convex objective func- tion f. Since the proposed method is tailored for non-strongly convex objective functions, we choose to work with the convex funetion fzx) == fx) - & || _ool2 rather than working directly with Accordingly, we consider the following alternative formulation for the dynamical system (4). which
involves f instead of f
x()- (()--fa ==((,)))(((())))
The following theorem offers a general result that can be used to establish convergence guarantees for dynamical systems of the form (9).
Theorem 1. Let v > 0 and X
Ca (10, R20) such that S x² < 1, (TT) 1, and
(t) 2 for all t E (O,T). Then, any solution to the integroddiffrentiin equation 9 satisfies
(() - f(x*)= < x (f(zo) f(x²)) + 1|z0 - x=
112,000 if the following PEP kernel is positive semidefinite: where f(x) = f(x - #| x12
(F(1,T) (x ()((1)=*(( (1,)))(( [ HT (s.)) 2a (1)(())F(1
12 T,
(10)
where a ((())= 1
So H² drds))
The proof of Theorem is done by finding dual feasible point to the PEP and can be found in
Appendix C Below, we establish convergence rates for various ODE models using Theorem |
In discrete PEP literature, a similar reparamctrization technique was employed
40
'The equivalent representations and (9) are in one-to-one correspondence. See Appendix
C.I for details.

---

(a) Contour plot.
(b) Surface plot.
Figure Visualization of the PEP kernel for AGM-SC ODE
AGM-SC ODE. We consider the following dynamical system modeling Nesterov's AGM for
strongly convex case 26 Equation 2.2.22] (see 448 Equation 7]):
X 2 + V =
(AGM-SC ODE)
This ODE model can be written as ! with H (t, (LT/VT-VV/) (Lt//r-////eeevtt---- (see Appendix
F.1
To use Theorem we choose the multiplier function as X (t) =eva(t- can be computed as (see Appendix [G.]]
The PEP kernel
S (t, veve(r-T)
11 2y4T t t2T.
(11)
2
When v - e - this kernel is written as S (1, = 22- (evir - 1), and is visualized in
Figure 1 It positive semidefinite since the function 7 evir 1 is nonnegative increasing function (see Proposition (d)) follows from Theorem that AGM-SC ODE achieves the following
convergence guarantee:
- f(X(T))-F(=")> Se vvv (f(zo) f(x') 1| =²)
(12)
which is consistent with the well-known ((TV convergence rate of AGM-SC ODE
Unified AGM ODE.
Using unified Bregman Lagrangian framework, 19 obtained the following
ODE that unifies AGM ODE and AGM-SC ODE
V (tanh, +3 coth,)
x+
VS(X)= = 0,
(Unified AGM ODE)
where tanh, and coth, denote the corresponding hyperbolic functions with the argument vTL This ODE model be written
9 with H (1, r) (1 + coth, (log(sech?) -oggsecc))) (see Appendix F.2) We select the multiplier function X (t) = sinh? sinh.. With this choice,
sinh- cosh- sinh, cosh,
the PEP kernel (10) can be expressed follows (see Appendix G.2
S (1, = (1, esch?) lanh, Lanh,
+ Lanh, lanh,, sinh?
12T.
(13)
sinh;
sinh?
We show that this kernel positive semidefinite for v == $ eschă² Proposition (a) shows that the kernel T) + tanh, tanh, is positive semidefinite. Proposition [ (d) shows that the kernel (t, sinh; is positive semidefinite because the function eschi can be expressed product of two positive semidefinite kernels, it is positive semidefinite by Proposition (b). Consequently, Theorem limplies that Unified AGM ODE achieves the following convergence guarantee:
sinh? is nonnegative increasing
function. Since the PEP kernel (13) with
f(X(T) f(x") < 2 csch? ||:0
x² x²1²
(14)
This guarantee aligns with the O convergence rate reported in 19
6 As a rule of thumb, when the expected convergence rate is O(p(T)). we set (1) = p(T)/p(t).
This dynamical system models the unified AGM in [19 and the constant step scheme (26 Equation 2.2.19].

---

TMM ODE. We consider the following novel limiting ODE for the triple momentum method
(TMM) 46 (see Appendix E.I for the derivation and a comparison with the one in (
+ + ( = 0.
(TMM ODE)
This ODE model can be written as D with 1 (t, T) - 2ev/l (ov/u(T-)) +4E2VH(T-1) (see Appendix F.3
By setting the multiplier function X (()) 22u((t- the PEP kernel 10) can be computed as (see Appendix G.3)
(1,
ue 2 evA(LtT-21)
(15)
which is positive semidefinite for v μe μe 2//l", Consequently, Theorem 1 implies that
TMM ODE
achieves the following convergence guarantee:
((x(T))-f f(x²) S "va (f(z)) - j(x)) + 100 x² IP)
(16)
which is new to the literature. In Appendix H.3
show that this convergence rate match aligns with the known convergence guarantee for TMM the discrete-time case.
ITEM ODE. We consider the following new limiting ODE of the information-theoretic exact method (ITEM) 40 (see Appendix E.2 for the derivation ITEM ODE)
X + coth X + 2V = 0,
(ITEM ODE)
where coth, denotes the corresponding hyperbolic function with the argument Vpt. This ODE model can be written as (9) with H² (t, = sinh, cosh, coth, esch, +2 +2 sinh, csch, (1 2 cothh²) (see
Appendix F.4. By choosing the multiplier function as A (t) = sinh² sinh²(V/it) (vTit/ sinh" (inh"( the PEP kernel TO can be computed as (see Appendix (.44
SF (t, r) = 2 csch? v cschÿy sinh, sinh,
(17)
For v = μ cschyy, this kernel is positive semidefinite. It follows from Theorem achieves the following convergence guarantee:
that ITEM ODE
((X - f(x*) S م4 csch [|:0 1=1
(18)
which is novel result. In Appendix H..4 we show that this guarantee matches the known convergence rate for ITEM in the discrete-time case.
4 Continuous PEP for minimizing velocity and gradient norm
In this section, we present a result analogous to Theorem T to address convergence rates on the squared velocity norm | (T2 or the squared gradient norm (VX(()))I For continuous-time ODE models, the analysis of convergence rates on the squared gradient norm IIV (TX())) ||2 was first presented in (37]. However, their argument relies on the use of L L'Hôpital's 's rule, which might give the impression that their approach is based on a clever trick appears somewhat mysterious.
4.1 Translating convergence rates on [x(]) into convergence rates on (X)(
In this subsection, present novel approach for establishing the convergence guarantee of ODE models on the squared gradient norm (x))( The crucial insight lies in expressing VS(X(T)) lo (rr() dr, where 5y denotes the Dirac delta function centered at T. Suppose we have a guarantee of the following form:
1 au cu(T)V((X(())) dr |' -((((z))-((x1)
(19)
where X E Cº C'OO, Rd)) and {at) a family of functions parametrized by t E (0, T). In particular,
we note that a convergence guarantee on (C) of the dynamics 44) can be written as 19 with (T) (tt) r). A well-known argument for constructing the Dirac delta function (sec
7

---

35
Section 3.2]) shows that the weighted integral So on ve(T)V dr converges to (T))
as + T. if the following conditions hold: (t) (1) 2 0, (ii) fo ar(T) dr + as 1 + T, and (Mii for every 7) E (O, T', we have So (T( dr + 0 as f - T' When a satisfies these properties, say that the function at converges to the Dirac delta function ôT. Consequently, taking the limit - 7 in 19) yields the following guarantee on ([
|V & (f - f(x"))
4.2 Convergence analysis via positive semidefinite kernels
In this subsection, we introduce variant of continuous PEP that establishes the convergence rate on (T) through checking the positive semidefniinteess of the PEP kernel. Notably, this methodology can also prove convergence rates on || ( because the convergence rates on [t]( can be translated into those on (T))( as discussed in the previous subsection.
Reparametrization time-varying functions. In Section 3.3, we employed a reparametrization technique to deal with strongly convex objective functions. In this section, we first apply the same technique again, leading to the following expression
x() (0)=-f( H ()
(20)
where f(x) = (xx) -|| - =oll. However, we not proceed directly with this form. Instead,
we introduce an additional reparametrization step. Given a solution X to (20). and function
Gc CO T); Rzo),
define family of functions (ff)) fi(x) (t)
(T (T(())((X())) (T) dr, æ). Then, we can show that 200 can be equivalently written in the following
form (see Appendix D.I
((t) - S (t, ( x(t==
(21)
for some kernel H The following theorem is analogous to Theorem for our current purpose.
Theorem 2. Let v > O, tend E [0, a E C([0, temal, IR), and X E Ca (10,, tema]; l22)) such that
(0) and i (t) 2 0 for all t. Then, any solution to 21 satisfies
11,-0 and ((VVI(((())
dr
s sup -
(22)
ZERd
if the following PEP kernel defined on [0, fend] is positive semidefinite:
(C( -aa))=vl(00 f (1, 2a (t)a
T2
(23)
In particular, the choice (1) = ((eend) HC (fend, t) gives a guarantee on [[C(tend) ) (tend)
1|?
The proof of Theorem 2 can be found in Appendix D We now use this theorem establish
convergence rates of the anti-transposed dynamic of the ODE models studied in Section 3.3
OGM-G ODE. By taking the limit of the stepsize in OGM-G 18] Suh el al. obtained the following ODE model for the non-strongly convex case (μx 0) 10
+
+ ( = 0.
(OGM-G ODE)
This ODE model is the anti-transposed dynamics of AGM ODE as it can be expressed as (20) with
HG (1, = (T (T-1)3/(T -)3 (see Appendix F.5 To use Theorem we choose GG = (T
Thii expression is identical in form to 9 but we use the notation H to avoid any notational overlap.
We refer to (20) as the anti-transposed dynamics of (). HG (t, = H² (T - - -,, - t) for all t, r.
We modified the coefficient of V (t)(t)) from 2
8

---

2 T We set the terminal time fend before T and apply a limiting argument to prove the convergence
rate on (T))]I By setting a (t) Ctenndl H H (tend, t) with ((tend) 1/(T (ndd we
can compute the PEP kernel (23 as (see Appendix
G.5
(T (T)
(1, =
(24)
72
T2
Since this kernel the anti-transpose of the PEP kernel for AGM ODE in the proof of Proposition 2
we have $ (t, 7) = 0 when y = 2/ by Proposition (c). By Theorem 2
we obtain the following
inequality:
lond
(T (T- lend) )2
X (lend)
2 sup (f(ro) f())). zER
(T- 3)3 (((((T)) dr =
(25)
T tend
T
Observing that the function r + (T (T-fe (e))
(T) converges to 1 as lend + T. we have
(7-
Jo Bland (T-toud) (((((T)) + /V as tend + T 12 Substituting this result into (5 we
(7-7)
deduce the following convergence guarantee:
8
sup (f(x)) f(z)), ZEad
(26)
T
which recovers the known convergence rate of OGG--G ODE
37
AGM-SC ODE. We now analyze the convergence of AGM-SC ODE in terms of the squared
velocity norm, using Theorem [ This ODE model is the anti transposed dynamics of itself, as it can
be expressed as 200 with Tt, = VIT ((l))vvR(--) We choose (t evit and
fend = T. By setting a (t) ((T)HC(TTTT
with C(T) vp/2, 2, the PEP kernel
23 is expressed
as (see Appendix G.6)
sC (t, r) ve Vpt
VeL
2VP
2
(27)
Since this kernel is the anti-transpose of [I it is positive semidefinite when v = - by Proposition (c). Therefore, we conclude that AGM-SC ODE achivees the following convergence guarantee:
VP (T) 2
TTT sup wERd
{f(z)) f(x))
(28)
which is new the literature. A numerical experiment for this guarantee can be found in Appendix
L.I
Unified AGM-G ODE.
In 19]. the following unified AGM-G ODE is proposed:
X + //l : 2
X + V = 0,
(Unified AGM-G ODE)
where tanhy-e and cothy denote the corresponding hyperbolic functions with the argument 2 (T t). This ODE model is the anti-transposed dynamics of Unified AGM ODE as it can be expressed as (2)) with (t
J
(t, 7) (1 + - (log(sech) (see Appendix F.6). To identify its convergence rate in terms of the squared gradient norm, we choose X C(( = c //sch// By setting (t) = ((Iena) (lend, 1) (Ienn,
sibly- cosby-r log(sech? sinhr coshr
with C(fend) =
ve
sechT- -teu cschT-tumr the PEP kernel 2
23 expressed as (see Appendix G.7
(C = ( ( csch?) tanhy- tanhy sinh?
tamby tanby sinh? sinh?
12 (29)
Since this kernel is the anti anti-transpose of (13), it is positive semidefinite when v = esch by Proposition (c). Therefore, Unified AGM-G achievee the following convergence guarantee:
11 As a rule of thumb, when expected convergence rate is Opp(T)). we set (1) p(T''t)/'(1)) In our argument using the Dirac delta function, we rely on the fact that the solution X OGM-G ODE be continuously extended to = T. which shown in [37 Appendix D.3J.
can

---

(C(teaa)X(aan 1|
_ cschy sup
(fxz)
(30)
2
ZER"
In Appendix G.7 we show that ((tend) ((tend) + - (Vf(((TT) as tend - T. As a result, we have the following convergence guarantee on [
( & 2μ eschi sup
- [wm)].
(31)
rERd
which recovers the known rate of Unified AGM-G ODE in 19
The convergence analyses of the anti- anti-transposed dynamics of TMM ODE and ITEM ODE are deferred to Appendix I.2 The convergence guarantees in this section can also be established using a Lyapunov function argument, detailed in Appendix L.3
5
Correspondence between minimizing function values and gradient norms
In Section 4.2 we verified the positive semidefiniteness of the PEP kernel (33 by showing its anti-transpose relationship with the PEP kernel (TO), that is, (t, T) (T T.T -). The following proposition indicates that this relationship Proposition 3. Suppose H (1,T) HG - T 1) (L) 1T - -), and of (1) = (T -1) for all t and r. Then, we have S (1, SC T, t) for all l. and T.
coincidental.
The following proposition offers general result for translating convergence rates on ffeedd a (X))), dr| into those on (
Proposition 4. Under the assumptions Proposition if ( x0 as - T, then we have faad (T)V dr - (X))( as lend
T.
Both Propositions 3 and 4 have straightforward proofs through calculations, which can be found in Appendix[]] []] Now, the next result naturally follows.
Theorem Under the assumptions Propositions
3 Band4
4
the following statements are equivalent:
(a) Theorem
proves the convergence guarantee f(X(T)) f(x*) S <v11= - =1
(b) Theorem proves the convergence guarantee [[)(( sfpp f(x)}.
Proof. (a) holds
SF
(b) holds.
Prop
Thm.
Prop
Conclusion
In this paper, we have developed a novel and simple framework for analyzing the convergence rates of accelerated gradient flows via positive semidefinite kernels. Our framework enhances our understanding of continuous-ting time models for accelerated first-order methods and bridges the gap between the continuous-time and discrete-time PEP frameworks. For instance, the continuous PEP in Section 3 can be viewed as a continuous-time limit of the discrete PEP presented in [ (see Appendix H.2). This connection unlocks new opportunities for studying PEP. Future research directions may involve extending our framework using techniques employed in the ODE models literature, such as generalizing to non-Euclidean settings 20 or analyzing high-resolution ODE models 33
Codes. The codes used to generate the figures in this paper are available at https://githui com/ juugjuiniiin///ntiinouuut -PEP
Acknowledgments and Disclosure of Funding
This work was supported in part by the National Research Foundation of Korea funded by wWw.2/220R111110077660 and the Information and Communications Technology Planning and Evaluation (IITP) grant funded by MSIT(2022-0-00124 2022-0-00480).
10

---

References
[1] Foivos Alimisis, Antonio Orvieto, Gary Becigneul, and Aurelien Lucchi. A continuous-time perspective for modeling acceleration in Riemannian optimization. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, pages 1297-1307, 2020.
[2] Hedy Attouch, Zaki Chbani, Juan Peypouquet, and Patrick Redont. Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity. Mathematical Programming. 168(1):123-175, 2018.
[3] Hedy Attouch, Zaki Chbani, and Hassan Riahi. Rate of convergence the Nesterov accelerated gradient method in the subcritical case S 3. ESAIM: Control, Optimisation and Calculus of Variations, 25:2, 2019.
[4] Michael Betancourt, Michael Jordan, and Ashia C Wilson. On symplectic optimization. arXiv preprint arXiv: 1802.0663, 2018.
[5] Etienne De Klerk, François Glineur, and Adrien B Taylor. On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions. Optimization Letters, 115-1991199 2017.
[6] Jelena Diakonikolas and Michael I Jordan. Generalized momentum-basee based methods: A Hamilto- nian perspective. SIAM Journal on Optimization, (1(1):915-)) (1):915-944, 2021.
[7] Yoel Drori and Adrien B Taylor. Efficient first-order methods for convex minimization: A constructive approach. Mathematical Programming, (84(1-2):183-220, 2020.
[8] Yoel Drori and Mare Teboulle. Performance of first-order methods for smooth convex mini- mization: novel approach. Mathematical Programming. 145(1):451-482, 2014.
[9] Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion, Pierre Gaillard, Hadrien Hendrikx, Laurent Massoulié, and Adrien Taylor. Continuized accelerations of deterministic and stochastic gradient descents, and of gossip algorithms. In Advances in Neural Information Processing Systems, pages 18054-28066
[10] Mahyar Fazlyab, Alejandro Ribeiro, Manfred Morari, and Victor M Preciado. Analysis of optimization algorithms via integral quadratic constraints: Nonstrongly convex problems. SIAM Journal on Optimization, 28(3):2654-2689) 2018.
[11] Guoyong Gu and Junfeng Yang. On the optimal ergodic sublinear convergence rate of the relaxed proximal point algorithm for variational inequalities. arXiv preprint arXiv: 1905.06030, 2019.
[12] Guoyong Gu and Junfeng Yang. Optimal nonergodic sublincar convergence rate proximal point algorithm for maximal monotone inclusion problems. arXiv preprint arXiv:1904.05495 2019.
[13] Shuvomoy Das Gupta, Bart PG Van Parys, and Ernest K Ryu. Branch-and-Ae houud--odddd performance estimation programming: unified methodology for constructing optimal optimization methods. arXiv preprint arXiv:2203.07300 2022.
[14] Bin Hu and Laurent Lessard. Dissipativity theory for Nesterov's accelerated method. In International Conference on Machine Learning, pages 1549-1557. PMLR, 2017.
[15] Bin Hu, Peter Seiler, and Anders Rantzer. A unified analysis of stochastic optimization methods using jump system theory and quadratic constraints. In Conference on Learning Theory, pages 1157-1189. PMLR, 2017.
[16] Donghwan Kim. Accelerated proximal point method for maximally monotone operators. Mathematical Programming, 190(1-2):57-33 2021.
[17] Donghwan Kim and Jeffrey A Fessler. Optimized first-order methods for smooth convex minimization. Mathematical programminn, 159(1)81-107, 2016.

---

[18] Donghwan Kim and Jeffrey A Fessler. Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions. Journal of optimization theory and applications, 188(1):192-219 2021.
[19] Jungbin Kim and Insoon Yang. Unifying Nesterov's accelerated gradient methods for convex and strongly convex objective functions. In International Conference on Machine Learning. pages 16897-16954. PMLR, 2023.
[20] Walid Krichene, Alexandre Bayen, and Peter L Bartlett. Accelerated mirror descent in contin- uous and discrete time. In Advances in Neural Information Processing Systems, volume 28, 2015.
[21] 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.
[22] Laurent Lessard and Peter Seiler. Direct synthesis of iterative algorithms with bounds on achievable worst-case convergence rate. In 2020 American Control Conference (ACC), pages 119-125. IEEE, 2020.
[23] Aleksandr Mikhailovich Lyapunov. The general problem of the stability of motion. International journal of control, 55(3):531-535 1992.
[24] Alexandre Megretski and Anders Rantzer. System analysis via integral quadratic constraints. IEEE Iransactions on automatic control, 42(6)) 1997.
[25] Céline Moucer, Adrien Taylor, and Francis Bach. A systematic approach to Lyapunov analyses of continuous- titerouuuu-eueeeeee models in convex optimization. SIAM Journal on Optimization, 33(3):1558- 1586, 2023.
[26] Yurii Nesterov. Lectures on Convex Optimization, volume 137. Springer, 2018.
[27] Yurii E Nesterov. A method for solving the convex programming problem with convergence rate o11/k²). In Dokl. akad. nauk Sssr, volume 269, pages 543-547, 1983.
[28] Frigyes Riesz and Béla Sz Nagy. Functional analysis. Courier Corporation, 2012.
[29] W. Rudin. Real and Complex Analysis. McGraw-Hie Hill,, 1987.
[30] W. Rudin, Functional Analysis. McGraw-Hill, 1991.
[31] Jesús María Sanz Serna and Konstantinos C Zygalakis. The connections between Lyapunov functions for some optimization algorithms and differential equations. SIAM Journal on Numerical Analysis, 59(3):1542-1565 2021.
[32] Damien Scieur, Vincent Roulet, Francis Bach, and Alexandre d' Aspremont. Integration methods and optimization algorithms. Advances in Neural Information Processing Systems, 30, 2017.
[33] Bin Shi, Simon S Du, Michael Jordan, and Weijie J Su. Understanding the acceleration phenomenon via high-resolution differential equations. Mathematical Programming, pages 1-70, 2021.
[34] Bin Shi, Simon S Du, Weijie Su, and Michael Jordan. Acceleration via symplectic discretiza- tion of high-resolution differential equations. In Advances in Neural Information Processing Systems, volume 32, 2019.
[35] Elias M Stein and Rami Shakarchi. Real Analysis: Measure Theory, Integration, and Hilbert Spaces. Princeton University Press, 2009.
[36] Weijie Su, Stephen Boyd, and Emmanuel J Candes. A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 17:1-43, 2016.
12

---

[37] Jaewook J Suh, Gyumin Roh, and Ernest K Ryu. Continuous timeeoeuuu--eeeeeee analysis of accelerated gradi- ent methods via conservation laws in dilated coordinate systems. In International Conference on Machine Learning, pages 20640-20667. PMLR, 2022.
[38] Boya Sun, Jemin George, and Solmaz Kia. High-resolution modeling of the fastest first-order optimization method for strongly convex functions. In 2020 59th IEEE Conference on Decision and Control (CDC), pages
IEEE, 2020.
[39] Adrien Taylor and Francis Bach. Stochastic first-order methods: Non-asymptotic and computer- aided analyses via potential functions. In Alina Beygelzimer and Daniel Hsu, editors, Pro- ceedings of the Thirty-Second Conference Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 2934-2992. PMLR, 25-28 Jun 2019.
[40] Adrien Taylor and Yoel Drori. An optimal gradient method for smooth strongly convex minimization. Mathematical Programming, pages 1 1-38, 2022.
[41] Adrien Taylor, Bryan Van Scoy, and Laurent Lessard. Lyapunov functions for first-order methods: Tight automated convergence guarantees. In International Conference Machine Learning, pages 4897-4906. PMLR, 2018.
[42] Adrien B. Taylor, Julien M. Hendrickx, and François Glineur. Smooth strongly convex interpo- lation and exact worst-case performance of first-order methods. Mathematical Programming, 161(1-2):307-444 May 2016.
[43] Adrien Taylor, Julien M Hendrickx, and François Glineur. Exact worst-case performance of first-order methods for composite convex optimization. SIAM Journal on Optimization. 27(3):1283-1313, 2017.
[44] Adrien B Taylor, Julien M Hendrickx, and François Glineur. Exact worst-case convergence rates of the proximal gradient method for composite convex minimization. Journal of Optimization Theory and Applications, 178:455 2018.
[45] Manu Upadhyaya, Sebastian Banert, Adrien B Taylor, and Pontus Giselsson. Automated tight Lyapunov analysis for first-order methods. arXiv preprint 23t.:22302.067.33. 2023.
[46] 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(1):49-54, 2017.
[47] Andre Wibisono, Ashia C Wilson, and Michael Jordan. A variational perspective on accelerated methods in optimization. proceedings of the National Academy of Sciences, 133(4))E7331- E7358, 2016.
[48] Ashia C. Wilson, Ben Recht, and Michael I. Jordan. A Lyapunov analysis of accelerated methods in optimization. Journal of Machine Learning Research, 22(113):1-34, 2021.
[49] Jingzhao Zhang, Aryan Mokhtari, Suvrit Sra, and Ali Jadbabaie. Direct Runge- Kutta discretiza- tion achieves acceleration. In Advances in neural information processing systems, volume 31, 2018.
13


Reviews:
[{"review_id": "DsBlUZYNZ3", "reviewer": "Reviewer_pACc", "summary": "Continuous counterpart of the work by Drori and Teboulle [2] was presented. Specifically, through the dual objective of the relaxed PEP in continuous time, the convergence rates of various ODEs were obtained. The analysis on the Lagrangian dual will lead to a dual solution based on a symmetric kernel of the Hilbert-Schmidt integral operator (Theorem 1).  Some of the follow up results were new to the literature e.g., low-resolution ODE (as opposed to high-resolution ODEs proposed by Shi et al. [19]) for the TM, ITEM methods & velocity/gradient norm convergence rates (Theorem 2).", "questions": "1- Is the statement in 33[However ...]36 true? There has been a line of work which used positive-semidefiniteness to define tight Lyapunov functions (see [1]). This work however deals with a more general case which entails various ODEs through the choice of the kernel.\n\n \n\n2- Following Q1, is it possible to use your framework to define tight Lyapunov functions? This relates to finding the analytical Lyapunov functions simulated in e.g. [2].\n\n \n\n3- Is it possible to extend this work to the high-resolution ODE framework proposed by Shi to bypass the Lyapunov based proofs in their analysis?\n\n \n\n4- Is there any connection between the low-resolution ODE for TMM proposed in this work and the high-resolution ODE proposed in [3]?\n\n \n\n5- In authors' mind, what discretizations can recover the TMM and ITEM from the proposed TMM  and ITEM ODEs?\n\n\nReferences\n[1] Sanz-Serna, Jesús María and Konstantinos C. Zygalakis. “The connections between Lyapunov functions for some optimization algorithms and differential equations.” SIAM J. Numer. Anal. 59 (2020): 1542-1565.\n\n[2] Upadhyaya, M., Banert, S., Taylor, A.B., & Giselsson, P. (2023). Automated tight Lyapunov analysis for first-order methods.\n\n[3] B. Sun, J. George and S. Kia, \"High-Resolution Modeling of the Fastest First-Order Optimization Method for Strongly Convex Functions,\" 2020 59th IEEE Conference on Decision and Control (CDC), Jeju, Korea (South), 2020, pp. 4237-4242, doi: 10.1109/CDC42340.2020.9304444.", "limitations": "The limitations are stated in the text.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1- The work has a solid mathematical base. The proofs are well written and mostly easy to follow. \n\n2- The rate for TM ODE and ITEM ODE matching their discretized algorithms.\n\n3- Investigating the connection between the continuous-time PEP and its discrete counterpart in Appendix G.2", "weaknesses": "1- The future directions are not clearly specified or very vague. This will impact the contribution of the work to the Neurips community. In the \"Questions\", I have asked some questions (numbers 2,3,4,5) which can be as future directions or even increase the contribution of this work beyond the current status.\n\n2- The presentation can improve e.g. \n\n-In (Relaxed PEP): move subject to under max for better readability. \n\n-In 145: Sinse is a typo.\n\n-References 22 23 are the same.\n\n-Appendix: 455 missed parenthesis for 70.\n\n\n3- Limited literature review. More comprehensive literature review could be placed in the Appnedix to save space.\n\n4- Inconsistency in some parts of the text; e.g., in 113 I expected to see the inequalities mentioned in 112, but I was noted with another representation of AGM ODE from [9]. Also, sudden shifts from convex cases to strongly convex ones can cause confusion.\n\n5- Some parts could be moved to the appendix (e.g. recovering the famous known rates for ODEs) and instead report their results in a table. Then, the authors could use the additional space to draw conclusions, compare (like graphs and visual simulations for instant comparison), or even exploring other aspects of the proposed framework or ODEs (by e.g. answering some of the questions in the \"Questions\" section below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q2.** In Summary: Our continuous PEP is intrinsically associated with certain Lyapunov functions. However, if you are asking about the conventional Lyapunov function argument, where the Lyapunov function takes specific forms like\n$\\mathcal{E}(t)=a(t)(f(X(t))-f(x^*)+b(t)\\Vert Z(t)-x^{*}\\Vert^{2},$\nthen the answer is no.\n\nLet's see how our framework can be interpreted using a Lyapunov function. The continuous PEP presented in Sections 3.1 and 3.2 is related to the following Lyapunov function:\n\n$\\mathcal{E}(t):=\\nu\\Vert x_0-x^*\\Vert^2+\\int_{0}^{t}\\lambda_{1}(s)\\left(\\dot{\\varphi}(s)+\\left\\langle \\gamma(s),\\int_{0}^{s}H(s,\\tau)\\gamma(\\tau)\\,d\\tau\\right\\rangle \\right)ds\\Vert x_0-x^*\\Vert^{2}$\n\n$\\qquad\\quad +\\int_{0}^{t}\\lambda_{2}(s)\\left(\\varphi(s)+\\left\\langle \\gamma(s),v+\\int_{0}^{s}\\int_{\\tau}^{s}H(\\sigma,\\tau)\\,d\\sigma\\gamma(\\tau)\\,d\\tau\\right\\rangle \\right)dt\\Vert x_{0}-x^{*}\\Vert^{2},$\n\nwhich is decreasing by its construction. When the multiplier functions form a feasible solution to (7), i.e., $\\lambda_{1}(0)=0$, $\\lambda_1(T)=1$, and $\\dot{\\lambda}\\_1(t)=\\lambda_{2}(t)$, we have $\\mathcal{E}(T)=f(X(T))-f(x^{*})+Q(T)$, where\n\n$\\mathcal{Q}(T)=\\left(\\frac{1}{2}\\langle K^{d}\\gamma,\\gamma\\rangle+\\langle\\lambda_{2}(t)v,\\gamma(t)\\rangle+\\nu\\right)\\|x_{0}-x^{*}\\|^{2}.$\n\nIf the PEP kernel (8) is positive semidefinite, we can show $Q(T)\\geq0$, following the argument in Appendix Lines 73–78. As a result, we obtain\n\n$f(X(T))-f(x^*)=\\mathcal{E}(T)-Q(T)\\leq\\mathcal{E}(T)\\leq\\mathcal{E}(0)=\\nu\\Vert x_0-x^*\\Vert^{2}.$\n\nIn the conventional Lyapunov function argument, we have an expression for $Q(T)$ that is automatically nonnegative (for example, as being a sum of squared norms). In contrast, the Lyapunov argument corresponding to PEP requires showing $Q(T)\\geq0$ by using the positive semidefiniteness of the PEP kernel.\n\n**Q1.** As noted by the reviewer, there exists a line of work for systematically finding (conventional) Lyapunov functions. While we have cited some of these works in the related work section, we agree that mentioning this research direction around line 33 is appropriate. We will incorporate this in the final version of our paper.\n\nNevertheless, the statement in lines 33–36 remains valid. Our framework circumvents the need for designing Lyapunov functions, resulting in a distinctive and more widely applicable way to establish convergence guarantees. In our framework, we can address all possible convergence rates obtained through a weighted integral of (5), with each corresponding to a dual feasible solution to (7). This capability enables us to show the optimality of convergence rates, as exemplified in Remark 1. Such a claim cannot be made straightforwardly in works focused on Lyapunov functions.\n\n**Q5.** TMM and ITEM can be expressed as the following fixed-step first-order method:\n\n$x_{i+1}=x_{i}-\\frac{1}{L}\\sum_{j=0}^{i}h_{ij}\\nabla f(x_{j}).$\n\nThe continuous-time counterpart of this form is the following dynamical system (4) (see [9, Section 2.4.2]):\n\n$\\dot{X}(t)=-\\int_{0}^{t}H(t,\\tau)\\nabla f(X(\\tau))\\,d\\tau,$\n\nwhere $H(i\\sqrt{s},j\\sqrt{s})\\approx h_{ij}$. In light of this, the discretization process can be understood as discretizing a kernel $H(t,\\tau)$ into a matrix $[h_{ij}]$.\n\n**Q3.** It seems that such an extension might not be straightforward. The low-resolution ODEs take on the form $\\ddot{X}(t)+b(t)\\dot{X}(t)+c(t)\\nabla f(X(t))=0$, which can be rewritten as (4) by Proposition 4 in the appendix. However, the high-resolution ODEs for Nesterov's AGM involve a gradient correction term $\\nabla^{2}f(X)\\dot{X}$, which cannot be derived from (4). To extend our continuous PEP framework to the high-resolution ODE framework, one should first find a reasonable generalization of the dynamics (4) that can handle the term $\\nabla^{2}f(X)\\dot{X}$, while enabling the convergence analysis via positive semidefinite kernels. This task is not trivial. Therefore, we defer it to future work.\n\n**Q4.** The high-resolution TMM ODE in [3] does not align with the low-resolution TMM ODE in our paper. This is due to the different choices of time step size. While we adopted a time stepsize of $1/\\sqrt{L}$, [3] employed a time stepsize of $\\sqrt{\\alpha}$, where $\\alpha=\\frac{2-1/\\sqrt{L/\\mu}}{L}$ (the value of $\\alpha$ depends on the specific algorithm). Although both choices make sense, our choice of stepsize $1/\\sqrt{L}$ is more commonly employed in the literature and can be applied to any fixed-step first-order method $x_{i+1}=x_{i}-\\frac{1}{L}\\sum_{j=0}^{i}h_{ij}\\nabla f(x_{j})$.\n\n**W5.** Thank you for providing a valuable suggestion. In the final version of our paper, we plan to include figures that visually illustrate PEP kernels (see Figures 1 and 2 in the attached pdf), along with detailed explanations. Additionally, we will enhance the conclusion section to offer a more comprehensive discussion of our framework and its potential applications in future research.\n\n**W1.** We will incorporate the reviewer's suggestions, as well as other possible future directions, e.g., obtaining optimal ODE model with the use of PEP.\n\n**W2.** Thank you for your suggestions; we will address these issues.\n\n**W3.** In our initial paper submission, we focused on including key papers related to our work, considering space limitations. Following your suggestion, we plan to utilize the appendix to provide a more comprehensive literature review. For instance, our literature review will cover papers related to PEP for finding tight Lyapunov functions and the generalization of PEP beyond the convex optimization setup.\n\n**W4.** Thank you for your suggestions. To improve readability, around line 113, we will first express equation (5) in a more familiar form:\n\n$0=\\frac{d}{dt}( f(X(t))-f(x^*)) -\\left\\langle \\nabla f(X(t)),\\dot{X}(t)\\right\\rangle $\n\n$0\\geq f(X(t))-f(x^*)-\\left\\langle \\nabla f(X(t)),x^*-X(t)\\right\\rangle .$\n\nAlso, before presenting Theorem 1, we will clearly mention that we consider the strongly convex case."}, {"review_id": "m5i2ekes2H", "reviewer": "Reviewer_C3yE", "summary": "This paper provides a new technique (that is fundamentally different from the Lyapunov approach) for systemically analyzing the convergence rates of ODE models for first-order optimization methods, which reduces to verifying the positive semidefiniteness of specific Hilbert-Schmidt integral operators. This is a continuous time version of the Drori and Teboulle's (discrete) performance estimation problem (PEP) approach, which has recently become a fundamental tool in systemically analyzing the convergence rates of first-order methods. As a verification, the authors utilized the proposed tool for analyzing various ODE models of accelerated first-order methods such as (unified) AGM, TMM, ITEM, AGM-G and OGM-G, which either recovered the existing convergence rates or revealed new rates for various ODE models.", "questions": "- Line 132: How about letting the readers know that the derivation can be found in Appendix B?\n- Line 180: Is this rate consistent with the rate in [9]?\n- Appendix Line 75: $K^1$? $K^d$?", "limitations": " ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This provides a new systematic analysis of convergence rates of the ODE models of first-order methods, which will be potentially useful for analyzing new ODE models. The authors have successfully verified the effectiveness of the tool for various ODE models.\n\n- This continuous PEP resembles the discrete PEP, but its construction via the functional analysis is certainly not trivial and is very interesting.\n\n- This provides new insights to the PEP analysis.", "weaknesses": "- One of the important features of the discrete PEP is that one can numerically find the values of Lagrange multipliers by numerically optimizing them, which can be used to reveal an analytical form of Lagrange multipliers. However, this paper's continuous PEP requires one to explicitly have the appropriate Lagrange multipliers, which can be laborious especially when dealing with new ODE models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and thoughtful comments. \n\n> One of the important features of the discrete PEP is that one can numerically find the values of Lagrange multipliers by numerically optimizing them, which can be used to reveal an analytical form of Lagrange multipliers. However, this paper's continuous PEP requires one to explicitly have the appropriate Lagrange multipliers, which can be laborious especially when dealing with new ODE models.\n\nThis concern does not significantly impact our contributions at this point. Our work primarily focuses on establishing a theoretical foundation, rather than dealing with implementation. \n\nAlthough it is not the main focus of our paper, the implementation of continuous PEP is a possible future direction. It would be necessitate to implement an optimization problem in function spaces, which might involve approximating continuous-time functions using a finite set of basis functions, with an appropriate care of numerical approximation errors.\n\nOne can use the continuous PEP as a guiding framework for the discrete PEP. In this scenario, numerically optimizing Lagrange multiplier can be done in discrete PEP, and then taking the limit of stepsize to guess an explicit form of the working multiplier function for the continuous PEP.\n\n> Line 132: How about letting the readers know that the derivation can be found in Appendix B?\n\nThank you for the suggestion. We will incorporate this into the final version of our paper.\n\n> Line 180: Is this rate consistent with the rate in [9]?\n\nIn [9, Corollary 8], a convergence rate of $f(X(T))-f(x^*)\\leq O(\\mathrm{csch}^{2}(\\frac{\\sqrt{\\mu}}{2}T))$ is reported (note that the notation $\\mathrm{cschc}$ in [9] is defined as $\\mathrm{cschc}(t):=t\\mathrm{csch}(t))$. While our convergence guarantee in Line 180 is not exactly the same as the one in [9] because our one is for $\\tilde{f}(X(T))-\\tilde{f}(x^*)$, both rates are consistence in the sense that both exhibits the rate $O(\\mathrm{csch}^{2}(\\frac{\\sqrt{\\mu}}{2}T))$ . We will make this point clear in the final version of our paper.\n\n> Appendix Line 75: $K^{1}$? $K^{d}$?\n\nAs $K^{d}$ is already defined in Appendix Line 63, $K^{1}$ is right here. However, there is a typo in Line 75: $L^{2}([0,T];\\mathbb{R}^{d})$ should be corrected to $L^{2}([0,T];\\mathbb{R}^{1})$. Thank you for the catch."}, {"review_id": "YkCRk5SY5l", "reviewer": "Reviewer_RgYv", "summary": "This paper presents a framework for analyzing convergence rates of a class of ODE models via the continuous-time performance estimation problem (PEP). The task of solving the PEP problem is relaxed into verifying the positive semidefiniteness of specific integral operators. The convergence rates of several accelarated gradient flow models were estabilished using the proposed method.", "questions": "There are some questions for technical unclarity.\n\n- Does the paper consider only the strongly convex $f(x)$? If it is, then the minimizer $x^*$ is unique, I suggest the refer $x^*$ as 'the minimizer' rather than 'a minimizer' throughout the paper; if it is not, for convex $f(x)$, how to guarentee that the minimizer $x^*$ exists? For example, $f(x) = e^{-x}$. How to interpret the result of Theorem 1 in this case without defining $x^*$? \n\n- For Exact PEP formulation in line 105, why the initial condition is set as $\\dot X(0) =0$? If $x_0 = x^*$, then there is zero division issue, while this was not a problem in formulation (3). I suggest the authors adapt this case into the Exact PEP formulation. \n\n- The computation stated in line 132 is not obvious. I suggest the authors include the outline in the paper.\n\n- Suggest to outline the proofs of Theorem 1 and Theorem 2 in the paper.\n\n- Can the convergence guarentee in line 155 imply the convergence guarantee of the ODE model? In what sense? For instance, as a extreme case, when $f(x) = \\frac{\\mu}{2}\\|x - x^*\\|^2$, $\\tilde f(x) - \\tilde f(x^*)$ is always zero, then Line 155 becomes trivial inequality.\n\n- Is it possible that the supremum in the inequalities (15) is infinity and the inequality is trivial? For example, $\\mu =  0$ and $f(x)$ is not bounded below.\n\n- What is $x^T$ in equation (20) and (21)?\n\n- Typos: line 45, 'enhances'; page 5, footnote 3 line 2, 'space'.\n\n- Please check the format of the reference list, particularly the letter case (in [25], [27], [30], etc).", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The novelty of the paper lies in the approach of defining and solving the continuous-time PEP problem to analyze ODE models. Under change of variables and Lagrangian duality, it is sufficient to verify the positive definiteness of specific integral operators. Using this method, the authors recover the known convergence guarantee and reveal unknown convergence rate for accelarated gradient flow models. The paper is clearly written and well-organized.", "weaknesses": "The intuition to consider the PEP kernel is not clear. The choices of multiplier function $\\Lambda$ and $\\nu$ are constructive and tricky for ODE models shown in section 3.3 (after Theorem 1) and section 4.2 (after Theorem 2). If given an ODE model as (4), it seems hard to distinguish if it can fulfill the assumptions in Theorem 1 and Theorem 2. \n\nLyapunov analysis for the discrete algorithms is much harder than the continuous dynamic system. The proposed approach only works for the continuous problems and didn't help the discrete case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments. \n\n> The intuition to consider the PEP kernel ...\n\nWe want to clarify that selecting the multiplier functions is not such a challenging task. Although not explicitly mentioned in the paper, there is a rule of thumb for choosing $\\Lambda$ (or $\\lambda$). When the expected convergence rate is $O(1/a(T))$, we found that setting $\\Lambda(t)=a(t)/a(T)$ in Theorem 1 (or $\\lambda(t)=a(T)/a(T-t)$ in Theorem 2) leads to the desired results. For instance, in line 165, because the known convergence rate of AGM-SC ODE is $O(1/e^{\\sqrt{\\mu}T})$, we set $\\Lambda(t)=e^{\\sqrt{\\mu}t}/e^{\\sqrt{\\mu}T}=e^{\\sqrt{\\mu}(t-T)}$. Once the appropriate $\\Lambda$ (or $\\lambda$) is determined, it is not difficult to select the parameter $\\nu\\in\\mathbb{R}$ that makes the PEP kernel positive semidefinite. In the final version of our work, we will include a formal explanation of this rule.\n\n> If given an ODE model as (4), ...\n\nIn our analysis, checking whether the given ODE model satisfies the assumptions in Theorem 1 and Theorem 2 is indeed straightforward. Once the multiplier function $\\Lambda$ (or $\\lambda$) is chosen, the verification process involves only computing the PEP kernel and checking if it is positive semidefinite.\n\nRegarding the soundness of assumptions, Theorem 2 in the initial submission of our paper relied on a nontrivial assumption (16). Fortunately, we have successfully relaxed this assumption, and the revised version will be included in the final version of our paper. In the general response, we provide a detailed explanation of the modification we made.\n\n> Lyapunov analysis for the discrete algorithms ...\n\nWhile it is true that discrete-time analysis can be more challenging than continuous-time analysis, we disagree that continuous-time analysis does not help discrete-time analysis. In fact, our continuous-time PEP framework can provide guidance for analyzing the discrete PEP. In the discrete PEP, finding an appropriate multiplier vector $\\lambda_{i}$ can be quite challenging. However, this task becomes more approachable in continuous-time analysis, where we need to find a multiplier function $\\lambda(t) $ for the corresponding continuous PEP. Once we have a multiplier function $\\lambda(t)$ that works for the continuous PEP, we can discretize this $\\lambda(t)$ to obtain candidates for multiplier vectors $\\lambda_{i}$ that work for the discrete PEP (see Appendix G.2.2 for a specific example and related discussion). Furthermore, discretizing a multiplier function $\\lambda(t)$ is typically simpler than discretizing a Lyapunov function. As a result, transitioning from continuous-time analysis into discrete-time analysis is more straightforward in the PEP framework than in traditional Lyapunov analysis.\n\n> Does the paper consider only the strongly convex ...\n\nIn our paper, we assume the existence of a minimizer $x^*$ (we will make this clearer in the final version). This assumption is standard in the literature on the analysis of accelerated first-order methods and can be found in Nesterov's seminal paper on AGM [15] as well as recent works [22,19] published in NeurIPS.\n\n> For Exact PEP formulation in line 105, ...\n\nThe initial condition $\\dot{X}(0)=0$ is a part of the continuous-time model (AGM ODE), and its derivation can be found in Su et al.'s paper [23]. Note that without having an initial condition for both $X(0)$ and $\\dot{X}(0)$, the solution to AGM ODE is not uniquely determined. In the final version, we will mention the initial condition immediately after introducing AGM ODE for the first time.\n\n> If $x_0=x^*$, then there is zero division issue, ...\n\nWhile it is desirable to avoid such an issue, we don't need to worry about this. The case $x_0=x^*$ leads to $X(t)=x^*$ for all $t$, making the situation so trivial that we can safely exclude this case from our analysis. Also, note that dividing by $\\|x_0-x^*\\|$ can be commonly found in the PEP literature [2,26].\n\n> Can the convergence guarentee in line 155 ...\n\nThe convergence guarantee in line 155 is for $\\tilde{f}(X(T))-\\tilde{f}(x^*)=f(X(T))-f(x^*)-\\frac{\\mu}{2}\\|X(T)-x^*\\|^{2}$, rather than for $f(X(T))-f(x^*)$. While it is possible to formulate a continuous PEP with the performance measure as $f(X(T))-f(x^*)$ (as done in the discrete-time case in [26, Appendix D]), we decided to use $\\tilde{f}(X(T))-\\tilde{f}(x^*)$ as the performance measure because it makes the construction of the PEP kernel more natural. Another compelling reason is its relevance to the well-known convergence rates for the Triple Momentum Method (TMM) and the Information-Theoretic Exact Method (ITEM), we aim to analyze whose ODE models in our paper. The known Lyapunov functions for these methods (see [26, Section 2]) yields convergence rates for the quantity $f(x_{N})-f(x^*)-\\frac{\\mu}{2(1-\\mu/L)}\\|x_{N}-x^*\\|^{2}$, not for $f(x_{N})-f(x^*)$. The continuous-time counterpart for this quantity is preicsely $\\tilde{f}(X(T))-\\tilde{f}(x^*)$. \n\n> Is it possible that the supremum ...\n\nIn the literature on minimizing gradient norm of convex functions following the work [8], it is standard to assume the initial function condition (IFC), that is, $f(x_0)-f(x^*)$ is bounded by some constant. In our work, we assume that the supremum in the inequality (15) is finite, and this assumption can be considered as a natural extension of (IFC) to the strongly convex setting.\n\n> What is $x^{T}$ in equation (20) and (21)?\n\n$x^{T}:=X(T)$. We will clarify this in the final version.\n\n> Typos: line 45, 'enhances'; page 5, footnote 3 line 2, 'space'.\n\nThank you for noting these typos. We will fix them in the final version.\n\nThe reviewer has also provided valuable suggestions, which will be incorporated into the final version."}, {"review_id": "DxINuZwiJL", "reviewer": "Reviewer_PRzN", "summary": "This paper proposes a novel methodology that analyzes ODE models for first-order optimization methods by converting the task of proving convergence rates into verifying the positive semidefiniteness of specific Hilbert-Schmidt integral operators. Based on the performance estimation problems (PEP) and functional analysis, the authors establish convergence rates of various accelerated gradient flow models.  The authors’ continuous time PEP framework provides insights into the analysis of the discrete-time PEP.", "questions": "See the weakness", "limitations": "None", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors developed a novel and simple framework for analyzing the convergence rate of continuous-time dynamics via positive semidefinite kernels.\n\n2. The authors bridge the gap between the PEP framework for the continuous and discrete settings from continuous-time dynamics.\n\n3. the authors’ continuous time PEP framework provides new opportunities for the analysis of the discrete-time PEP.\n", "weaknesses": "1. The results of this paper lack experimental validation.\n\n2. The verification of the positive semidefiniteness of an integral kernel is difficult in implementation. How do you solve the difficulty in the calculation for the integral kernel?\n\n3. There is a misspelling in line 39.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and thoughtful comments. \n\n> The results of this paper lack experimental validation.\n\nIn the initial submission of our paper, we did not include experimental validations, as our primary focus is to provide a new theoretical framework for convergence analysis of ODE models, rather than developing novel algorithms or ODE models. Additionally, most of the obtained convergence guarantee itself, or the corresponding discrete-time convergence guarantee, is already well-known in the literature. However, the convergence guarantee of AGM-SC ODE with respect to the measure $\\Vert\\dot{X}(T)\\Vert^{2}$ is novel. We have performed experiments for this guarantee. The results can be found in Figure 3 of the attached PDF and will be included in the final version.\n\n> The verification of the positive semidefiniteness of an integral kernel is difficult in implementation. How do you solve the difficulty in the calculation for the integral kernel?\n\nWe believe this concern does not significantly impact our contributions. Our work primarily focuses on establishing a theoretical foundation, rather than dealing with implementation. Due to the simplicity of our continuous PEP framework, compared to its discrete counterpart, all the results in our paper can be derived manually, without the need for numerical solvers.\n\nHowever, we agree that the implementation of continuous PEP could be a possible future direction. An integral kernel can be approximated with an arbitrarily small accuracy \\epsilon by finite-rank integral operators (see Townsend & Trefethen, 2013), and one can readily verify the positive semidefiniteness of finite-rank operators. Thus, one can numerically verify the positive semidefiniteness of the given integral kernel, with an appropriate care of numerical approximation errors.\n\n> There is a misspelling in line 39.\n\nIn Line 39, \"typiccally\" should be corrected to \"typically\". Thank you for the catch.\n\n## Reference\n\nTownsend, A., & Trefethen, L. N. (2013). An extension of Chebfun to two dimensions. SIAM Journal on Scientific Computing, 35(6), C495-C518."}, {"review_id": "q1ei1OjEm4", "reviewer": "Reviewer_48x5", "summary": "The article presents a continuous-time optimization framework for convex objectives which streamlines the process of giving rate guarantees.  Beginning from (Exact PEP), a difficult looking infinite-dimensional optimization problem.  This is relaxed using convexity, and then recast in a dual form, wherein it suffices to verify the positive definiteness of a PEP kernel.  This mirrors the discrete PEP kernel of Drori and Teboulle, and the authors show that this continuous PEP kernel can in fact be derived as a certain limit of the discrete one.\n\nThe article then deploys its method on a variety of accelerated ODE methods (Nesterov methods, triple momentum, information-theoretic exact methods, and others).  It additionally considers a variety of standard metrics, as appropriate for different situations (function value convergence, norm of gradient convergence).  The rates given appear to be consistent to state of the art  continuous-time guarantees or mirroring discrete-time guarantees\n\nThe method, which is designed to avoid construction of Lyapunov functions, instead requires construction of a positive definite kernel, which is built from the choice of a Lagrange multiplier function $\\Lambda.$", "questions": "1) Is there a systematic way that you produce the Lagrange multiplier function? If so, this should be more prominently displayed.\n2) The exact PEP is relaxed and them seems to play no further role.  Can you provide any insight in the degree to which this relaxation is sharp? (Are there examples where it is solvable?). Is there anything to say about Exact PEP at all, except for the relaxation?\n3) Can you reverse engineer the c-PEP guarantee to produce optimization methods?\n4) All the rate guarantees (for say the strongly convex case) look largely equivalent.  Is the best possible rate guarantee (say asymptotically) -- given a class of ODE methods with $a\\sqrt{\\mu}$ is second coefficient and $1$ its final coefficient $e^{-c(a)\\sqrt{\\mu}T}$?\n", "limitations": "The article appropriately addresses its limitations.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1) The article is very clearly presented, with a large set of examples to illustrate the method.  This in particular important for illustrating the search for the magic $\\Lambda.$\n2) Certifying that the rate guarantee is correct, given the presented H-kernel (which can be computed directly from the ODE), and given the Lagrange multiplier is simple.  \n3) The article improves some existing rate guarantees and appears to reproduce many of the best-known guarantees, presumably found through more usual Lyapunov functional methods.  In this sense, the article identifies exactly the way in which these Lyapunov functional estimates are optimal (in the sense that the c-PEP guarantees produced this way follow (5) -- see Remark 1).\n4) The method is extended systematically to give convergence of gradients (section 4).", "weaknesses": "1) While the paper removes the need to produce a Lyapunov function, it introduces the need to produce the Lagrange multiplier function $\\Lambda$.  This does not appear to be systemized, and so it raises the obvious question to what extent it is necessary to learn the c-PEP machinery only to search for the $\\Lambda$ when one could just search from the beginning for the more intuitive Lyapunov function.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and thoughtful comments.\n\n> While the paper removes the need to produce a Lyapunov function, it introduces the need to produce the Lagrange multiplier function $\\Lambda$. This does not appear to be systemized, and so it raises the obvious question to what extent it is necessary to learn the c-PEP machinery only to search $\\Lambda$ for the when one could just search from the beginning for the more intuitive Lyapunov function.\n\n> Is there a systematic way that you produce the Lagrange multiplier function? If so, this should be more prominently displayed.\n\nWhile not explicitly mentioned in the paper, there is a rule of thumb for choosing $\\Lambda$ (or $\\lambda$). When the expected convergence rate is $O(1/a(T))$, we found that setting $\\Lambda(t)=a(t)/a(T)$ in Theorem 1 (or $\\lambda(t)=a(T)/a(T-t)$ in Theorem 2) leads to the desired results. For instance, in Line 165, because the known convergence rate of AGM-SC ODE is $O(1/e^{\\sqrt{\\mu}T})$, we set $\\Lambda(t)=e^{\\sqrt{\\mu}t}/e^{\\sqrt{\\mu}T}=e^{\\sqrt{\\mu}(t-T)}$. In the final version of our work, we will include a formal explanation of this rule.\n\n> The exact PEP is relaxed and them seems to play no further role. Can you provide any insight in the degree to which this relaxation is sharp? (Are there examples where it is solvable?). Is there anything to say about Exact PEP at all, except for the relaxation?\n\nDealing with the exact PEP itself is a highly challenging task, and to the best of our knowledge, there is no prior research exploring this direction, even in the discrete-time case. For the discrete PEP framework, [27] showed that using an interpolation argument, the exact PEP can be relaxed into a tractable form, and this relaxation is exact, meaning that the relaxed PEP is equivalent to the exact PEP. However, the relaxation technique applied in our continuous PEP framework mirrors the relaxation technique used for the discrete PEP in [2], which is known to be not tight (see [27, Section 1.4] for a related discussion). It could be an interesting future direction to find an exact tractable reformulation of the exact continuous PEP.\n\n> Can you reverse engineer the c-PEP guarantee to produce optimization methods?\n\nIn the literature, there has been a line of work [7, 26] for producing optimal optimization methods by reverse engineering the discrete PEP presented in [2]. As our continuous PEP serves as a continuous-time counterpart of the discrete PEP, it can be used to produce optimal ODE models. Given a family of continuous-time models (4), parametrized by the kernel $H(t,\\tau)$, we denote the best achievable convergence guarantee as $\\mathrm{Guarantee}(H)$. The task of finding the optimal ODE model is then formulated as $\\min_{H}\\mathrm{Guarantee}(H)$. Using the continuous PEP, we can express $\\mathrm{Guarantee}(H)$ as $\\mathrm{Guarantee}(H)=\\min_{\\lambda}\\mathrm{Dual}(H,\\lambda)$, where $\\mathrm{Dual}$ is the dual objective function defined in (7). Now, the task of finding the optimal ODE model can be formulated as $\\min_{H,\\lambda}\\mathrm{Dual}(H,\\lambda)$. One can generate the optimal ODE models by solving this problem, although it may not be a trivial task.\n\n> All the rate guarantees (for say the strongly convex case) look largely equivalent. Is the best possible rate guarantee (say asymptotically) -- given a class of ODE methods with $a\\sqrt{\\mu}$ is second coefficient and 1 its final coefficient $e^{-c(a)\\sqrt{\\mu}T}$?\n\nWe can partially answer this question as follows: The ODE model $\\ddot{X}+a\\sqrt{\\mu}\\dot{X}+\\nabla f(X)=0$ achieves a convergence rate of $O(e^{-(a-1)\\sqrt{\\mu}T})$, although we do not guarantee that this convergence rate is the best possible. Proof sketch: This ODE model is equivalent to the second Bregman Lagrangian flow in [30] with $\\alpha(t)=\\log\\sqrt{\\mu}$ and $\\beta(t)=(a-1)\\sqrt{\\mu}t$. As a result, it achieves a convergence rate of $O(e^{-\\beta(T)})=O(e^{-(a-1)\\sqrt{\\mu}T})$."}]

Author rebuttal:
Dear all reviewers,

# Figures

The attached PDF file contains the figures mentioned in the rebuttals: Visualization of PEP kernels, and numerical experiment for the convergence rate of AGM-SC ODE obtained in Section 4.

# Relaxing assumptions in Theorem 2

We have relaxed the assumption (16) in Theorem 2. This modification will not affect other parts of our paper, as the revised version is a generalization of the initial version.

## Theorem statement

Remove the assumption (16) and replace the transformation before line 226 with the following:

$g^{G}(t)=\lambda(t)g(t)-\int_{0}^{t}\dot{\lambda}(\tau)\nabla g(\tau)d\tau,$

where $g(t)=\nabla f(X(t))+\mu\int_{0}^{t}\int_{\tau}^{t}h^{G}(s,\tau)ds\nabla f(X(\tau))d\tau$.

(Note: we have shown that this transformation is equivalent to that in the initial submission.)

## Proof

We make the following modifications on Lines 103--117.

Remove Lines 103--108, 110.

Let $\bar{f}(x)=f(x)-\frac{\mu}{2}\|x-x_{0}\|^{2}$. Then, $\bar{f}$ is convex.

Change the definition of $\tilde{f}_{t}(y)$ as follows:

$ \tilde{f}_t(y)=\lambda(t)(\bar{f}(y)-\bar{f}(X(T)))$ 

$\qquad \qquad -\langle \int_0^t\dot{\lambda}(\tau)\nabla\bar{f}(X(\tau))d\tau,y-X(T)\rangle . $

Change the formula after Line 112 as follows:

$ \frac{\partial}{\partial t}\tilde{f}\_{t}(y)|_{y=X(t)} =\dot{\lambda}(T)\left(\bar{f}(X(t))-\bar{f}(X(T))-\left\langle \nabla\bar{f}(X(t)),X(t)-X(T)\right\rangle \right). $ 

Change the definition of $N(t)$ as follows:

$N(t)=\frac{1}{M}\left(\bar{f}(y)-\bar{f}(X(T))-\left\langle \nabla\bar{f}(X(t)),y-X(T)\right\rangle \right).$

Meta-review: The paper introduces a continuous time counterpart to the performance estimation problems (PEP) of Drori and Teboulle, offering a new systematic analysis of convergence rates of the ODE models of first-order methods. The reviewing team unanimously agreed that the proposed methodology is interesting and the paper satisfies the acceptance criteria. The paper's technical foundation is found to be solid. While the approach builds on PEP, designing the continuous-time PEP through functional analysis presents a nontrivial challenge. The article is presented well with numerous examples that demonstrate the effectiveness of the method. 

In terms of weaknesses, the paper lacks experimental evaluation since its focus is primarily on the theoretical foundation of continuous-time PEP. The implementation is deferred to future work, though a basic numerical experiment for the convergence rate of AGM-SC ODE is provided in the rebuttal. Some reviewers raised concerns about the difficulty of identifying suitable Lagrange multiplier functions, which can be considered as a potential drawback. Although no systematic way to find suitable multiplier functions is presented, the authors suggest in their rebuttal a rule of thumb for selecting appropriate functions when we have a prediction on the final convergence rate. A reviewer suggested expanding the literature review. The authors are encouraged to incorporate these suggestions in the camera-ready version and to provide detailed explanations addressing these concerns where relevant.
Decision: Accept (poster)