Rethinking the Variational Interpretation of Accelerated Optimization Methods
Authors: Peiyuan Zhang
Antonio Orvieto
Hadi Daneshmand
Venue: NeurIPS 2021 Poster (2021)
Keywords: convex optimization
acceleration
Nesterov
Euler-Lagrange equations

Abstract: The continuous-time model of Nesterov's momentum provides a thought-provoking perspective for understanding the nature of the acceleration phenomenon in convex optimization. One of the main ideas in this line of research comes from the field of classical mechanics and proposes to link Nesterov's trajectory to the solution of a set of Euler-Lagrange equations relative to the so-called Bregman Lagrangian. In the last years, this approach led to the discovery of many new (stochastic) accelerated algorithms and provided a solid theoretical foundation for the design of structure-preserving accelerated methods. In this work, we revisit this idea and provide an in-depth analysis of the action relative to the Bregman Lagrangian from the point of view of calculus of variations. Our main finding is that, while Nesterov's method is a stationary point for the action, it is often not a minimizer but instead a saddle point for this functional in the space of differentiable curves. This finding challenges the main intuition behind the variational interpretation of Nesterov's method and provides additional insights into the intriguing geometry of accelerated paths.


Rethinking the Variational Interpretation of Accelerated Optimization Methods
Peiyuan Zhang* ETH Zurich talantyeri@gmail com
Antonio Orvieto"
Hadi Daneshmand Inria Paris
ETH Zurich aorvieto@ethz..ot
seyed. www.seaannnnnniiiii....
Abstract
The continuous-tine timiimuuuu-tmee model of Nesterov's momentum provides a thought-provoking perspective for understanding the nature of the acceleration phenomenon in convex optimization. One of the main ideas this line of research comes from the field classical mechanics and proposes to link Nesterov's 'ss trajectory the solution of a set of Euler-Lagrange equations relative to the so-called Bregman Lagrangian. In the last years, this approach led the discovery of many new (stochastic) accelerated algorithms and provided a solid theoretical foundation for the design structure- prreturringeseiiingggg. accelerated methods. In this work, we revisit this idea and provide an in in-depth analysis of the action relative to the Bregman Lagrangian from the point of view of calculus of variations. Our main finding is that, while Nesterov's method is stationary point for the action, it is often not a minimizer but instead saddle point for this functional in the space of differentiable curves. This finding challenges the main intuition behind the variational interpretation of Nesterov's method and provides additional insights into the intriguing geometry accelerated paths.
Introduction
This paper focuses the problem of unconstrained convex optimization, i.e. to find
I² E arg min f(z),
(P)
RER
for some lower bounded convex L-smooth loss f E C² (R)
Nesterov's acceleration. Nemirovski and Yudin (1983) showed that no gradient- optimizer
can converge to a solution of (P) faster than O(k 3) where & is the number of gradient evaluations
While Gradient Descent (GD) converges like OO the optimal rate (k-22) is achieved by the
celebrated Accelerated Gradient Descent (AGD) method, proposed by Nesterov 1983):
1:
Tk+11 yk V (yx), with 3/ =
(
(AGD)
4:
+
The intuition behind Nesterov's method and the fundamental reason behind acceleration is, this day, an active area of research (Allen-Zhu and Orecchia 2014 Defazio 2019 Ahn 2020
ODE models. Towards understanding the acceleration mechanism, Su et al. (0016) made an interesting observation: the convergence rate gap between GD and AGD is retained in the continuous- time limits (as the step-size ? vanishes):
X fX()) (GD-ODE),
x x Vf(X)= 0 (AGD-ODE)
'Equal Contribution.
A differentiable function / Idd - is said to be 8-smooth if it has 8-Lipschitz gradients. "This lower bound holds just for d hence it only interesting in the high high-dimensional setting.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

