A Variational Perspective on High-Resolution ODEs
Authors: Hoomaan Maskan
Konstantinos C. Zygalakis
Alp Yurtsever
Venue: NeurIPS 2023 poster (2023)
Keywords: Nesterov's accelerated gradient
gradient descent
Lyapunov function
gradient norm minimization
rate-matching
stochastic variance reduction
stochastic gradient descent
noisy gradient
TL;DR: Through a variational study on high-resolution ODEs, we propose better convergence rate of the gradient norm minimization for the NAG method, deeper study on the rate-matching technique, and an accelerated method for noisy gradients.

Abstract: We consider unconstrained minimization of smooth convex functions. We propose a novel variational perspective using forced Euler-Lagrange equation that allows for studying high-resolution ODEs. Through this, we obtain a faster convergence rate for gradient norm minimization using Nesterov's accelerated gradient method. Additionally, we show that Nesterov's method can be interpreted as a rate-matching discretization of an appropriately chosen high-resolution ODE. Finally, using the results from the new variational perspective, we propose a stochastic method for noisy gradients. Several numerical experiments compare and illustrate our stochastic algorithm with state of the art methods.

A Variational Perspective on High-Resolution ODEs
Hoomaan Maskan Umeå University hoomaan. mww.aaaamaaaaaaaaaaaaaa.mmmm
Konstantinos C. Zygalakis University of Edinburgh k zygalakis@ed ac uk
Alp Yurtsever Umeå University alp. yurtseverrumu..ee
Abstract
We consider unconstrained minimization of smooth convex functions. We pro- pose novel variational perspective using forced Fuler-Lagrange equation that allows for studying high-resolution ODEs. Through this, we obtain a faster conver- gence rate for gradient norm minimization using Nesterov's accelerated gradient method. Additionally, we show that Nesterov's method can be interpreted as a rate- matching discretization of appropriately chosen high-resolution ODE. Finally, using the results from the new variational perspective, we propose a stochastic method for noisy gradients. Several numerical experiments compare and illustrate our stochastic algorithm with state of the art methods.
Introduction
Smooth convex minimization a fundamental class optimization with broad applications and a rich theoretical foundation that enables the development of powerful methods. In fact, the theory and methods developed for other problem classes, such as non-smooth convex or smooth non-conver optimization, often build upon the work done in smooth convex optimization. As result, the study of smooth convex minimization has a significant impact on the broader field of optimization. Over the last two decades, first-order methods -those relying solely gradient information, in contrast to methods like Newton's 's that require Hessian information- have seen a lot of interest both in the- ory and applications due their efficiency and adaptability for large-scale data-driven applications. Among these, gradient descent stands as one of the simplest and oldest. When equipped with an appropriate step-size, gradient descent guarantees suboptimality gap (objective residual) of order (1//k) after k iterations.
In his seminal work, Nesterov 1983 has shown that the gradient method can achieve faster rates by incorporating momentum deviations. Nesterov's ' accelerated gradient algorithm (NAG) ensures convergence rate of ((1 /R.2) which is order of magnitude faster than the gradient descent. Re- markably, this rate matches information-theoretie meaning that NAG is optimal and no other first-order method guarantee essentially faster convergence rate [Nesterov, 2003].
lower bounds for first-order oracle complexity,
The original proof of Nesterov 1983], known the estimate sequence technique, is highly alge- braic and complex procedure, difficult to interpret, and provides arguably limited insight into why momentum deviations help with the convergence rates [Hu and Lessard. [017]. Therefore, many re- searchers have tried to provide a better understanding of momentum based acceleration through dif- ferent perspectives. For example, Su et al [2066]. Shi et al. [202]]. and Sanz Serna and Zygalakis [202]] consider a continuous time perspective) Lessard et al. (2016) and Fazlyab et al. [20 use in- tegral quadratic constraints and control systems with non-linear feedbacks; Muehlebach and Jordan 2019 (2022, 2023) present a dynamical perspective; Attouch et al.) 22020] 2021 utilize inertial dy- namic involving both viscous damping and Hessian-driven damping: Zhu and Orecchia [2014] view acceleration as a linear coupling of gradient descent and mirror descent updates; and Abn and Sra 2022 provide understanding of the NAG algorithm through an approximation of the proximal point method. Our work is focused on the contimuous-time perspective.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In [Su et al,, 2016], the authors derive second-orde ordinary differential equation (ODE) that ex- hibits trajectories similar those of the NAG algorithm in the limit of an infinitesimal step-size + O. This result has inspired researchers to analyze various ODEs and discretization schemes to gain better understanding of the acceleration phenomenon. Notably, Wibisono et (016] demon- strate that the ODE presented in [Su et all 2016] is a special case of a broader family of ODEs that extend beyond Euclidean space. They achieve this by minimizing the action on a Lagrangian that captures the properties of the problem template, an approach known as the variational perspective, and they discretize their general ODE using the rate-matching technique. In related vein, (Shi SSi et all [2021] proposed substituting the low-resolution ODEs (LR-ODEs) introduced in et 2016) with nigh-resolution ODEs (HE-ODEs) which can capture trajectories of NAG more precisely.
Our main contribution in this paper is a novel extension of the variational perspective for HR- ODEs. A direct combination of these two frameworks is challenging, as it remains unclear how the Lagrangian should be modified to recover HR-ODEs. To address this problem, we propose an alternative approach that preserves the Lagrangian but extends the variational perspective. More specifically, instead of relying Euler-Lagrange equation that incorporates external forces acting on the system. By representing the damped time derivative of the potential function gradients as external force, our proposed varia- tional perspective allows us to reconstruct various HR-ODEs through specific damping parameters. More details are provided in (Section 2
the conventional Euler-Lagrange equation, we leverage the forced
Other contributions of our paper are as follows: In Section 3 we show that our proposed variational analysis yields special representation of NAG leading to superior convergence rates than [[Si et all 2019| in terms of gradient norm minimization. rate-matching technique. We demonstrate that NAG can be interpreted as an approximation of the rate-matching technique applied to a specific ODE. Then, in [Section 5 we extend our analysis to a stochastic setting with noisy gradients, introducing a stochastic method that guarantees convergence rates of (1 (1/k://2 for the expected objective residual and Ó (11/33//1) for the expected squared norm of the gradient. Finally, in[Section 6) we present numerical experiments to demonstrate the empirical performance of our proposed method and to validate our theoretical findings.
(Section 4. we propose an HR-ODE based on the
Problem template and notation. We consider a generic unconstrained smooth convex minimiza- tion template:
min (x) 2ER
where / RR > R is convex and L-smooth, meaning that its gradient is Lipschitz continuous:
[v vf(())l S L||=- yll, Vr,y E R",
(2)
with || denoting the Euclidean norm. We denote the class of L-smooth convex functions by Fr. Throughout, we assume that the solution set for Problem ①I is non-empty, and we denote arbitrary solution by x=, hence f == f(x*) ) & fx) for all x E R
The NAG Algorithm. Given initial state zo yo E R and step-size parameter 0, the NAG algorithm updates the variables Iy and yk iteratively as follows:
yk+1 I fVx(,,,
(NAG)
Fa+1 = 3k+z + k 3 (0k+1 3ke.
Low-Resolution and High-Resolution ODEs. Throughout, by LR-ODE, we refer to the second- order ODE introduced and studied in (Su all. 2016), which exhibits a behavior reminiscent of momentum-basee accelerated methods like Heavy Ball (HB) and NAG in the limit of step-size s + Unfortunately, this generic ODE cannot distinguish the differences between HB and NAG. It is important to note, however, that the guarantees of HB and NAG differ significantly in discrete time. Specifically, HB has guarantees for only specific subset of Problem (.) whereas NAG guarantees a solution for all instances of ( with appropriate step sizes. Therefore, it's worth noting that the LR-ODE may not fully capture certain important aspects of the NAG trajectory. Conversely, by HR-ODEs, we refer to the ODEs proposed in [Shi et al.. [022]]. which extend the LR-ODE by incorporating gradient correction terms. Through this extension, HR-ODEs provide a more precise representation of the trajectory for these distinct algorithms.

---

2 External Forces and High-Resolution ODEs
Consider the Lagrangian
= e (1
=
Here, X, E Rd is the first time-derivative of (t), and 0t 04,,8,77 : T IR continuously differentiable functions of time that correspond to the weighting of velocity, the potential function f. and the overall damping, respectively. Using variational calculus,
define the action for the curves
A(X) JR L(x,, Xx, ()d.. In the absence of external forces, a curve stationary point for the problem of minimizing the action A(X) if and only if it satisfies the oc Buler Lagrange equation d #c (Xt, Xe; {) ax, (Xe, X2,(). This was used in WWibisono et all
{X+: RJ the functional
axx,
2016 Wilson et al. 202 to calculate the LR-ODEs for convex and strongly convex functions Note that the Euler-Lagrange equation as written, does not account for an external force, (which non-conservative). In this case, the Euler- equation should be modified to the forced Euler-Lagrange Equation
f 0L (X,, Xx,)) dt oxx,
UC (Xe, t),t)
(4)
ax.
which itself is the result of integration by parts of Lagrange d' Alembert principle 2021]. Using the Lagrangian
[Campos et al
B) we have
OC (X,, X,,t) e Xi),
dL
(X,, X,,t) te (VS(X.)). (V(())
(5)
ax,
0X,
Substituting (5) in gives
X. (fx dz) 20 (X())) c.
(6)
In what follows, will present various choices of the external force F, including two for convex functions and one for strongly convex functions.
2.1 Convex Functions
First choice for convex functions. Let first consider the following external force:
F = 55 d
1e- ((())
dt
In this case, 6 becomes
X. + (fr - a,) + 20r 2 -se [ ((())]
(8)
di
It is possible to show the convergence of X; to x- and establish convergence rate for this as shown in the following theorem (proof in Appendix A.1). The proof of this theorem (and the sub- sequent theorems in this section) is based on the construction of suitable Lyapunov function for the corresponding ODE (e.g. see [Siegel, 2019, Shi all 2019. Attouch et all 2020. 2021)). This non-negative function attains zero only at the stationary solution of the corresponding ODE and decreases along the trajectory of the ODE [Khali. 2002 For this theorem (and the subsequent theorems), we will define proper Lyapunov function and prove sufficient decrease of the function along the corresponding ODE trajectory.
Theorem 2.1. Under the ideal scaling conditions 3, e and tt e X, will satisfy
f(Xi) - f(x²)=====) O
for f E Fr.
Wilson et al [202 use different Lagrangian for strongly convex functions, but the methodology is the same.

---

Now, choosing parameters
0+ = log(n(t)), & ==loo((()//(()), =
(9)
in S
gives
X, (n(t) a(t)
ale)
xx Vf((X) 0,
(10)
F= -5 Lle V(()),,
which reduces to
Xe+ + ( + voV x,+ (cp2p Vs) Vf(Xi) =0, 0,
p+1
(11)
by taking ret) = 8 q(t) = Cpt
p
Remark 2.1.1. For = C,C = 1/4, equation
corresponds to the (H-ODE) in
[Laborde and Oberman 2020
Second choice for convex functions. Now, consider external force given by
F -oe d (o-(a-BOV
(12)
dt
In this case, replacing F in ) gives
X + (ix - az) + 2ar Vf = -5
dt le -o)
- fXx))
(13)
We establish the following convergence result, and the proof can be found in Appendix A.2.
Theorem 2.2. Under the modified ideal scaling conditions 3. S Let, , ex ,3, c 3, + 201
X₁ in (13 will satisfy
f(X.) - f(x)) 00 =0 ( c.: + Usc 201 Br
for f E FL.
Taking the same parameters in (9) gives
X + (n(() π(0
a(t)
VoV* - (n(V)(()) (=((())
A(0) (0)m(()-(0g(())) (xx) = 0,
m(()(())
F = - - [e-la-
(14)
which reduces to
X.+ + p+1 + +VVP)(()) X, (COPM-2 15(p+ vf(x)) = 0, (15)
for n(l) pppp:ttl q(t) Cptp-1
Remark 2.2.1. Note that setting = 1/4,,p p= 2 will lead to the ODE
3 ( voV* X. + (1+ 3/8 t vf(X)) =
X,
(16)
This ODE was discretized using the Semi- Semi-Implicit Euler (SIE) and the Implicit Euler (IE) discretiza- tion schemes in [Shi et all 2019). The corresponding optimization algorithms were shown to accel- erate. In addition, note that the convergence rate proved Theorem 2. faster than counterpart in Theorem 2.1
2.2 Strongly Convex Functions
Our analysis is applicable to strongly convex functions as well. Consider the Lagrangian proposed in Wilson et al., 2021] for strongly convex functions
L(X,, X., = - + 1 1 3212-f(X3)
(17)

---

Then, the forced Euler-Lagranee equation 4 becomes
F
+ (-àr t/ 3.)
2220 VS(X)=
(18)
pee 1
Taking F= -V (e Vf(())) in 18) gives
+ + i + 3) + e v(())= -vse 20 - (c (c Vf((i))
di
(19)
P
We can establish the following convergence result for X, in (19) to the unique minimizer x². The proof this result is deferred to Appendix A.3.
Theorem 2.3. Under the modified ideal scaling conditions at = a, Br S e ft = eh, and B. 2 X, in 19 satisfies
f(X)) - 5(e=))
(20)
for p-stroogly convex function Remark 2.3.1. Taking a log(VR) and 7t Be vut in 19 gives the NAG's corresponding
HR-ODE
X. (2V7 VVV* + V (fX) 0,
(21)
for j-stroogly convex function f as in Shi ct al 2021
3 Gradient Norm Minimization of NAG
One of the implications of our variational study on HR-ODEs in Section was the ODE formulating this ODE gives
14 Re-
{
X, = =() - X,) VXVI(X,)
1 = -())((()))))) - V Act)olll (X())).
(22)
(()0((
Applying the SIE on 22 for X(t) = ((t)), V(t) = V(ta), nltx) = p//x, gtxx) = Cpt p = 2, 4 = k/s and C - 1/4 gives
{
Tk+1 = I'k + 2 ( - 2k+1) s sf(x)) R
- sV f
(23)
Uk+1 = Uk - [((s)
which is exactly the NAG algorithm. The interpretation of the NAG method as the SIE discretization
of (22) has not been discussed before in the literature (see [Ahn and Sra 2022 for the four most studied representations). It is precisely this connection with the ODE 22 though that inspires choice of the Lyapumov function which in turn gives rise to faster convergence rate. The following theorem formulates this result. The proof is in Appendix A.4 and it is based on the discrete Lyapunov analysis of (33). Similar convergence rate was very recently found by [Chen et al., [222] through implicil velocity perspective HR-ODEs which uses different Lyapunov analysis than this work.
Theorem 3.1. Consider the update
23
Then, if f E Fr. we have
min
[f(x,) < k3 10 - x x11
0sisk-1
and
f(xx) - f(x*)(x'=))))))) <
1 x= x=1
skikk + 2)
for 0 S $ vo- Fo, and any Ig E R.
Remark 3.1.1 (Comparison with state of the art). The rate in Theorem 3.1 is improved compared to the previous rate found in [Shi all 2021],, which is
8568
min [V((2)] < osick
100 x1
(I: + 1)3
for 0 < s 1/(3)) and k 0.
5

---

4
Rate-Matching Approximates the NAG Algorithm
The ODE 1 when p =2 C 1/4 is equivalent
{
Xx ( X1) (XV)(X)),
(24)
-
which can be viewed as a perturbation of the LR-ODE
{
X = -x);
(25)
-
We now show that when the rate-matching technique in [Wibisono et al. 2016 is applied to
25)
the final algorithm reveals similar behavior as (24). This result is then used to approximately recover the NAG method using rate-matchin matching discretization.
Applying the rate-matching discretization on the ODE gives
Tk++ 2 2k + E ys: = - f
(26)
24 = zk-1 1 ((K)).
which has a convergence rate of O(1/(sh?)) Wibisono et al. 2016). In the following proposition, study the behavior of (26) in limit of O. The proof is given in Appendix A.5.
Proposition 4.1. The continuous behavior of (26) approximately
X.+ (++ (++VV+ X.
11+ v
vf(x)) = O,
(27)
which is the the high-resolution ODE (7).
The ODE 27 is the same as (24). In this sense, rate-matching implicitly perturbs the LR-ODE. The question that naturally arises is that when do recover the HR-ODE (66) (which corresponds to
the NAG algortihm through the SIE discretization) from the rate-matching technique? To answer,
we will first perturb the LR-ODE (25) in the second line. Then, the rate-matching discretization is applied. Perturbing gives
X 2 - Xi),
(28)
2 = - - (X,)
Discretizing
28
using the rate-matching method with la = kivo gives
Fk++ = k+2 2k + Uk
y/ Th - (xx))
(29)
z4 zk- - (k + 2)
which is extremely close to the NAG algorithm. Indeed, replacing V (yx) with f(x)) in the third
line of (29) gives exactly the NAG method. Typically, 24 and yı are very close. This is due to Ta and yk having a difference of order s. Since in continuous time X(tx) = Y(4)) (due to s + 0), the HR-ODE of (29) is (16). This means that the corresponding HR-ODE of (29 is
{
x = 2 X.) SXx), - V / f(x.).
(30)
which is the perturbed version 28 and the HR-ODE associated with the NAG algorithm.
5 Stochastic Extensions
In this section, we propose stochastic variation of (23). We model noisy gradients by adding i.i.d noise eq with variance o² to the gradients. Consider the update
Fk+1
Fx +
25B (ux #K+1)
VT. (VI + ek+1)
Bay
(V)( Ek),
(31)
Uk+1
uh [1aSk
25
VT.

---

with 3 2 2. This update reduces to 23 when ex = 0, = refer to (3T) as the Noisy NAG (NNAG) algorithm. NNAG interesting due its capability of dealing with perturbed gradients. This is the case in practical methods e.g. SGD [Bottou. 2010]. SAG ISchmidt al. 2017], SAGA Deffzzio all 2014], SVRG [Johnson and Zhang, 2013 and etc. The following convergence result holds for NNAG, and its proof is in Appendix A.6.
kys. We will
Theorem 5.1. Suppose FL and consider the NNAG method detailed in (31 with the following parameter choices:
k
B22,
2,
Sk
c ka
and tg
Σ S
for some
cs
1
and
3
sacl.
(32)
VL
4
1=1
We define the critical iteration kg as the smallest positive integer that satisfies
1/a
ko 2
(33)
e/L
No 1
LVL
Then, the following bounds hold for all 2 ko
22,4 E[c(ko))+
[kg 4a
2v/.11 5
12-30 30
222
1k0
1-
[[ ff(x))
[1-0]3
22
-10
411 411-
((k) -o 1)
2V1(1-o)
[111 (kl1-a)-))
if 3/4. and
[[[([=)]] - (xx)) Ble(kull+200 log(
+ 802,30p
1/4 1/4 4.
02.200
Ag
1/2
1/2
vI.
(34)
de ((12)>11))0 +
202 (A:1/-1)
i = 3/4 with (k:) = ( 40 (f(xx)) f(x))) + 2 1110 - x= 2.T.
Next, we show that slight modifications to the NNAG method gives rise to another stochastic method with similar convergence rate the NNAG algorithm, but more transparent proof (see Appendix A.7). This proof results in a convergence rate for E mminogisk-1 ll V (z.))]] with a rate of Olog (k) (1.34)) It remains future work to show similar result for the NNAG update.
Theorem 5.2. Suppose FL and consider the following modification of the NNAG method
{
28 (Un 1k+1 3b b2
Ik+1) Ny (Vx) En), 0k+1 = U2 (V
(35)
+ e - + +e+1)).
with the same parameter choices as
(22) Then, the following convergence bounds hold:
E[e(0]]+
(o(11tog(k)) +og()))
a 3
2ca
2(k 3 +k -12-1)
-(())
E[=(0]]
c,,2
(dn-2)
4(to-1) 4(8o)
(36)
(12 u3 44u 3) [1-06---2 (1)
1> a
17² tk- (k:11- a)
=(1-m)
2(1-a)
with [E[=(0)] =1110 xz In addition, for a = 3/4 we have
2VLEE(((O) + (T) +6 2)
min osisk-1 [V](z;)]1
(37)
16c3
63/4
11/4
3 + 11/2
3
Remark 5. The algorithm in 355 reduces
23 when e = 0,
Remark 5.2.2 (Connection NAG). When there is noise (a 0) we can also allow parameter to be zero. This because we do not need to alleviate the effect of the noise with a decreasing step- size. Therefore, we recover the convergence rate of (11 kk²) for the NAG method when c = L/vL. Remark 5.2.3 (Comparison with [Laborde and Oberman 2020)). Laborde et al., proposed a stochas- tic method with noisy gradients. Their method uses another presentation of the NAG algorithm (the presentation from EE discretization). Our rate (36) has the same order of convergence as [Laborde and Oberman, 2020 However, their analysis did not achieve the bound (37) (see
[Lbborde and Oberman. 2020] Appendix C.4).
7

---

Remark 5.2.4 (Comparison between Theorems 5.1 and 5.2)
The rate in 34 is asymptotically similar to (36). However, the transient behavior of 54 is faster than both (36) and the rate in
[Laborde and Oberman, 2020] when T. is large (see Figure 1 top row). This is due to the tuning
parameter 3 which is usually set to I. or higher. This scenario (Large L) often happens in practice, e.g. in training a two-layer Convolutional Neural Network (CNN) [Shi et al. 2022].
Remark 5.2.5 (Limitations and future directions). One limitation of theoretical analysis is that our convergence result for NNAG holds only for large enough number of iterations k 2 kg. How- ever, our numerical experiments we observed that the same bounds hold also for S ko, so we believe our result can be improved. Additionally, our proposed forces are currently defined only in Euclidean space, and we see potential for extending the framework non-Euclidean spaces.
6 Numerical Results
In this section, we present our empirical results, divided into three parts: Theoretical upper bounds, binary classification with logistic regression, and classification with neural networks.
336 with the Proposition 4.5 in Upper Bounds. First, we compare the bounds in 34 and
[Laborde and Oberman. 2020]. The results are depicted in Figure 1 In practical scenarios where L is large [Shi et al [022] the bound (34) is lower than the other two for large enough iterations. This observation has motivated us analyze the behavior of NNAG in practical scenarios such as binary classification and CNN training tasks.
10
Bound value for L 103
Bound value for L = 102
10
Upper-bound
14
10a
Upper-boutt bound
10 a= 3/4
10a
Upper-bond
[2020]]
10a
10a
10
10
10
10
10
10
10
10"
10a
10a
10a
10a
10
10a
10a
10a
10a
10a
10
Iteration
Iteration
Figure 1: Comparison our upper bounds with the state-of-the-an
Binary Classification. For this task we considered d 1000 randomly generated samples of dimension 10 and labels. The problem can be written
d d Σ
min #ER"
log(1 + e -)(()))))
(38)
where Ys and denote the ith label and sample. For comparison, considered the perturbed gra- dient descent method with Gaussian noise and decreasing step-size s = 11/(VLA2/3) (Proposition 3.4 in [Laborde and Oberman, 2020]) together with accelerated noisy gradient descent (Per-FE-CC in [aborde and Oberman, 2020]. For NNAG we used 8₃ = 1/(VLL3/4) and B = L/10. All the perturbation done using i.i.d. Gaussian noise with unit variance, and we conducted 100 Monte- Carlo runs. The results are presented in Figure 2 right panel. As shown, NNAG outperforms all the other methods in this case.
In a related experiment, we combined NNAG with SGD and SVRG. For the SGD-mixing, we re- placed the noisy gradients with SGD-like gradients, while for the SVRG-mixing we evaluated all the gradients at the beginning each epoch (essentially like taking a snapshot SVRG) and set Lg = The step-sizes for SVRG (in accordance with the original implementation [Johnson and Zhang 2013), SGD, NNAG+SVRG, and NNAG+SGD were set 1/(10L), 1/L, c 1/VL, 8 L/10,

---

10
109
NNAG Perturbed Gradient Per-EE-C
Logistic loss
10-3
Logistic loss
10"1
SGI SVRGI NNAGASGID
10-2
10
10-3
10-9
20
60
100
20
80
100
Epoch
Epoch
Figure 2: Comparison of the performance of various methods in binary classification problem.
and c = 1/VT,B I,, respectively. We conducted 100 Monte-Carlo runs, and the results are dis- played in Figure 2eeff panel. Notably, when mixed with either SGD SVRG, NNAG outperforms the original methods. This highlights NNAG's flexibility in terms of gradient noise and demonstrates its potential accelerate various methods.
Classification on CIFAR10. Finally, we tackled the non-convex optimization problem train- ing CNN with CIFARIO dataset [Krizhevsky et all 2009] using the SGD, SVRG, NNAG, and NNAG+SVRG methods. The network consisted of two convolutional layers each followed by max pooling and fully connected linear layers each followed by ReLU activation function. The step- sizes for SGD and SVRG were set as 0.01, and for the NNAG and NNAG+SVRG algorithms we had 0.05, 3 150 and 0.001, 3 100 /10, respectively. The division by 10 is due step- size division by 10 in the SVRG method. The results for 20 Monte-Carla simulations are depicted in Figure 3 Notably, SVRG+NNAG outperforms the other methods terms of minimizing training error Additionally, NNAG exhibits slightly better validation accuracy, hinting at its convergence toward different local solution.
is worth noting that faster convergence rates of NNAG+SVRG do not pose problems of overfitting. If necessary,
terminate the algorithm carlier to achieve optimal performance. In Figure 3 for instance, NNAG+SVRG reaches its peak "validation accuracy" after approximately 20 epochs, with validation accuracy of roughly 0.6 and training slow overfitting phase begins. Similarly, for SGD and SVRG, their peak "validation accuracy" is achieved after about 50 epochs, with validation accuracy of approximately 0.6 and training error of about 0.66, followed by slow overfitting phase. Finally, NNAG achieves comparable results after approximately 100 epochs.
of around 0.66. After this point,
2.5
0.8
2
Validation Accuracy
0.7
Training Error
0.6
1.5
0.5
0.4
0.3
SGD
SVRG
0.2
0.5
NNAG
NNAG+SVRG
0
0
20
40
60
80
100
20
40
60
80
100
Epoch
Epoch
Figure 3: Training emor and validation accuracy of NNAG, SGD, SVRG, and NNAG+SVRG when used for training a simple CNN on CIFARIO 10 dataset. Lower and upper confidence bounds with significance level of 0.68 are drawn with similar color to their corresponding line.

---

7 Related Work
Polyak's Heavy-Ball (HB) method was one of the first momentum methods which could ac- celerate relative to the gradient descent method [Polyakk 1963]. However, this was not the case for every smooth function [Lessard et al. [016]. Nesterov modified the HB and introduced the NAG method. This method achieved global convergence with rate of (1/kk²) for smooth convex func- tions Nesterov, [183]. Nesterov used estimate sequence technique to show the convergence of the NAG method. This technique does not provide immediate insights toward the success of the NAG algorithm in acceleration. Thus, many have tried to understand the essence of acceleration.
On similar line of work, Wibisono al. [0166] introduced a variational perspective accelerated methods, leading to a general (oon-Euclidean) ODE containing the ODE found by SSu et al [2016) as
special case. Their approach is based on the choice of a Lagrangian and its corresponding param-
eters. Since the choice of Lagrangian is not unique WWllson et al. [2021] provided a variational per- spective on different accelerated first-order methods using another Lagrangian. Fazlyab et al. [017
developed a family of accelerated dual algorithms for constrained convex minimization through a similar variational approach. In more recent development, Zhang et all [202]] showed that the
second-variation also plays an important role in optimality of the ODE found by Su et al. (2016).
Specifically, they showed that if the time duration is long enough, then the mentioned ODE for the NAG algorithm is the saddle point to the problem of minimizing the action functional.
The dynamical system perspective on NAG was studied in Muchlebach and Jordan 2019). They showed that the NAG algorithm is recovered from the SIE discretization of an ODE, The mentioned ODE not the result of vanishing step-size argument. They found that survature-depeddee damping term accounts for the acceleration phenomenon. Interestingly, [Chen et al., (022) also used similar ODE without the SIE discretization. They showed that implicit-velee velloitt is the reason of the acceleration. In a recent analysis, [Muchlebach and Jordan, 2023] explores the connections between non-smooth dynamical systems and first-order methods for constrained optimization.
8 Conclusion
In this work, we tackled the problem of unconstrained smooth convex minimization in Euclidean space. Through a variational analysis of HR-ODEs, we achieved improved convergence rates for NAG in terms of gradient norm. In addition, we showed that NAG can be viewed as an approxima- tion of the rate-matching technique when applied on specific ODE, Our analysis was then extended to stochastic scenarios. particular, we proposed method with both constant and varying step- sizes which performed comparable and sometimes better than state of the art methods.
This work entails multiple future directions. Nesterov's 's oracle complexity lower bound on gradient norm minimization is (A=-1) NNsterovv 2003). It remains an open question to see if the NAG method can achieve this rate of convergence for gradient norm minimization. In this work, we no- ticed that the HR-ODEs follow the same external force structure. In the smooth moothh-tronngy convex case, Triple Momentum (TM) method is the fastest known globally convergent method [Van Scoy et all 2018). However, the HR-ODE associated with the TM method is not shown to achieve the similar convergence rate as the TM method (Sun et al. 2020]. One could use the external force structure pro- posed here to find better convergence rate for the HR-ODE associated with the TM algorithm. In addition, our analysis was confined to the Euclidean space. We believe it is possible to explore non- Euclidean forces using a Bregman Lagrangian in Wiiiison et all 2016). Finally, we blended our noisy stochastic scheme with other known stochastic methods (e.g. SGD and SVRG). This technique improved the performance of those methods. As future work, one can apply the same technique to other practical methods like ADAM, RMSprop, etc, and study the behavior of the final algorithm.
Acknowledgements
Alp Yurtsever and Hoomaan Maskan received support from the Wallenberg AI, Autonomous Sys- tems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. Kon- stantinos C. Zygalakis acknowledges support from a Leverhulme Research Fellowship (RF/2020- 310), and the EPSRC grant EP/V006177/1. We gratefully acknowledge the support of NVIDIA Corporation with the donation of 2 Quadro RTX 6000 GPUs used for this research.
10

---

References
K. Ahn and S. Sra. Understanding nesterov's acceleration via proximal point method. In Symposium on Simplicity in Algorithms (SOSA), pages 117-130. SIAM, 2022.
H. Attouch, Z. Chbani, J. Fadili, and H. Riahi. First-order optimization algorithms via inertial systems with hessian driven damping. Mathematical Programming, pages 1-43, 2020.
H. Attouch, Z. Chbani, J. Fadili, and H. Riahi. Convergence of iterates for first-order optimization algorithms with inertia and hessian driven damping. Optimization, pages 1-40, 2021.
L. Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMP- 2010: 19th International Conference on Computational StatisticsParis France, August 22- 27, 2010 Keynote, Invited and Contributed Papers, pages 177-186. Springer, 2010.
C. M. Campos, A. Mahillo, and D. M. de Diego. A discrete variational derivation of accelerated methods in optimization. arXiv preprint arXin:2/00.02700, 2021.
S. Chen, B. Shi, and Y.-x. Yuan. Gradient norm minimization of nesterov acceleration: o(1/k=). arXiv preprint arXiv:2209.0888 2022.
A. Defazio, F. Bach, and S. Lacoste-Julien. Saga: A fast incremental gradient method with sup- port for non-strongly convex composite objectives. Advances in neural information processing systems, 27, 2014.
M. Fazlyab, A. Koppel, V. M. Preciado, and A. Ribeiro. variational approach to dual methods for constrained convex optimization. In 2017 American Control Conference (ACC), pages 5269- 5275, 2017. doi: 1022919/AAC220177799777.
M. Fazlyab, A. Ribeiro, M. Morari, and V. M. Preciado. Analysis of optimization al-
gorithms via integral quadratic constraints: Nonstrongly convex problems. SIAM Jour- nal on Optimization, 28(3):2654-2689, 2018.
doi: 10.1137/17M11166455 URL
https: //doi org/oog//// wttp//....//////....// 1137/17MM116945
B. Hu and L. Lessard. Dissipativity theory for nesterov's accelerated method. In International Conference on Machine Learning, pages 1549-1557. PMLR, 2017.
R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive variance reduc- tion, Advances in neural information processing systems, 26, 2013.
H. K. Khalil. Nonlinear systems third edition. Patience Hall, 115, 2002.
A. Krizhevsky, G. Hinton, et al. Learning multiple layers features from tiny images. Toronto, ON, Canada, 2009.
M. Laborde and A. Oberman. A Iyapunov analysis for accelerated gradient methods: from de- terministic to stochastic case. In S. Chiappa and R. Calandra, editors, Proceedings of the Twenty Third International Conference Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 612-612. PMLR, 26-28 Aug 2020. URL httpss:/prroceedingg mlr. ppress/v108/labbreeeeeo html
I.. Lessard, B. Recht, and A. Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM J. Optim., 26:57-95, 2016.
M. Muehlebach and M. Jordan. A dynamical systems perspective on nesterov acceleration. In International Conference on Machine Learning, pages 4656-4662. PMLR, 2019.
M. Muehlebach and M. I. Jordan. On constraints in first-order optimization: A view from non- smooth dynamical systems. Journal of Machine Learning Research, 23(256): 2022.
M. Muehlebach and M. I. Jordan. Accelerated first-order optimization under nonlinear constraints.
arXiv preprint arXiv:2302.00:: 2023.
Y. Nesterov. A method for solving the convex programming problem with convergence rate o(1/22). Proceedings of the USSR Academy of Sciences, 269:543-547, 1983.

---

Y. Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
B. Polyak. Gradient methods for the minimisation of functionals. Ussr Computational Mathematics and Mathematical Physics, 3:864-878, 1963.
J. M. Sanz Serna and K. C. Zygalakis. The connections between Iyapunov functions for some optimization algorithms and differential equations. SIAM Journal on Numerical Analysis, 59(3): 1542 1565, 2021.
M. Schmidt, N. Le Roux, and Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming. 122 2017.
B. Shi, S. S. Du, W. J. Su, and M. I. Jordan. Acceleration via symplectic discretization of high- resolution differential equations. arXiv preprini PeXii:/902.0530 2019.
B. Shi, S. S. Du, M. Jordan, and W. Su. Understanding the acceleration phenomenon via high-resolution differential equations. ArXiv, 0bs/1810008807,2222.
Z. Shi, Y. Wang, H. Zhang, J. Z. Kolter, and C.-J. Hsieh. Efficiently computing local lipschitz constants of neural networks via bound propagation. Advances in Neural Information Processing Systems, 35:2350-2364, 2022.
W. Siegel. Accelerated first-order methods: Differential equations and Yyaрunov functions. arXiv preprint arXiv:I903.0500 2019.
W. Su, S. Boyd, and E. J. Candès. A differential equation for modeling nesterov's accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 17(153): -43, 2016. URL http:///://mmrr http:/irrrrorral.mmmmmmmm http:/ppppss////eeeeee/ee html
B. Sun, J. George, and S. S. Kia. High-resolution modeling of the fastest first- order optimization method for strongly convex functions. In 59th IEEE Conference Decision and Control, CDC 2020, Jeju Island, South Korea, December 14-18, 2020, pages 4237-4242. IEEE, 2020. doi: 10. 200/CIDCA2244.2220009000 https://doi. arg/10. 1109/ 002009304444
URL
B. Van Scoy, R. A. Freeman, and K. M. Lynch. The fastest known globally convergent first-order method for minimizing strongly convex functions. IEEE Control Systems Letters, 2(1):49-54, 2018. doi: L0.1109LLSSS..01...... SSS.SSSS...17.222200055
A. Wibisono, A. C. Wilson, and M. I. Jordan. variational perspective on acceler- ated methods in optimization. Proceedings of the National Academy of Sciences, 113 URI
(47358 2016. ISSN 0027-8424. doi: (0.1077/pmaa..611733113 https://www, pnas. cott//t/t13///////////
A. C. Wilson, B. Recht, and M. I. Jordan. A Iyapunov analysis of accelerated methods in optimiza- tion. J. Mach. Learn. Res.,
P. Zhang, A. Orvieto, and H. Daneshmand. Rethinking the variational interpretation of accelerated optimization methods. Advances in Neural Information Processing Systems, 34:14396-14406. 2021.
Z. A. Zhu and L. Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. In Information Technology Convergence and Services, 2014.
12


Reviews:
[{"review_id": "MDLW7jgFEb", "reviewer": "Reviewer_CWtz", "summary": "This paper did four works about High-Resolution ODEs and first-order optimization algorithms. The first part uses forced Euler-Lagrange equations to generalize the analysis of Low-Resolution ODEs to High-Resolution ODEs. The second part is a refined result for bound estimation of gradient norm. The third part is an interpretation of Nesterov’s acceleration by rate-matching discretization. In the last part, the authors propose a stochastic version of Nesterov’s accelerated gradient method, named NNAG in this paper, and compared it to several known stochastic methods on binary classification and training CNN.", "questions": "The Lagrange function is kinetic energy minus potential energy (though multiplied by some decreasing coefficient). The Lagrange function and external force is considered separately in this paper. Is it possible to give physical explanation about the acceleration by forced Euler-Lagrange equation and use different energy function and external force to inspire better algorithm design?", "limitations": "The authors have adequately addressed the limitations and have indicated problems for further study. This work appears to have little negative societal impact.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper proposes a new idea of external force and uses the idea of forced Euler-Lagrange equations to generalize the analysis of Low-Resolution ODEs to High-Resolution ODEs. This leads to a new formulation of NAG. Combined with rate-match discretization, the authors discover a new connection of NAG and the continuous ODE, i.e., it is understood as a perturbation of the Low-Resolution ODE. The new formulation of NAG further inspires the framework of Noisy NAG. The idea of forced Euler-Lagrange equations may bring new insight to fast algorithm design.", "weaknesses": "Although this paper provides a new reformulation of NAG, as the author suggested, the refined convergence rate of gradient norm for NAG is already appeared in [S. Chen, B. Shi, and Y.-x. Yuan. Gradient norm minimization of nesterov acceleration: o(1/k^3). arXiv preprint arXiv:2209.08862, 2022]. The Lyapunov function is essentially the same using the implicit-velocity form and the explicit-velocity form in [B. Shi, S. S. Du, M. I. Jordan, and W. J. Su. Understanding the acceleration phenomenon via high-resolution differential equations. ArXiv, abs/1810.08907, 2021].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and comments. In what follows, we address and respond the points raised by the reviewer.\n\n\n**Reviewer**: \"Although this paper provides a new reformulation of NAG, as the author suggested, the refined convergence rate of gradient norm for NAG is already appeared in [Chen et al., 2022].\"\n\n**Authors**: [Chen et al., 2022] appeared while we were already working on our paper. Although they achieve essentially the same convergence rate, the analysis techniques are significantly different. In particular, they follow an implicit velocity perspective leading to a different Lyapunov analysis, whereas we introduced the forced Euler-Lagrange perspective. Despite the end results being similar, we believe that our analysis is interesting in its own right. In particular, the use of external forces can inspire new methods or new convergence results for existing methods. \n\n\n**Reviewer**: \"The Lyapunov function is essentially the same using the implicit-velocity form and the explicit-velocity form in [She et al., 2021].\"\n\n**Authors**: Although our Lyapunov function is essentially the same as in [1] and [2], we would like to highlight that our new representation (please see (21)) enhances the understanding behind the selection of this Lyapunov function. This is due to the fact that the second component of this Lyapunov function, represented as\n$$\\left( \\frac{1}{2}||x_{k+1}-x^*+\\frac{k}{2}(x_{k+1}-x_k)+\\frac{ks}{2}\\nabla f(x_k)||^2 \\right)$$\nequates to \n$$\\frac{1}{2}||v_k-x^*||^2$$\nwhere $v_k$ is defined in (21) (it is easy to see this simply by rewriting $v_k$ as a function of $x_k$ and $x_{k+1}$ by using the first line of (21)). This intuitive understanding seems to be missing in the prior work. \n\nIn addition, please note that one of the main goals of [1] is to simplify the analysis in [2]. Our work significantly advances this aim: Upon comparing the proofs of Theorem 3.1 in [1], Theorem 6 in [2], and Theorem 3.1 in our work (see Appendix A.4), it is apparent that our new representation substantially simplifies the algebraic aspects of the proof. \n\nWe will further clarify these connections and make comparisons with the existing approaches in the camera-ready version. \n\n\n**Reviewer**: \"Is it possible to give physical explanation about the acceleration by forced Euler-Lagrange equation and use different energy function and external force to inspire better algorithm design?\"\n\n**Authors**: From a physical perspective, the forces are non-conservative (line 87 in our paper) meaning that they are dissipative in nature, similar to friction or air resistance. This characterization provides a more comprehensive and accurate formulation compared to that in [3], which depicts a particle losing potential energy and gaining kinetic energy and therefore accelerating. In this respect, proper choice of the force leads to a more accurate physical model and thus better algorithm design and can even yield other interesting findings. For example, in the strongly convex regime, choosing an appropriate force to derive the HR-ODE of the TM method could unveil new convergence rates for both the HR-ODE and the algorithm (line 287 in our paper). As it stands, the HR-ODE in [4] for the TM method has a proven convergence rate that is slower than the algorithm itself. We will provide a detailed discussion on this in the camera-ready version.\n\n**References**\n\n[1] S. Chen, B. Shi, and Y. Yuan. \"Gradient norm minimization of nesterov acceleration: $o(1/k^3)$\" (2022)\n\n[2] B. Shi, S. S. Du, M. I. Jordan, and W. J. Su. \"Understanding the acceleration phenomenon via high-resolution differential equations\"(2021)\n\n[3] A. Wibisono, A. C. Wilson, and M. I. Jordan, \"A variational perspective on accelerated methods in optimization\" (2016)\n\n[4] B. Sun, J. George, and S. S. Kia. \"High-resolution modeling of the fastest first-order optimization method for strongly convex functions\" (2020)\n\n"}, {"review_id": "OQjE2Piy2p", "reviewer": "Reviewer_ZUpb", "summary": "They generalize the Lagrangian formulation of known first order optimization methods [Wibisono et al., 2016, Wilson et al., 2021] by introducing the notion of external forces, and show theorems on convergence of convex/strongly convex functions. \n\nIn addition, they show the variational analysis leads a special representation of NAG, and it enjoys to superior convergence rates than [Shi et al., 2019]. Based on the special representation of NAG, they generalize it to stochastic variation in Section 5, called NNAG, and show its convergent theorem. \n\nThey check the practical behavior of the proposed NNAG by using \n- binary classification,\n- classiﬁcation on CIFAR10.", "questions": "- Is there any natural/theoretical motivation to introduce i.i.d. noise to the gradients in section 5?\n- Is there any strong incentive to use NNAG or its variants compared to SGD in practice?\n- Besides it, the authors wrote `As the figure depicts, the SVRG+NNAG performs faster than the other methods in terms of minimizing the training error.`, but minimizing training error itself sounds possibility of overfitting in machine learning context. If not, please correct me.", "limitations": "n/a", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "originality\n- Introducing the external force term to the Lagrangian formulation and show convergent theorems with it. \n\nquality/clarity\n- They show their idea and mathematical statements clearly, and show their proofs.\n\nsignificance\n- Their formulation can lead known dynamics also. In this sense, their proposal can be regarded as a unification of various optimization dynamics.", "weaknesses": "- The first part of the paper sounds natural, but to me, there seems no theoretical reason to introduce i.i.d. noise to the gradients in section 5.\n- In my opinion, they should conduct more numerical experiments. For example, the experiments in classification on CIFAR10, NNAG and SVRG+NNAG are competitive to SGD. This result, itself is good, but it means there is no big incentive to use the proposed algorithm, but SGD.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and comments. We are pleased that you recognized the strength of our paper in terms of originality, quality/clarity, and significance. Below, you will find our responses addressing the concerns you raised. \n\n**Reviewer**: “The first part of the paper sounds natural, but to me, there seems no theoretical reason to introduce i.i.d. noise to the gradients in section 5. Is there any natural/theoretical motivation to introduce i.i.d. noise to the gradients in section 5?”\n\n**Authors**: The motivation for studying the model with i.i.d. noise in Section 5 is twofold: From a practical standpoint, this choice is motivated by the fact that many algorithms employed in machine learning (for example for training neural networks) are characterized by noisy gradients [1,2,3]. Thus, adding noise to the gradients takes our theoretical results from the earlier sections one step closer to the real-world practical scenarios. In addition, from a theoretical standpoint, our interest lay in probing the novel representation (21). For instance,  [1] extends the continuous time analysis of deterministic NAG from [4] to a stochastic setting. Similarly, we extended our analysis in Section 5 to investigate the impacts of the new representation (21) in the stochastic setting. \n\n**Reviewer**: “In my opinion, they should conduct more numerical experiments. For example, the experiments in classification on CIFAR10, NNAG and SVRG+NNAG are competitive to SGD. This result, itself is good, but it means there is no big incentive to use the proposed algorithm, but SGD. Is there any strong incentive to use NNAG or its variants compared to SGD in practice?”\n\n**Authors**: As an incentive, we can highlight that SVRG+NNAG outperforms SGD in terms of convergence rate in our experiments. However, we wish to emphasize that our primary contribution lies in a new comprehension of acceleration, and SVRG+NNAG simply serves as a proof-of-concept resulting from this insight. \n\nThe main contribution of our paper is a novel understanding of the acceleration phenomenon through an innovative extension on the continuous time analysis of the Nesterov’s accelerated gradient (NAG) method that leverages the forced Euler-Lagrange equation that we present in Section 2. Although NAG itself is mathematically well-founded, the particular mechanisms behind its effectiveness are not immediately obvious and often considered ‘mysterious’; please see lines 28-50 in our paper for a short survey on different attempts to ‘demystify’ this phenomenon. In this context, our novel understanding of acceleration through the forced Euler-Lagrange equation is interesting in its own right. Nevertheless, beyond its theoretical significance, we believe that this novel perspective also holds great potential for deriving new results and practical algorithms. We mention some immediate implications in Sections 3, 4, and 5, with SVRG+NNAG being just one of these examples. Our goal in Section 5 is to demonstrate the potential of exploring different representations (like (21)) in practice. This idea is further emphasized in the future directions, including the combination of NNAG with ADAM or RMSprop.\n\nFinally, we are open to the idea of including more numerical experiments if the reviewer can provide specific recommendations regarding the suggested experiments.\n\n**Reviewer**: “Besides it, the authors wrote \"...\", but minimizing training error itself sounds possibility of overfitting in machine learning context. If not, please correct me.”\n\n**Authors**: In the context of neural networks (or non-convex optimization in general), there is always the possibility of overfitting as well as converging to a poor local minimum that does not generalize well. This is why we include both \"validation accuracy\" and \"training error\" plots in Figure 2. These plots help us ensure that these issues do not arise in our experiments. \n\nIt is important to note that faster convergence rates of NNAG+SVRG do not pose problems of overfitting. If needed, one can terminate the algorithm earlier to achieve top performance more quickly. This observation is evident in Figure 2. For instance, NNAG+SVRG achieves the top \"validation accuracy\" after around 20 epochs (with a validation accuracy of approximately 0.6 and a training error of approximately 0.66), after which a slow overfitting phase begins. Similarly, for SGD and SVRG, their peak \"validation accuracy\" results are achieved after approximately 50 epochs (with a validation accuracy of around 0.6 and a training error of about 0.66), followed by an overfitting trend. Finally, NNAG achieves comparable results after roughly 100 epochs. We will include this discussion in our camera ready version. \n\nFinally, please note that any technical analysis of the generalization error and/or overfitting is outside of the scope of our paper. \n\n\n**Before we conclude**, we would like to kindly express our surprise regarding your relatively low score for our paper, especially because your review acknowledges the strengths of our paper in terms of originality, quality/clarity, and significance. Based on your feedback and statements, it appears (in our opinion) that the positive aspects of our work are more crowded than the negative ones. We have noticed that your concerns are focused on the stochastic extension in Section 5. In light of the comprehensive responses we have provided above for your concerns, we hope that you would consider reevaluating your score for our submission.\n\n**References**\n\n[1] M. Laborde and A. Oberman. “A Lyapunov analysis for accelerated gradient methods: from deterministic to stochastic case” (2020)\n\n[2] A. Defazio, F. Bach, S. Lacoste-Julien, \"SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives\" (2014)\n\n[3] J. Wu et al. “On the Noisy Gradient Descent that Generalizes as SGD” (2019)\n\n"}, {"review_id": "OjCtozXcsR", "reviewer": "Reviewer_A9z2", "summary": "This work combines variational perspective approach with high-resolution ODE functions to investigate the Nesterov accelerated gradient descent algorithm (NAG). With variational perspective, the authors reconstruct various high-resolution ODEs derived in previous research using alternative methods. Moreover, through this approach, they propose a special representation of NAG that exhibits an improved convergence rate in terms of gradient norm minimization. The authors also discuss some new properties of rate-matching technique. Finally, the authors analyze the stochastic setting both theoretically and empirically. ", "questions": "1.\tIt is unclear to me that equation (21) and equation (27) (by replacing one term) is equal to NAG (line 76), why is that? \n2.\tIn line 211, the authors say that practically $k_0$ is lower than the term $(\\cdot)^{1/\\alpha}$. However, one of the conditions in Theorem 5.1 and Theorem 5.2 is that $k_0\\geq (\\cdot)^{1/\\alpha}$, does that mean this condition will not be satisfied in practice? \n", "limitations": "The authors don't specifically discuss the limitations of this work. The authors may consider adding a paragraph in their manuscript to discuss the limitations of their work based on the reviewer's feedback. \n\nI don't think there will be a significant negative societal impact of this work. ", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1.\tThe idea of combining variational perspective and high-resolution ODEs by including external forces is very interesting. \n2.\tThe authors show several important theoretical results in their manuscript. By carefully checking their proofs of theorems (except for Section 5 because of time), I think overall these results are correct. \n3.\tThe numerical results indicate the potential of having better optimization algorithms based on the theoretical results in this manuscript. \n4.\tOverall, the manuscript is well written. \n\nOverall, I have a positive impression of this work, however, I also admit that I am not an expert in this specific field, which may affect my confidence in assessing its accuracy and significance. \n", "weaknesses": "1.\tIt would be better to have a more detailed introduction to low-resolution ODEs and high-resolution ODEs. Without reading some previous work, it is difficult to understand the differences between low-resolution ODEs and high-resolution ODEs. Are high-resolution ODEs the ODE functions that contain the learning rate $s$? Why do people need to care about high-resolution ODEs? \n2.\tI feel that the proof of Proposition 4.1 is more of an intuition rather than a rigorous demonstration. The treatment of the condition $s\\to 0$ seems imprecise, as sometimes the authors will directly consider this condition as $s=0$ (e.g. line 60), while at other times the authors maintain $s$ to be a non-zero value (e.g. line 59). The use of the word “approximately” in Prop 4.1 is also vague. \n3.\tSome typos/ unclear parts in the proofs that the authors may need to double-check. \n\n(a) line 84, $\\frac{\\partial L}{\\partial X}(X_t,...)$ should be $\\frac{\\partial L}{\\partial X_t}(X_t,...)$.\n\n(b) equation (7), left hand side, $\\bigtriangledown f$ should be $\\bigtriangledown f(X_t)$.\n\n(c) Theorem 2.1, $\\dot{\\gamma}=e^{\\alpha t}$ should be $\\dot{\\gamma}=e^{\\alpha_t}$. \n\n(d) line 138, ODE(14) should be ODE(12). \n\n(e) equation (25) $(3/t+\\sqrt{s}\\bigtriangledown f(X_t))$ should be $(3/t+\\sqrt{s}\\bigtriangledown^2 f(X_t))$.\n\n(f) line 196, $\\sigma$ not introduced, is it the variance of the noise? \n\n(g) equation (38) (appendix), second line $\\sqrt(s)e^{-\\alpha_t}\\ddot{\\beta_t}$ should be $\\sqrt(s)e^{-2\\alpha_t}\\ddot{\\beta_t}$. \n\n(h) line 392, (7) should be (11). \n\n(i) line 406, first equality $+\\frac{1}{2}||v_k-x^*||^2$ should be $-\\frac{1}{2}||v_k-x^*||^2$. \n\n(j) line 408, the term $+\\frac{s^2(k+2)}{4}||\\bigtriangledown f(x_{k+1})||^2$ in the second inequality is left out, therefore the authors need to double-check whether the results still hold after considering this term. \n\n(k) line 411, the first equaltiy redundant, \n\n(l) line 413 \"not ethat\" typo\n\n(m) line 421, the term $\\frac{ks}{2}(\\bigtriangledown f(x_k-\\bigtriangledown f(x_k))$ miss \")\". \n\n(n) equation (62), $(3/t+\\sqrt{s}\\bigtriangledown f(X_t))$ should be $(3/t+\\sqrt{s}\\bigtriangledown^2 f(X_t))$.\n\n4. Figure 1 is hard to read. (font size too small)\n5. It would be better to describe what \"NAG\" means (Nesterov accelerated gradient?) the first time this abbreviation is used.  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and valuable comments. We are pleased that you recognized the strength of our paper in terms of novelty, significance, soundness, and presentation. Below, you can find our responses addressing the concerns you raised. \n\n**Reviewer**: “It would be better to have a more detailed introduction to low-resolution ODEs and high-resolution ODEs. Without reading some previous work, it is difficult to understand the differences between low-resolution ODEs and high-resolution ODEs. Are high-resolution ODEs the ODE functions that contain the learning rates? Why do people need to care about high-resolution ODEs?”\n\n**Authors**: We will update the introduction of our camera ready version with a “Background” section where we describe the terms like “LR-ODE”, “HR-ODE” and “rate matching technique” and their significance to our analysis in order to reach a wider audience, as thoughtfully suggested by the reviewer. \n\nThe HR-ODEs contains the step-size (learning rate) ‘s’ allowing them to effectively incorporate Nesterov's Accelerated Gradient (NAG) method as the step-size changes. In contrast, this is not the case for LR-ODEs which were independent of the step-size (for an illustrative description, refer to [3, Figure 2]).  \n\nThe importance of HR-ODEs lies in their direct connection to accelerated algorithms. These ODEs can be discretized using the common discretization techniques like the semi-implicit Euler discretizer and recover well-known methods like the NAG algorithm. This is not the case for LR-ODEs in [1], where more complicated and less intuitive discretizers (like the rate-matching technique in [2]) are needed. \n\n**Reviewer**: “I feel that the proof of Proposition 4.1 is more of an intuition rather than a rigorous demonstration. The treatment of the condition $s\\rightarrow 0$ seems imprecise, as sometimes the authors will directly consider this condition as $s=0$ (e.g. line 60), while at other times the authors maintain s to be a non-zero value (e.g. line 59). The use of the word “approximately” in Prop 4.1 is also vague.”\n\n**Authors**: We use the term 'approximation' because we employ approximations as in equations (59) and (60). The reason for utilizing different forms of approximations is as follows: Given that $s$ converges to zero more rapidly than $\\sqrt{s},$ we neglect $s$. This same 'approximation' strategy is used in [3, equations (2.2),(2.3)]. We will provide a clear explanation of the concept of 'approximation' in this specific context in our camera-ready version.\n\n**Reviewer**: “Some typos/ unclear parts in the proofs that the authors may need to double-check.”\n**Authors**: Thank you for your careful reading and detailed comments. We will fix these typos and mistakes in our camera ready version. Particularly,\n(f): Yes, $\\sigma^2$ is the noise variance. \n(j): Thanks for noticing this, it is easy to fix this problem. We simply forgot updating the coefficient of $||\\nabla f(x_{k+1})||^2$   to $\\frac{s(k+2)}{4}\\left(\\frac{1}{L}-s\\right)$. This means that the term you pointed out should be combined with the second $||\\nabla f(x_{k+1})||^2$. Therefore, the last 2 lines of (48) should be \n$$=-\\frac{s(k+2)k}{8}\\left(\\frac{1}{L}-s\\right)||\\nabla f(x_{k+1}-\\nabla f(x_k))||^2-\\frac{s(k+2)}{4}\\left(\\frac{1}{L}-s\\right)||\\nabla f(x_{k+1}||^2-\\frac{s^2(k+2)k}{8}||\\nabla f(x_{k})||^2$$\n$$\\leq -\\frac{s^2(k+2)k}{8}||\\nabla f(x_{k})||^2$$\n\n**Reviewer**: “Figure 1 is hard to read. (font size too small)”\n**Authors**:  We will make the font size larger for the camera-ready version.\n\n**Reviewer**:  “It would be better to describe what \"NAG\" means (Nesterov accelerated gradient?) the first time this abbreviation is used.”\n**Authors**: We will clarify this in our camera ready version. \n\n**Question 1**: “It is unclear to me that equation (21) and equation (27) (by replacing one term) is equal to NAG (line 76), why is that?”\n\n**Authors**: This can be seen when one writes down the one line representation of the update (21) or (27) with one term replacement. The pathway is as follows: consider (21), write $v_k$ as a function of $x_k,x_{k+1}$ through the first line of the update (21). Then, replace in the second line and rearrange the terms and get\n$$x_{k+2}=x_{k+1}+\\frac{k}{k+3}(x_{k+1}-x_k)-\\frac{sk}{k+3}\\left( \\nabla f(x_{k+1}-\\nabla f(x_k)\\right)-s\\nabla f(x_{k+1}) $$\n\nwhich is the one-line representation of the NAG method. For (27) after replacing that one term, same approach for the sequence $x_k$ (eliminating $y_k$'s and $v_k$'s) leads to the one-line representation of the NAG method. \n\n**Question 2**: “In line 211, the authors say that practically $k_0$ is lower than the term $(⋅)^{1/α}$. However, one of the conditions in Theorem 5.1 and Theorem 5.2 is that $k_0 \\geq (⋅)^{1/α}$, does that mean this condition will not be satisfied in practice?”\n\n**Authors**: The condition on $k_0$ is the minimum number of iterations needed for our theoretical guarantees to hold. In line 211 we mean that in practice the method achieves the error bounds in Theorems 5.1 and 5.2 even for the smaller number of iterations than the theoretical bound $(⋅)^{1/α}$. In a sense, the method works better than the theory suggests. \n\nThank you for your careful reading. We will clarify this statement to avoid confusions.\n\n**Limitations**: “The authors may consider adding a paragraph in their manuscript to discuss the limitations of their work based on the reviewer's feedback.”\n\n**Authors**: We will add this paragraph, thank you for your suggestions. \n\n**References**\n\n[1] W. Su, S. Boyd, E. J. Candes, \"A Dfferential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights\" (2016)\n\n[2] A. Wibisono, A. C. Wilson, and M. I. Jordan, \"A variational perspective on accelerated methods in optimization\" (2016)\n\n[3] B. Shi, S. S. Du, M. I. Jordan, and W. J. Su. \"Understanding the acceleration phenomenon via high-resolution differential equations\" (2021).\n\n\n"}, {"review_id": "dbUme9ACLd", "reviewer": "Reviewer_rs2m", "summary": "This paper introduces forced Lagrangians in order to better understand discrete schemes for accelerate convex numerical optimization from a continuous-time ODE perspective.", "questions": "none", "limitations": "see \"weaknesses\" on how to improve the presentation", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Two choices of F enable to re-derive continuous-time ODEs which were introduced recently in the literature (Section 2). Likewise, accelerated discrete schemes derive subsequently (Sections 3, 4) recover known schemes or in slightly modified form with slightly superior convergence rates. Empirically, it is demonstrated that even for non-convex network training, applying stochastic versions of accelerated schemes may perform well.\n\nThis paper significantly contributes to our understanding what unconstrained convex optimization with optimal convergence rates really means.", "weaknesses": "Authors use their jargon right from the beginning which makes the paper hard to read for readers who do not work on similar topics. For example, what “LR-ODE”, “HR-ODE” and the “rate matching technique” means should be briefly explained to a broader educated readership in the introduction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and comments. We will update the introduction of our camera ready version with a “Background” section where we describe the terms like “LR-ODE”, “HR-ODE” and “rate matching technique” in order to reach a wider audience, as thoughtfully suggested by the reviewer. "}]

Author rebuttal:

Meta-review: This paper studied High-Resolution ODEs and first-order optimization algorithms by giving 1) a forced Euler-Lagrange equations to generalize the analysis of Low-Resolution ODEs to High-Resolution ODEs, 2) a refined result for bound estimation of gradient norm, 3) an interpretation of Nesterov’s acceleration by rate-matching discretization, and 4) a stochastic version of Nesterov’s accelerated gradient method. All reviewers believe this paper makes an important contribution to the community. The AC agrees and recommends acceptance.
Decision: Accept (poster)