where X := dxjdtt denotes the time derivative (velocity) and X == d2 the acceleration. Namely, we have that GD- converges like O(t-1) and AGD-ODE like (t= where is the time variable. This seminal paper gave researchers new tool to understand the nature of accelerated optimizers through Bessel Functions (Su et al. 2016), and led to the design of many novel fast and interpretable algorithms outside the Euclidean setting (Wibisono et al.) [0166] Wilson cct al., 2019), in the stochastic setting (Krichene et al. 2015 Xu et al. 20188) and also in the manifold setting (Alimisis et al. 2020 Duruisseaux and Leok 2021
Nesterov as solution to Euler-Lagrange equations. It is easy to see that AGD-ODE can be recovered from Euler-Lagrange equations, starting from the time-dependent Lagrangian
L(X,X,) t3 (21xx1e- (1xx1e-f(x)) -Fxip-((x))
Indeed, the Euler- Lagran- equation
( a ((x,XX dt 0x
d
0 x(x 0x
(2)
reduces in this case to 8 + 32 + (( = O. which is equivalent AGD-ODE (assuming
t >> 0). In a recent influential paper, Wibisono et al. (2016) generalized the derivation above to non-Euclidean spaces, where the degree of separation between points and y is measured by means of the Bregman Divergence (Bregman 1967) (2, y) = (vv) vb(x) - (Vob(a)) x²,, where
a/ Rd + R is a strictly convex and continuously differentiable function (see e.g. Chapter 1.3.2
Amari 2016)). Namely, they introduced the so-called Bregman Lagrangian:
I, X, t) ca(0)t(0) (D&(X t ==-l00, V) e x(X)) -())
(3)
where a, 3, are continuously differentiable functions of time. The Euler-Lagrange equations imply
+ -(()) + + 20(()
V - x(1x) Vf(() = O. (4)
The main result of Wibisono al. (2016) is that, under the ideal-scaling conditions /(t) I co(() and (t) ea((), any solution to Eq. (4) converges to solution of (P) at the rate (c)-)(t)) Under
the choice ((r) = ||1z| 2. we get back to the Euclidean metric D (z. y) = 1| - y/13. Moreover,
choosing (t))
(2/t). ((t) (t) 2 log(t). (). we recover the original Lagrangian in Eq.
and O(e 90)) O( 2), derived in Su et al. (2016).
Impact of the variational formulation. The variational formulation in Wibisono et al. (016) has had considerable impact on the recent developments in the theory of accelerated methods. Indeed, this approach can be used to design and analyze new accelerated algorithms. For instance, Xu et al. (2018) used the Lagrangian mechanics formalism to derive a novel simplified variant of accelerated stochastic mirror descent. Similarly, França et al. (2021). Muehlebach and Jordan] (2021) used the dual Hamiltonian formalism to study the link between symplectic integration of dissipative ODEs and acceleration. Due to its rising importance in the field of optimization, the topic was also presented by Prof. M. I. Jordan as a plenary lecture at the International Congress of Mathematicians in 2018 (Jordan 2018). centered around the question "what is the optimal way optimize?".
Imprecise implications of the variational formulation. While the I Lagrangian formalism has been inspiring and successful for algorithm design and analysis, its precise implications for the geometry and the path of accelerated solutions have not been examined in a mathematically rigorous way (to the best of our knowledge). In Jordan (2018) it is hinted that, since Nesterov's method solves the Euler-Lagrange equations, minimizes the action functional Sr La. (Y, Y, t)dd over the space of curves by the minimum action principle of classical mechanics Arroll' d 2013). This claim is inaccurate. Indeed, the term minimum action principle is misleading solving Euler-Lagrange
Paragrapph before Eq. (9) in Jordan 2018): "(...] we use standard calculus of variations to obtain a differential equation whose solution is the path that optimizes the time-intee oone-integrated Bregman Lagrangian".
*From Section 36.2 in Gelfand and Fomin 2000): "The principle of least action is widely used [...]. However. in a certain sense the principle is not quite true [..]. We shall henceforth replace the principle of least action by the principle of stationary action. In other words, the actual trajectory of given mechanical system will not be required to minimize the action but only cause its first variation to vanish." "
2

---

sin (1) perturbation
(tn perturbation
sin (()
perturbation
san (4) perturbation
AGD-ODE persurbation
AGD-ODE perturbation
04
Nesterov
0.3
A. w.r.t. Nesterov
000
0:313
02-
1000
02
tix00
Size perturbation >33
timee
Size perturbation
Figure 1: Optimization of f(x) x²/ /2 using AGD-ODE. Peturbations (vanishing at extrema) are added to the AGD-ODE solution: depending on the perturbation kind (i.e. direction in space of curves), the local behavior is either max or min. Hence. Nesterov's path can be a saddle point for the action (formally shown in Sec. 3.1
only makes the action stationary (necessary condition: vanishing first-order derivative), but does not guarantee minimality this only holds in physics for very special case which do not include even simple mechanical systems like the pendulum (proof in Section 36.2 of Gelfand and Fomin (2000). Indeed, from theoretical perspective, the claim requires computing the second variation along Nesterov's path. Quite surprisingly, even though many papers are dedicated to the variational formulation (Wibisono et al. 2016 Jordan] 2018 Casgrain 2019 Duruisseaux and Leok] 2021), to the best of our knowledge there is no work which provides an in-dhpth rigorous study of the action relative to Bregman Lagrangian and that characterizes minimality of Nesterov in the space of curves.
Our contributions. Intrigued by the non-trivial open question of minimality of Nesterov's 's path and by the enigmatic geometry of accelerated flows, in this paper, we examine the properties of accelerated gradient methods from the perspective of calculus of variations.
1. In Sec. 3 we study the minimality of classical Nesterov's ' ODE (damping 3/t) proposed by Su let al. (2016) on multidimensional quadratic losses. By using Jacobi's theory for the second variation (summarized in Sec. ( find that Nesterov's 's path is optimal only if the integration interval [ (2] is small enough. In contrast, if L2 I v /40/3 (B is Lipschitz constant for the gradient), Nesterov's path is actually a saddle point for the action (see Fig. D-
2. In Sec. 4 we extend the analysis to the u--strongy convex setting and thus consider a constant
damping a. We show that, for extremely overdamped Nesterov flows (a 2 2vF), i.e for highly suboptimal parameter tuning (acceleration holds only for a = 2/P)) Nesterov's 's path is always a minimizer for the action. In contrast, we show that for a < 2/3 (acceleration setting), Nesterov's ' path is again a saddle point for the action.
f2 f > 2T/ /43
3. In Sec. we we discuss the implications of our results for the theory of accelerated methods and propose a few interesting directions for future research.
We start by recalling some definitions and results from calculus of variations, which we adapt from classical textbooks (Landau and Lifshitz 1976 Amoll's d 2013 Gelfand and Fomin 2000).
2 Background on calculus of variations
We work on the vector space of curves C² ([4, (2), Rd)) with 4, l2 E [0, oc). We equip this space with the standard norm ||Y||| = max stst, [t) ]|2 + maxt,seso || (2) Under this choice, for any regular Lagrangian L, the action functional J[Y] == Sr (Y,Ý,t)d is continuous.
First variation. Let D be the linear subspace of continuously differentiable displacements curves The corresponding increment of J at Y along is defined as AJ[Y; Al := J[Y + /t] - J JY] Suppose that we can write AJ ; h] = o|{;; hi] + el|bil, where is linear in h and -> 0 as |||] -> 0. Then, J is said to be differentiable at Y and the linear functional - D > IR such that 8J[Y; h] := >>(Y; h] is called first variation of J at Y. It can be shown that, if J is differentiable at Y, then its first variation at Y unique.
such that h(t1) h(t2)
Extrema. J is said to have an extremum at Y if 38 > 0 such that, Yh E D with ||b||| < 8, the sign of J[Y h J[Y] constant. A necessary condition for J to have an extremum at Y is that
y h] = O, for all h D.
(5)
'e.g free particle in vanishing potentials, or t 12. see Remark 2 the end of Section 21 and Section 36.2.
3

---

We proceed with stating one of the most well-known results in calculus of variations, which follows by using Taylor's theorem J[Y]= S:" L(Y, Y .) dt.
Theorem (Buler-Lagrange equation). necessary condition for the curve Y (a,, f2), to be an extremum for J (w.Et. D) is that it satisfies the Euler-Lagrang equations (
is crucial to note that Theorem I provides necessary, but not sufficient condition for extremum indeed, the next paragraph is completely dedicated to this.
Second Variation. Thm. D does not distinguish between extrema (maxima or minima) and saddles. For this purpose, we need to look at the second variation.
Suppose that the increment of J at Y can be written as AJ(Y; h] = 91 Y A| + P2(YY; hl + + where yii is linear in h, (22 is quadratic in h and + |||||| + 0. Then J said to be twice differentiable and the functional J- :, D + R s.t. J h] := <22lY; hJ is called the second variation of J Y. Uniqueness of second variation is proved in the same way as the first variation. Theorem 2. A necessary condition for the curve Y E (Ct, t2], Rd) to be a local minimum for J (w.rt D) is that it satisfies 8 J[; ; h] 2 O. For local maxima, the sign is flipped.
Jacobi equations. Recall that J[Y] = =,- L(Y,Y, .I)dt. Using the notation Lyz 82 (0Y
the Taylor expansion for AJ(Y; h] J[ + h]
- J[Y] if ||Ab|| - converges to
AJY:: = (1yhh hr
Ex dt 2 0 (Lrrh² + Lyrhh + 22 dt,
(6)
where the equality holds coordinate-wise. Therefore, 8J[Y; = S/1 (Lyh+ Lyh) dt and
1
/ (Lrr + 2L - + L dt
8 J|
2 )
1 1'
(INY-
1.¹²¹ dt (vr)) 1iddt 2 Saa Lygli2d
2 J
1 ('
(Pi²² + Qli)) dl,
)dl,
2 b
where P Lyy. Q Lyy Lyy. and the second equality follows from integration by parts since h vanishes at 1 and 8g. Using this expression, it is possible to derive an easy necessary (but not sufficient) condition for minimality.
Theorem 3 (Legendre's 's necessary condition). A necessary condition for the curve Y to be a minimum of J is that Tay' is positive semidefinite.
Conjugate points. A crucial role in the behavior of J² h] is played by the shape of the solutions
to Jacobi's ' differential equation 4 (Ph) Qh O. A point & E (t1, (t),t2) is said to be conjugate to point 4 (w.rt. J) if Jacobi's equation admits a solution which vanishes at both i and but is not identically zero. We have the following crucial result.
Theorem (Jacobi's condition). Necessary and sufficient conditions for Y be a local minimum for J are: (I) Y satiesfies the Euler-Lagrange Equation; (2) P positive definite; (3) (1,, 12) contains no points conjugate to tj.
3 Analysis of the action of Nesterov's path with vanishing damping 3/t
This section is dedicated to the analysis of the action functional relative to Eq. (3) By incorporating the tool of variational calculus, we study the optimality of Nesterov's method in minimizing the action. We start by general abstract analysis in the convex quadratic case in See. 3.] and then present an intuitive analytical computation in Sec. 3.2 The non-quadratic case is discussed in Sec. 3.4
3.1 Solutions to Jacobi's equation for the Bregman Lagrangian in the quadratic setting
For the sake of clarity, we start by considering the Lagrangian in Eq. for the simple one- dimensional case f(x) = 3x² / We have
d Lvv -Bt". P Lyy = 23.
Q= = Lyy dt
(8)
4

---

11
Solution k())
Fizst cosjugate point
Solution Jacobi M()
Flast conjuupat point
<5
10
sime
sbarpness
time
sharpness
Figure 2: First conjugate point to 4 = 1, 4 for quadratics Bx²/3 /2, under the settings of Section 3.1 For each
value of B. six solutions h(() to the Jacobi equation (each one has different velocity) shown.
Therefore, Jacobi's equation relative to the action functional J L(Y, Y, tt)t with t > 0 is
3 7
di -
35 0.
hh 3t
h
3h 0,
(9)
which is itself Nesterov's ODE, Following the procedure outlined in Theorem solutions h such that h(t1) = 0. Any solution to Eq. (9) can be written as
2 we now study the
((()) C t)(33t -C Vi(VB 1 E(
(10)
I(VBh)
where C' > 0 specifies the initial velocity (see Fig. Ta is the Bessel function of the first kind and Va is the Bessel function of the second kind.
[a(x)
(-1)"M
② (
2m+aa
Va(x)
[a(z) cos(aT) - [r((r) sin(a.)
(1I)
m! 7(m +a+1) 1)
m=0
Points t t conjugate to & satisfy h(t) = O, which results in the identity D1 ( Ji(B (VB t.). Remarkably, this condition does not depend on C, but only on t and
on the sharpness 3. Let us now fix these parameters and name K8,t Vv3 t/) (vB t)).
Points conjugate to t then satisfy Vi(33 expansions (Watson] 1995), also used by Su et al. (0166)
Ka.t, JIVB t). We now recall the following
3R
( x )
2 m
3
(x) = π
cos
x
J (x)
V
sin
T
+
4
(12)
Since Ji and Vi asymptotically oscillate around zero and are out of synch (T (T/2 difference in phase), for t big enough the condition Y1 (V3 t) Kg Ji (vB t) is going to be satisfied. Further, this condition is going to be satisfied for a smaller value for if 3 is increased, as confirmed by Figure 2
Theorem 5 (Local optimality of Nesterov with vanishing damping). Let f: RRd - R be conver quadratic, and let X : + Rd be solution to the ODE X + 5 VX() = 0. For 0 < t < tz
consider the action functional J[Y] St2 L(Y, Y, ,f)dt, mapping E C² number. Then, if [/2 41] is small enough, there are no points conjugate to t and Nesterov's 's path minimizes J over all curves such that ((,) ((1) and (12) = X(2)). The length of the optimality interval It2 t1 shrinks as B, the maximum eigenvalue of the Hessian of f. increases.
to a real
Proof. The argument presented in this section can be lifted to the multidimensional case. Indeed, since the dynamics in phase space is linear, it's geometry is invariant to rotations and we can therefore assume the Hessian diagonal. Next, Jacobi's equation has to be solved coordinate-wist which leads to logical AND between conjugacy conditions. By the arguments above, the dominating condition is the one relative to the maximum eigenvalue 3.
The following corollary shows that Nesterov's path actually becomes suboptimal if the considered time interval is big enough. This is also verified numerically in Figure I
Symbolic computations are checked in Maple/Mathematica, numerical simulations are performed in Matlab.
5

---

Corollary 6 (Nesterov with vanishing damping is not globally optimal). In the settings of Thm. 5 for It- -t ti big enough, Nesterov's path becomes a saddle point for J.
Proof. Non-existence of conjugate points is necessary and sufficient for minimality/maximaliiy
In the next subsection, we provide constructive proof for Cor. 6 which allows us to derive concrete bound for It2 - l In particular, we show in Prop. that, for the case of vanishing damping 3/ Nesterov's path is always a saddle point for the action if Ito - t1l v /40/B.
Optimality for the special case ((t2) = x=" Some readers might have already realized that Jacobi's equation Eq. 49) in the quadratic po- tential case is itself the solution of Nesterov's s ODE. This means that, 1 R O, the first time conjugate to ( is exactly when Nesterov's puth reaches the minimizer. Hence - only in the one-dimensional case it is actually true that, we do not consider arbitrary time intervals but only the first interval before the solution first touches the optimizer, Nesterov's path always minimizes the action. Sadly, this strong and interesting result is not valid in higher dimensions, since Nesterov's s path in general never actually crosses the minimizer in finite time?" [
Nesterov poth (daaping 3/1)
(
18 xx(0)l2
Remark on dropping boundary conditions. The results in this section are formulated for the fixed boundaries case Y (ti) (ti) and Y (t2) = (f2)) where X the solution to Nesterov's ODE, From an optimization viewpoint, this requirement seems strong. Ideally, we would want (t2) be any point close to the minimizer (say inside an c-ball). A simple reasoning proves that Nesterov's 's path can be a saddle point for the action also in this case. By contradiction, assume Nesterov's trajectory minimizes the action among all curves that reach any point inside a small e-ball at time 22. Then, Nesterov's s path also minimizes the action in the (smaller) space of curves that reach exactly X (12). By Cor. 6 this leads to a contradiction if (2 is big enough.
3.2 A constructive proof of Nesterov's suboptimality in the quadratic setting
We now present direct computation, to shed some light on the suboptimality of Nesterov's path in the context of Thm. In the setting of Sec. 3.1 the second variation of J along is 1/2 1 +²(h(t)²- 3h(t) (dt,, independent of y. Consider now the finite-nomi norm perturbation (vanishing at boundary):
I c - or 2
(t)
t E c,
CE (t1,),)), < min(c - 4,,12 c).
(13)
1 LE (c)
This is triangular function with support (c (c-c, c, c) and height one. Let he,c be a C² modification of he,c such that llhe,e- - he,ell negligible For any scaling factor o > O,
(libha for o (0.30), 8-2
3. + (Be² 3)²² 3c²) c
82 Ja he.)) =
10
(14)
3e
The denominator is always positive. Hence, we just need to study the sign of the numerator, with respect to changes in
0 and c > 0. Consider for now e fixed, then the zeros of the numerator are (15 5u + /25u² 60u + 225)/(33)))) with u == Bcc.. Since 25u² 60u + 225 for all u 2 0. the solution has two real roots. However, only one root 2. (u. .3) is admissible, since the smallest one is always negative As result, for fixed e > 0, 82 (aJ(hhe,c)) changes sign only at c,( Note that 2. (u. 3) decreasing as a function of and (2, 3) = 10/ 3 as well as lim =_ [,, 3) 3/3. Therefore, for any e, 3 > 0, we showed that 82 (arhee)) changes sign when c, 1/3/B, / 10/ (). If choosing
*The first crossing time in each direction depends on the sharpness in each direction, hence hy the time cach coordinate reaches zero, we alrcady have conjugate point.
9 Standard technique in calculus of variation, see e.g. proof Legendre's Thm Gelfand and Fomin 2000 1ff u > O, then 15- 5u / 225 60u + 225- < 0.

---

e big is allowed by the considered interval (he,c has to vanish at f1, t2), then the second variation is
indefinite. This happens if It- ti > 2e,. By taking o + O, we get the following result.
Proposition (Sufficient condition for saddle). The second variation of the action of Nesterov's 's Lagrangian (damping 3/t) on f(x) = 3x²² /2 is an indefinite quadratic form | - t1l v 40/ B. This result generalizes to 3-smooth multidimensional convex quadratics.
We remark that the inverse dependency on the square root of 3 is also predicted by the general proof in Sec. 3.1 where the argument of the Bessel functions is always t/B.
3.3 Unboundedness of the action for large integration intervals (from above and below)
In Prop. 7 we showed that for big enough integration intervals, Nesterov's 's method with damping 3/1 on f(z) 3z² /2 saddle point for the action. This suggests that the action itself unbounded both from above and below. It is easy to show this formally.
Proposition 8 (Unboundedness of the action). Let L be Lagrangian of Nesterov's 's method with damping 3/t on 3-smooth convex quadratic and J[Y] St2 L(Y, Y, t]dt. Let a, b be two arbitrary vectors in RRd. There exists a sequence of curves (Yk)seN, with Y2 E (it,, t2], t2), and (t1) = a, (xt) b for all & E N, such that J [(,]] & co. In addition, It - t1 v 40/3 there exists another sequence with the same properties diverging to -00
Proof. The proof is based on the computation performed for Prop. 7 Crucially, note that for the
quadratic loss function case we have 8².J = J. For the case a = b = 0, we showed that for any interval [2), by picking e small enough, we have J (hh,,e) = 6 (h,,e) > 0 (also illustrated in the figure supporting the proof). Hence, J(,r-he.)) - +o0 as o - co. Same argument holds for -co in the large interval case. This proves the assertion for a = b O. Note that the curves corresponding to the diverging sequences can be modified to start/end at any a, b E IRd at the price of bounded error in the action. This does not modify the behavior in the limit; hence, the result follows.
3.4 Optimality of Nesterov with vanishing damping if curvature vanishes (polynomial loss)
Note that the bound on It. - t1l in Prop. 7 gets loose as 3 decreases. This is also predicted by the argument with Bessel functions in Sec. 3.T and clear from the simulation in Fig. 2 As a result, as curvature vanishes, Nesterov's path becomes optimal for larger and larger time intervals. This setting is well described by polynomial losses f(x) x (x==")² with p > 2. As Nesterov's 's path approaches the minimizer x", the eurvature vanishes; hence, for every 3 > 0 there exists time interval (t1, 2o) where the curvature along Nesterov's 's path is less then B. This suggest that, for losses with vanishing curvature at the solution, there exists time interval (4., oo) where Nesterov's path is actually minimizer for the action. While this claim is intuitive, it is extremely hard to prove formally since in this case the second variation of J depends on the actual solution of Nesterov's 's equations for which no closed-form formula is known in the polynomial case (Su et al. 2016).
However, we also note that the vanishing sharpness setting is only interesting from theoretical perspective. Indeed, regularized machine learning objectives do not have this property. Actually, in the deep neural network setting, it is known that the sharpness (maximum eig. of the Hessian) actually increases overtime (Yao et al., 2020 Cohen et al. (02T). Hence, it is safe to claim that the machine learning setting Nesterov's 's path is only optimal for small time intervals, as shown in Thm.
4 Analysis of the action of Nesterov's path with constant damping a
In the p-stroonly convex case is well known that constant damping = 2// yields acceleration compared gradient descent This choice completely changes the geometry of Nesterov's path and needs a separate discussion.
The corresponding Lagrangian is
La (Y,Y,1)= = att ( (111P--
(15)
11 Hessian eigenvalues lower bounded by μ > O. The corresponding rate is linear and depends on v Vp/B. as opposed to p/8 (GD case).
7

---

Again, we consider the quadratic function f(x) fx² /2 and examine Jacobi's ODE h(t) + ah(t) -
3h(t) O. We have to determine whether there exists a non-trivial solution such that h(t))
(1222) 0 and h(t) vanishes also at point /. E (41 f2), the conjugate point.
For the critical damping case a 2 the general solution such that ((t2) 0 is
h(t) = Ce v t1).
(16)
There is no non-trivial solution h that vanishes also at E (t1, 12) conjugate points. The same holds for the overdamping case a > 2/3, where the solution that vanishes at 1 is
h(t) = Ce - c ( - evvo= -3
(17)
For the underdamping case < 3. the picture gets more similar the vanishing damping case (Sec 3.1b. The solution under h((4) 0 is
1(11) = Ce 4 sin /4 - a²
tan <4BB - a² h
V48 a² (VA5-a2))
cos
(18)
2
2
2
43 a² for h E N. Therefore for any t2 t + 2T/ V 43 a² there exists a conjugate point E (21,
Hence all points > i conjugate to i satisfy & = (1 + 2kT / /43
Theorem 9 (Global optimality of overdamped Nesterov, suboptimality of accelerated Nesterov). Let f Idd + R be strongly convex quadratic, and let X R + Rd be solution to the ODE 0. For 0 S t2, consider the action J[Y] Se LY,YY, t)dt. If a 2 2/B, where B is the max. eigenvalue of the Hessian of f. then Nesterov's path minimizes J over all curves s.t. ((t)) = X(1)) and (t2) (t2)). Else (e.g. acceleration setting a z 2/Pp).
X + ax Vx())
Nesterov's path is optimal only for It2 t1l S 2n/ 43 a² and otherwise is a saddle point.
Proof. As for the proof of Thm. 5 the condition conjugate points has to hold for each eigendirec- tion separately. We conclude by noting that eigenvalues are in the range [ja, B]. For the underdamping case, we give a concrete example for a nature. Consider the finite-norm perturbation h(t) = sin(ko(t t/)/(tt tz)), where k E N. Then,
1, show the saddle point
( (t2 t1 (4k2 + (to 21)²)
( (k2e-(te (t2 (12-t)) ( 1)(2k² - (t2 -
Jb)( = 02c221
(19)
Hence, for any 1o t /2kT, it holds that 82 (hlhh))) <.
Extending the optimality claims to t2 = 00 with r-convergence. From an optimization view- point, the most interesting setting is to study the action over the complete trajectory, i.c. consider E C(t, oo), Rd) such that ((t)) = X X(f1) and ((x) = x². a minimizer. Prop. 7 and Thm. 9 show that the question of optimality in this case deserves discussion only in the extremely over- damped case 2 2/3, where minimality is guaranteed for any time interval. A careful study of the infinite-time setting would require the theory of T-convergence (Braides al., 2002). The usual pipeline consists in defining a sequence of problems Jk. on intervals [2. with 122 + co as + XC Under the assumption that each Js admits a global minimizer (only true for the overdamped case), one can study convergence of J = min[J&[Y]] Y E C² ([11,,]) (,,, R) to J = (Y) Y E (2 x)), Rd)). While existence of J and Joc is not trivial in general, for our setting the pipeline directly yields minimality of overdamped Nesterov's path until co.
Discussion of the main findings and directions for future research
In this section, we summarize the results of Sec. & and discuss some implications that our analysis delivers on the geometry of accelerated flows in the convex and strongly convex setting.
We summarize below the main high-level findings of our theoretical analysis:
1. The optimality of Nesterov's 's path for minimization of the action corresponding to the Bregman Lagrangian is strictly linked to the curvature around the minimizer reached by the flow.
8

---

2. As the maximal curvature 8 increases, it gets increasingly difficult for accelerated flows to minimize the action over long integration intervals: both the accelcrated ODEs X + 3/txX - are optimal only for intervals of length x 1/vB.
v V((X) 0 and X + 2/TUX ( =
3. If Nesterov's ' path does not minimize the action, there does not exist a "better" (through the eyes of the action) algorithm, as the functional gets unbounded from below (Sec. 3.3
4. This suboptimality is due precisely to the oscillations in the accelerated paths. In contrast, long as each coordinate in parameter space decreases monotonically (as it is the case for gradient descent), Nesterov's 's path is optimal. See also O'donoghue and Candes (2013).
5. Hence, Nesterov's 's method with very high damping o 2vB which does not oscillate and hence does not lead to acceleration (see Fig. 3
minimizes the action.
In nutshell, locally Nesterov's 's method does indeed optimize functional over curves. However, this property breaks down precisely when the geometry gets interesting - i.e. when the loss evolution is non-monotonic. Since acceleration is a global phenomenon, i.e. is the cumulative result of many consecutive oscillations (see Fig. 3. our results suggest that the essence of acceleration cannot be possibly captured by the minimization of the action relative to the Bregman Lugrangian.
[(X(0))
Gradiint Flow
Noodarus Flowr (dimping 2v(T)
Nastezov Flow (dampins
Non-uniqueness of the Lagrangian. A possible reason for the non-optimality of Nesterov's ' path is, simply put - that we are not looking at the right action functional. Indeed, there are many Lagrangians that can generate Nesterov ODE. Let F(Y,t) t) be any function which does not involve the velocity, then it is easy to see that the Lagrangian L is equivalent to
Nosezov Flow (damaping 2/()
Figure 3: Optimization of potential
[(x, 3) 0.02z 2 + 0.0004y² where 2e = 3 >> μ = 3e 4. Non- monotonic trajectories (i.e. the acceler- ated curves) minimize the action only for short time intervals. Simulation with Munge-Kutta 4 integration.
i(YYY,1) Y,) + Y OF
OY (x.0)
OF
(X,
(20)
This simple fact opens up new possibilities for analyzing and interpreting Nesterov's 's method using different functionals - which perhaps have both a more intuitive form and better properties.
Higher order ODEs. On a similar note, could be possible to convexify the action functional by considering a logical OR between symmetric ODEs, e.g zيz + a + B) mzz a + 3) = 0.
Such tricks are often used in the literature on dissipative systems (Szegleti and Márkus 2020).
Noether Theorem. In physics, the variational framework is actually never used to claim the minimality of the solution the equations of motion. Its power relies almost completely in the celebrated Noether's Theorem (Noether 1918), which laid the foundations for modern quantum field theory by linking the symmetries in the Lagrangian (and of the Hamiltonian) the invariances in the dynamics. Crucially, for the application of Noether's Theorem, one only needs the ODE to yield a stationary point for the action (also saddle points work). Coincidentally, while finalizing this manuscript, two preprints (Tanaka and Kunin 2021 Gtuch and Urbanke, (021]) came out on some implications of Noether's Theorem for optimization. However, we note that these works do not discuss the direct link between Noether's s Theorem and acceleration, but instead study the interaction between the symmetries in neural network landscapes and optimizers. While some preliminary implications of Noether's 's theorem for time-rescaling of accelerated flows are discussed in (Wibisono) jtt al. 2016),, we suspect that a more in-depth study could lead, combination with recent work on the Hamiltonian formalism (Diakonikolas and Jordan 2019), to substantial insights on the hidden invariances accelerated paths. We note that finding these invariances might not be an easy task, and requires dedicated work: indeed, even for simple linear damped harmonic oscillators (constant damping), invariance in the dynamics can be quite complex (Choudhuri et al. 2008).
Conclusion
We provided an in-depth theoretical analysis of Nesterov's 's method from the perspective of calculus of variations, and showed that accelerated paths only minimize the action of the Bregman Lagrangian locally. This suggests that further research is needed for understanding the underlying principle of generation for acceleration - which has been an open question in optimization for almost 40 years (Nesterov) 1983). To this end, we proposed few concrete directions for future work.

---

Acknowledgments and Disclosure of Funding
The authors thank Prof. Luca Martinazzi for his helpful discussions. This work was partially funded in part by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d' d'avenir" program, reference ANR-19-P3LA 100-199-3A-0000PPRRAA (PRRARE 31A Institute). Hadi Daneshmand acknowledges support from the European Research Council (grant SEQUOIA 724063).
References
Ahn, K. (2020). From proximal point method Nesterov's acceleration. arXiv preprint.
Alimisis, F., Orvieto, A., Bécigneul, G., and Lucchi, A. (2020). A continuous-time perspective for modeling acceleration in Riemannian optimization. In AISTATS.
Allen-Zhu, Z. and Orecchia, L. (2014). Linear coupling: An ultimate unification of gradient and mirror descent. arXiv preprint.
Amari, S.-i. (2016). Information geometry and its applications, volume 194. Springer.
Aroo'd, V. I. (2013). Mathematical methods of classical mechanics, volume 60. Springer Science & Business Media.
Braides, et (2002). Ganma-convergence for Beginners, volume 22. Clarendon Press.
Bregman, L. M. (1967). The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics, 7(3):200-217.
Casgrain, P. (2019). A latent variational framework for stochastic optimization. In Advances in Neural Information Processing Systems, pages 5647-5657.
Choudhuri, A., Ghosh, S., and Talukdar, (2008). Symmetries and conservation laws of the damped harmonic oscillator. Pramana, 70(4):657-667.
Cohen, J. M., Kaur, S., Li, Y., Kolter, J. Z., and Talwalkar, A. (2021). Gradient descent on neural networks typically occurs the edge of stability. arXiv preprint.
Defazio, (2019). On the curved geometry of accelerated optimization. Advances in Neural Information Processing Systems, 12:1766-1775.
Diakonikolas, J. and Jordan, M. I. (2019). Generalized momentum- based methods: A Hamiltonian perspective. arXiv preprint.
Duruisseaux, V. and Leok, M. (2021). A variational formulation of accelerated optimization on Riemannian manifolds. arXiv preprint.
França, G., Jordan, M. I., and Vidal, R. (2021). On dissipative symplectic integration with applica- tions to gradient-basee based optimization. Journal of Statistical Mechanics: Theory and Experiment, 24)444024
Gelfand, I. and Fomin, S. (2000). Calculus of (triationsstraasslatedd and edited by Silverman, RA).
Gluch, G. and Urbanke, R. (2021). Noether: The more things change, the more stay the same. arXiv preprint.
Jordan, M. (2018). Dynamical, symplectic and stochastic perspectives on gradient-based optimiza- tion. University of California, Berkeley.
Krichene, W., Bayen, A., and Bartlett, P. L. (2015). Accelerated mirror descent in continuous and discrete time. Cortes, C., Lawrence, N. D., Lee, D. D., Sugiyama, M., and Garnett, R., editors, Advances in Neural Information Processing Systems 28, pages 2845 2853. Curran Associates, Inc.
Landau, L. D. and Lifshitz, E. M. (1976). Mechanics: Volume 1, volume 1. Butterworth- -eioorthhh-iimmam....
10

---

Muehlebach, M. and Jordan, M. I. (2021). Optimization with momentum: Dynamical, control- theoretic, and symplectic perspectives. Journal of Machine Learning Research, 22(73):1-50.
Nemirovskii, A. and Yudin, D. (1983), Problem Complexity and Method Efficiency in Optimization. A Wiley-Interscience publication. Wiley.
Nesterov, Y. E. (1983). A method for solving the convex programming problem with convergence rate )../k²). In Dokl. akad. nauk Sssr, volume 269, pages 543-547.
Noether, E. (1918). Invariante variationssprobleme Nachrichten von der Gesellschaft der Wis- senschaften zu Göttingen, cetthhemmattcc---yysaaliiie Klasse, 1918:235-257.
O'donoghue, and Candes, E. (2015). Adaptive restart for accelerated gradient schemes. Founda- tions of computational mathematics, 15(3):15--73.
Su. W., Boyd, S., and Candès, E. J. (2016). A differential equation for modeling Nesterov's s accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 17(153):1-43,
Szegleti, A. and Márkus, F. (2020). Dissipation in Lagrangian formalism. Entropy, 22(9):930.
Tanaka, H. and Kunin, D. (2021). Noether's learning dynamics: The role of kinetic symmetry breaking in deep learning. arXiv preprint.
Watson, G. N. (1995). A treatise on the theory of Bessel functions. Cambridge university press.
Wibisono, A., Wilson, C., and Jordan, M. I. (2016). variational perspective on accelerated methods in optimization. proceedings of the National Academy of Sciences, 113(4)):53351-6735
Wilson, A. C., Mackey, L., and Wibisono, A. (2019). Accelerating rescaled gradient descent: Fast optimization of smooth functions. In Advances in Neural Information Processing Systems, pages 13533-13543.
Xu, Wang, T., and Gu, Q (2018). Accelerated stochastic mirror descent: From continuous-time dynamics to discrete-time algorithms. In International Conference on Artificial Intellignce and Statistics, pages 1087-1096.
Yao, Z., Gholami, A.. Keutzer, K., and Mahoney, M. W. (2020). Pyhessian: Neural networks through the lens of the Hessian. In 2020 IEEE International Conference on Big Data (Big Data), pages 581-590. IEEE.


Reviews:
[{"review_id": "kUD3IWB3CsE", "reviewer": "Reviewer_buiE", "summary": "This paper considers Nesterov’s accelerated method from a novel perspective and sheds lights onto its variational interpretation. This paper reads really well and opens further avenues for understanding the acceleration phenomenon.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper starts from an observation that optimality of the Nesterov’s method has not been rigorously demonstrated in previous works. This is an important issue, as if the Nesterov’s method (and other accelerated methods) does not minimise the proposed action functionals, then their interpretation becomes unclear. This paper does a good job explaining this and even proposing some alternative action functionals that would give rise to the Nesterov’s method.\n\nWhile I haven’t checked the proofs (as they go beyond my knowledge of this area), I found the paper as an insightful read and an important contribution to the area.\n\n1) Can authors expand on the comments that the action functional is not unique - therefore, it is possible to get more intuitive action functionals for improving the understanding of accelerated methods? Is there an action functional where the Nesterov arises as the optimal?\n\n2) Also can authors clarify what is the use and advantage of convexifying the action functional? What kind of properties and advantages does it bring in terms of interpreting acceleration or developing new accelerated methods?\n\n3) I believe that the small paragraph written about Noether Theorem wasn’t clear. Actually, it wasn’t possible to understand how it relates to the rest of the work and why it is written. It would be good to clarify.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "UhJO7kGC87k", "reviewer": "Reviewer_7bjp", "summary": "The Lagrangian variational characterization of continuous time trajectories that converge to the global minimum of a convex objective function at a rate faster that $O(1/t)$ is an area of active research, and this paper addresses the question of whether the Euler-Lagrange trajectories induced by the Bregman Lagrangian are minimizers of the action integral. This question is motivated by a statement made in Michael Jordan's 2018 ICM proceedings paper, which alludes to the trajectories optimizing (as opposed to extremizing) the action integral.\n\nThe main contributions of the paper are as follows:\n\n1. Proving that the action integral is a minimum only for sufficiently small time intervals (Theorem 5), which appears to be a consequence of the well known result in the calculus of variations that local coercivity induces local minimum.\n2. Constructively proving that the action for the Nesterov trajectory is suboptimal in the quadratic setting (Proposition 7).\n3. A proof that the overdamped Nesterov trajectory minimizes the action integral for arbitrarily long time intervals, whereas the accelerated Nesterov trajectory is a saddle (Theorem 9).\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The Lagrangian variational characterization of continuous time trajectories that converge to the global minimum of a convex objective function at a rate faster that $O(1/t)$ is an area of active research, and this paper addresses the question of whether the Euler-Lagrange trajectories induced by the Bregman Lagrangian are minimizers of the action integral. This question is motivated by a statement made in Michael Jordan's 2018 ICM proceedings paper, which alludes to the trajectories optimizing (as opposed to extremizing) the action integral.\n\nThe main contributions of the paper are as follows:\n\n1. Proving that the action integral is a minimum only for sufficiently small time intervals (Theorem 5), which appears to be a consequence of the well known result in the calculus of variations that local coercivity induces local minimum.\n2. Constructively proving that the action for the Nesterov trajectory is suboptimal in the quadratic setting (Proposition 7).\n3. A proof that the overdamped Nesterov trajectory minimizes the action integral for arbitrarily long time intervals, whereas the accelerated Nesterov trajectory is a saddle (Theorem 9).\n\nThe proofs appear to be sound, but nothing in the Lagrangian variational approach to mechanics necessitates that the action integral is a minimizer (as opposed to extremizer) over arbitrarily long time intervals, so the fact that the Nesterov accelerated trajectory is generally a saddle point as opposed to minimizer of the action integral is hardly surprising or noteworthy. In honesty, I think the paper under consideration is fixating on a misstatement that has never served as the theoretical justification for the variational approach to accelerated optimization, which is why this issue has never really been studied rigorously.\n\nThere is nothing technically wrong with the results in the paper, but the underlying motivation for the paper appears to be somewhat misguided. In particular, for the paper to be truly significant, I would like the authors to point out instances in which the variational approach to accelerated optimization relies critically on the incorrect assumption that the action integral is minimized as opposed to being extremized.\n\nSome additional comments: Since Theorems 1-4 are well known in the calculus of variations, and are presented without proof, the authors should cite a reference for these results.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "PaIcR1VUg7H", "reviewer": "Reviewer_XNyg", "summary": "The authors try to understand the low-resolution ODE for Nesterov accelerated gradient descent in convex case from the variational perspective. Meanwhile, they find the ODE is not the minimizer of the action functional, but the saddle. From mathematical perspective, it is a new and novel point to investigate. ", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The topic in this paper is very interesting. Understanding the Nesterov' method from continuous perspective is a very attractive topic. But the content is so few that it is hard to persuade the readers the framework makes sense, such as how about other ODEs and high-resolution ODEs in (Understanding the Acceleration Phenomenon via High-Resolution Differential Equations). Moreover, the purpose of the authors to investigate the low-resolution ODE is not clear for readers, which looks to start from a pure mathematical view. If yes, please show more results about all related ODEs; if no, please show more motivation. The quality is not enough. Furthermore, the authors need to show significance of this paper. Finally, if the authors can show more convince, I would like to change my grade.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper needs to show more convince. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "25"}, "extra_text": {}}, {"review_id": "HUaqQ2D7zeX", "reviewer": "Reviewer_4GWq", "summary": "In prior work, Su et al. (2016) introduced a continuous-time modelling of Nesterov's accelerated gradient descent (AGD) and analyzed its property. Wibisono et al. (2016) introduced the Bregman Lagrangian, which obtains Su et al.'s acceleration ODE via the principle of \"least action\" and establishes the connection of AGD with classical Lagrangian and Hamiltonian mechanics of mathematics physics. In this work, the authors point out an (in my view) significant misconception that the acceleration ODE arises from a \"least action\" path; rather, it is merely a stationary point. ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors provide the first rigorous study of the action relative to Bregman Lagrangian and characterize (the non) minimality of Neterov's path. The clarity of this paper is good. I enjoyed reading the paper and learned a good deal from the discussion of prior work. The misconception that the authors point out is one that I also held myself, so I am glad to be corrected. I am also under the impression that the original authors of the Bregman Lagrangian work shared this misconception, so I imagine this work will serve to prevent the misconception from being propagated by them as well.\n\nHowever, after reading the paper, I am left with the feeling of \"so what\"? This work provides a valuable correction on how we interpret the prior analyses, but it doesn't invalidate any of the prior concrete results nor immediately inform us of what to do differently. The authors mention that the power of the variational framework lies almost completely in Noether Theorem. Perhaps fleshing this out would lead to, I suspect, a really interesting line of work. However, the paper, as is, I feel does not contain enough interesting content to be published at NeurIPS.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper discusses a misconception (or implicit assumption) from some popular recent work that links Nesterov acceleration to continuous time equations.  There was a very robust discussion between the reviewers and author(s), and also privately among the reviewers.  We also solicited an extra review, and the AC and SAC had involved discussions.

Generally, the reviewers liked the paper, and there were no fatal flaws or mistakes.  The writing is nice, and it's certainly not a hostile paper.  The main argument against accepting the paper is that it is not clear the misconception has led to incorrect research, and it's also not clear how influential the original arguments have been.

However, the paper offers more than just pointing out the misconception (it discusses regimes where Nesterov's method is optimal) and makes some nice connections.  It's an enjoyable read, and useful to anyone interested in modern optimization. Furthermore, the original misconception had been repeated in high-profile venues (like a plenary talk at the ICM).  While it's not certain that this paper is currently needed in order to fix state-of-the-art research, this paper does contribute to the literature and may be useful in the future.

Overall, this is a nice paper, and has a chance of making an impact, hence we're pleased to suggest its acceptance.
Decision: Accept (Poster)