Rethinking the Variational Interpretation of Accelerated Optimization Methods
Year: 2022

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.

heading: 1 Introduction
text: This paper focuses on the problem of unconstrained convex optimization, i.e. to find x∗ ∈ arg min
x∈Rd f(x), (P)
for some lower bounded convex L-smooth2 loss f ∈ C1(Rd,R). Nesterov’s acceleration. Nemirovskii and Yudin (1983) showed that no gradient-based optimizer can converge to a solution of (P) faster than O(k−2), where k is the number of gradient evaluations3. While Gradient Descent (GD) converges like O(k−1), the optimal rate O(k−2) is achieved by the celebrated Accelerated Gradient Descent (AGD) method, proposed by Nesterov (1983):
xk+1 = yk − η∇f (yk) , with yk = xk + k − 1 k + 2 (xk − xk−1). (AGD)
The intuition behind Nesterov’s method and the fundamental reason behind acceleration is, to 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. (2016) made an interesting observation: the convergence rate gap between GD and AGD is retained in the continuoustime limits (as the step-size η vanishes):
Ẋ +∇f(X) = 0 (GD-ODE), Ẍ + 3 t Ẋ +∇f(X) = 0 (AGD-ODE)
∗Equal Contribution. 2A differentiable function f : Rd → R is said to be β-smooth if it has β-Lipschitz gradients. 3This lower bound holds just for k < d hence it is only interesting in the high-dimensional setting.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
where Ẋ := dX/dt denotes the time derivative (velocity) and Ẍ := d2X/dt2 the acceleration. Namely, we have that GD-ODE converges like O(t−1) and AGD-ODE like O(t−2), where t > 0 is the time variable. This seminal paper gave researchers a 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., 2016; Wilson et al., 2019), in the stochastic setting (Krichene et al., 2015; Xu et al., 2018) 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̇, t) = t3 ( 1
2 ‖Ẋ‖2 − f(X)
) . (1)
Indeed, the Euler-Lagrange equation
d
dt
( ∂
∂Ẋ L(X, Ẋ, t)
) = ∂
∂X L(X, Ẋ, t) (2)
reduces in this case to t3Ẍ + 3t2Ẋ + t3∇f(X) = 0, which is equivalent to 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 x and y is measured by means of the Bregman Divergence (Bregman, 1967) Dψ(x, y) = ψ(y)− ψ(x)− 〈∇ψ(x), y − x〉, where ψ : Rd → R is a strictly convex and continuously differentiable function (see e.g. Chapter 1.3.2 in Amari (2016)). Namely, they introduced the so-called Bregman Lagrangian:
Lα,β,γ(X, Ẋ, t) = e α(t)+γ(t) ( Dψ(X + e −α(t)V,X)− eβ(t)f(X) ) , (3)
where α, β, γ are continuously differentiable functions of time. The Euler-Lagrange equations imply Ẍ + (eα(t) − α̇(t))Ẋ + e2α(t)+β(t) [ ∇2ψ(X + e−α(t)Ẋ) ]−1 ∇f(X) = 0. (4)
The main result of Wibisono et al. (2016) is that, under the ideal-scaling conditions β̇(t) ≤ eα(t) and γ̇(t) = eα(t), any solution to Eq. (4) converges to a solution of (P) at the rate O(e−β(t)). Under the choice ψ(x) = 12‖x‖ 2 2, we get back to the Euclidean metric Dψ(x, y) = 1 2‖x− y‖ 2 2. Moreover, choosing α(t) = log(2/t), β(t) = γ(t) = 2 log(t), we recover the original Lagrangian in Eq. (1) and O(e−β(t)) = O(t−2), as derived in Su et al. (2016). Impact of the variational formulation. The variational formulation in Wibisono et al. (2016) has had a 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 to optimize?”. Imprecise implications of the variational formulation. While the 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, it minimizes the action functional ∫ t2 t1 Lα,β,γ(Y, Ẏ , t)dt over the space of curves by the minimum action principle of classical mechanics (Arnol’d, 2013). This claim4 is inaccurate. Indeed, the term minimum action principle is misleading5: solving Euler-Lagrange
4Paragraph 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-integrated Bregman Lagrangian”.
5From 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 a given mechanical system will not be required to minimize the action but only to cause its first variation to vanish.”
only makes the action stationary (necessary condition: vanishing first-order derivative), but does not guarantee minimality — this only holds in physics for very special cases6, which do not include even simple mechanical systems like the pendulum (proof in Section 36.2 of Gelfand and Fomin (2000)). Indeed, from a 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-depth 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 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
et al. (2016) on multidimensional quadratic losses. By using Jacobi’s theory for the second variation (summarized in Sec. 2), we find that Nesterov’s path is optimal only if the integration interval [t1, t2] is small enough. In contrast, if t2 − t1 > √ 40/β (β is Lipschitz constant for
the gradient), Nesterov’s path is actually a saddle point for the action (see Fig. 1). 2. In Sec. 4 we extend the analysis to the µ-strongly convex setting and thus consider a constant
damping α. We show that, for extremely overdamped Nesterov flows (α ≥ 2 √ β), i.e for highly suboptimal parameter tuning (acceleration holds only for α ≈ 2√µ), Nesterov’s path is always a minimizer for the action. In contrast, we show that for α < 2 √ β (acceleration setting), if t2 − t1 > 2π/ √
4β − α, Nesterov’s path is again a saddle point for the action. 3. In Sec. 5 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; Arnol’d, 2013; Gelfand and Fomin, 2000).

heading: 2 Background on calculus of variations
text: We work on the vector space of curves C1([t1, t2],Rd) with t1, t2 ∈ [0,∞). We equip this space with the standard norm ‖Y ‖ = maxt1≤t≤t2 ‖Y (t)‖2 + maxt1≤t≤t2 ‖Ẏ (t)‖2. Under this choice, for any regular Lagrangian L, the action functional J [Y ] := ∫ t2 t1 L(Y, Ẏ , t)dt is continuous. First variation. Let D be the linear subspace of continuously differentiable displacements curves h such that h(t1) = h(t2) = 0. The corresponding increment of J at Y along h is defined as ∆J [Y ;h] := J [Y + h]− J [Y ]. Suppose that we can write ∆J [Y ;h] = ϕ[Y ;h] + ‖h‖, where ϕ is linear in h and → 0 as ‖h‖ → 0. Then, J is said to be differentiable at Y and the linear functional δJ [Y ; ·] : D → R such that δJ [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 is unique.
Extrema. J is said to have an extremum at Y if ∃δ > 0 such that, ∀h ∈ D with ‖h‖ ≤ δ, the sign of J [Y + h]− J [Y ] is constant. A necessary condition for J to have an extremum at Y is that
δJ [Y ;h] = 0, for all h ∈ D. (5) 6e.g. free particle in vanishing potentials, or t1 ≈ t2, see Remark 2 at the end of Section 21 and Section 36.2.
We proceed with stating one of the most well-known results in calculus of variations, which follows by using Taylor’s theorem on J [Y ] = ∫ t2 t1 L(Y, Ẏ , t) dt. Theorem 1 (Euler-Lagrange equation). A necessary condition for the curve Y ∈ C1([t1, t2],Rd) to be an extremum for J (w.r.t. D) is that it satisfies the Euler-Lagrange equations (2).
It is crucial to note that Theorem 1 provides a necessary, but not sufficient condition for an extremum — indeed, the next paragraph is completely dedicated to this.
Second Variation. Thm. 1 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 ∆J [Y ;h] = ϕ1[Y ;h] + ϕ2[Y ;h] + ‖h‖2, where ϕ1 is linear in h, ϕ2 is quadratic in h and → 0 as ‖h‖ → 0. Then J is said to be twice differentiable and the functional δ2J [Y :, ·] : D → R s.t. δ2J [Y, h] := ϕ2[Y ;h] is called the second variation of J at Y . Uniqueness of second variation is proved in the same way as the first variation. Theorem 2. A necessary condition for the curve Y ∈ C1([t1, t2],Rd) to be a local minimum for J (w.r.t D) is that it satisfies δ2J [Y ;h] ≥ 0. For local maxima, the sign is flipped.
Jacobi equations. Recall that J [Y ] = ∫ t2 t1 L(Y, Ẏ , t)dt. Using the notation LY Z = ∂2L/(∂Y ∂Z), the Taylor expansion for ∆J [Y ;h] = J [Y + h]− J [Y ] if ‖h‖ → 0 converges to
∆J [Y ;h] = ∫ t2 t1 ( LY h+ LẎ ḣ ) dt+ 1 2 ∫ t2 t1 ( LY Y h 2 + LẎ Ẏ ḣ 2 + 2LY Ẏ hḣ ) dt, (6)
where the equality holds coordinate-wise. Therefore, δJ [Y ;h] = ∫ t2 t1 ( LY h+ LẎ ḣ ) dt and
δ2J [Y ;h] = 1
2 ∫ t2 t1 ( LY Y h 2 + 2LY Ẏ hḣ+ LẎ Ẏ ḣ 2 ) dt
= 1
2 ∫ t2 t1 ( LY Y − d dt LY Ẏ ) h2dt+ 1 2 ∫ t2 t1 LẎ Ẏ ḣ 2dt
= 1
2 ∫ t2 t1 ( Pḣ2 +Qh2 ) dt, (7)
where P = LẎ Ẏ , Q = LY Y − d dtLY Ẏ , and the second equality follows from integration by parts since h vanishes at t1 and t2. Using this expression, it is possible to derive an easy necessary (but not sufficient) condition for minimality. Theorem 3 (Legendre’s necessary condition). A necessary condition for the curve Y to be a minimum of J is that LẎ Ẏ is positive semidefinite. Conjugate points. A crucial role in the behavior of δ2J [Y ;h] is played by the shape of the solutions to Jacobi’s differential equation ddt (Pḣ) −Qh = 0. A point t ∈ (t1, t2) is said to be conjugate to point t1 (w.r.t. J) if Jacobi’s equation admits a solution which vanishes at both t1 and t but is not identically zero. We have the following crucial result. Theorem 4 (Jacobi’s condition). Necessary and sufficient conditions for Y to be a local minimum for J are: (1) Y satiesfies the Euler-Lagrange Equation; (2) P positive definite; (3) (t1, t2) contains no points conjugate to t1.
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 a general abstract analysis in the convex quadratic case in Sec. 3.1, and then present an intuitive analytical computation in Sec. 3.2. The non-quadratic case is discussed in Sec. 3.4.

heading: 3.1 Solutions to Jacobi’s equation for the Bregman Lagrangian in the quadratic setting
text: For the sake of clarity, we start by considering the Lagrangian in Eq. (1) for the simple onedimensional case f(x) = βx2/2. We have
Q = LY Y − d
dt LY Ẏ = −βt 3, P = LẎ Ẏ = t 3. (8)
Therefore, Jacobi’s equation relative to the action functional
∫ t2
t1 L(Y, Ẏ , t)dt with t1 > 0 is
d dt (t3ḣ)− βt3h = 0. =⇒ t3ḧ+ 3t2ḣ+ βt3h = 0 =⇒ ḧ+ 3 t ḣ+ βh = 0, (9)
which is itself Nesterov’s ODE. Following the procedure outlined in Theorem 2, we now study the solutions h such that h(t1) = 0. Any solution to Eq. (9) can be written as7
h(t) = C Y1( √ β t)
t − C Y1(
√ β t1) J1( √ β t)
J1( √ β t1) t
, (10)
where C > 0 specifies the initial velocity (see Fig. 2), Jα is the Bessel function of the first kind and Yα is the Bessel function of the second kind.
Jα(x) = ∞∑ m=0
(−1)m
m! Γ(m+ α+ 1) (x 2 )2m+α , Yα(x) = Jα(x) cos(απ)− J−α(x) sin(απ) . (11)
Points t > t1 conjugate to t1 satisfy h(t) = 0, which results in the identity Y1( √ β t)/Y1( √ β t1) =
J1( √ β t)/J1( √ β t1). Remarkably, this condition does not depend on C, but only on t1 and
on the sharpness β. Let us now fix these parameters and name Kβ,t1 = Y1( √ β t1)/J1( √ β t1).
Points conjugate to t1 then satisfy Y1( √ β t) = Kβ,t1J1( √ β t). We now recall the following expansions (Watson, 1995), also used by Su et al. (2016):
J1(x) = √ 2
πx
( cos ( x− 3π
4
) +O ( 1
x
)) , Y1(x) = √ 2
πx
( sin ( x− 3π
4
) +O ( 1
x
)) .
(12) Since J1 and Y1 asymptotically oscillate around zero and are out of synch (π/2 difference in phase), for t big enough the condition Y1( √ β t) = Kβ,t1J1( √ β t) is going to be satisfied. Further, this condition is going to be satisfied for a smaller value for t if β is increased, as confirmed by Figure 2.
Theorem 5 (Local optimality of Nesterov with vanishing damping). Let f : Rd → R be a convex quadratic, and let X : R→ Rd be a solution to the ODE Ẍ + 3t Ẋ +∇f(X) = 0. For 0 < t1 < t2, consider the action functional J [Y ] = ∫ t2 t1 L(Y, Ẏ , t)dt, mapping Y ∈ C1([t1, t2],Rd), to a real number. Then, if |t2 − t1| is small enough, there are no points conjugate to t1 and Nesterov’s path minimizes J over all curves such that Y (t1) = X(t1) and Y (t2) = X(t2). The length of the optimality interval |t2 − t1| shrinks as β, the maximum eigenvalue of the Hessian of f , increases.
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 is diagonal. Next, Jacobi’s equation has to be solved coordinate-wise, which leads to a logical AND between conjugacy conditions. By the arguments above, the dominating condition is the one relative to the maximum eigenvalue β.
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 1.
7Symbolic computations are checked in Maple/Mathematica, numerical simulations are performed in Matlab.
Corollary 6 (Nesterov with vanishing damping is not globally optimal). In the settings of Thm. 5, for |t2 − t1| big enough, Nesterov’s path becomes a saddle point for J . Proof. Non-existence of conjugate points is necessary and sufficient for minimality/maximality.
In the next subsection, we provide a constructive proof for Cor. 6, which allows us to derive a concrete bound for |t2 − t1|. In particular, we show in Prop. 7 that, for the case of vanishing damping 3/t, Nesterov’s path is always a saddle point for the action if |t2 − t1| > √ 40/β.
-0.015 -0.01 -0.005 0 0.005 0.01 0.015
-0.015
-0.01
-0.005
0
0.005
0.01
0.015
0 10 20 30 40 50 -0.02
-0.01
0
0.01
0.02
0.03 0.04Optimality for the special case X(t2) = x∗. Some readers might have already realized that Jacobi’s equation Eq. (9) in the quadratic potential case is itself the solution of Nesterov’s ODE. This means that, if t1 ≈ 0, the first time conjugate to t1 is exactly when Nesterov’s path reaches the minimizer. Hence — only in the one-dimensional case — it is actually true that, if 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 path in general never actually crosses the minimizer in finite time 8. Remark on dropping boundary conditions. The results in this section are formulated for the fixed boundaries case Y (t1) = X(t1) and Y (t2) = X(t2), where X is the solution to Nesterov’s ODE. From an optimization viewpoint, this requirement seems strong. Ideally, we would want X(t2) to be any point close to the minimizer (say inside an -ball). A simple reasoning proves that Nesterov’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 -ball at time t2. Then, Nesterov’s path also minimizes the action in the (smaller) space of curves that reach exactly X(t2). By Cor. 6, this leads to a contradiction if t2 is big enough.

heading: 3.2 A constructive proof of Nesterov’s suboptimality in the quadratic setting
text: We now present a direct computation, to shed some light on the suboptimality of Nesterov’s path in the context of Thm. 5. In the setting of Sec. 3.1, the second variation of J along γ is 12 ∫ t2 t1 t3[ḣ(t)2− βh(t)2]dt, independent of γ. Consider now the finite-norm perturbation (vanishing at boundary):
h̃ ,c(t) =  0 t ≤ c− or t ≥ c+ t−c+ t ∈ (c− , c)
c+ −t t ∈ (c, c+ )
, c ∈ (t1, t2), < min(c− t1, t2 − c). (13)
This is a triangular function with support (c − , c + ) and height one. Let h ,c be a C1 modification of h̃ ,c such that ‖h̃ ,c − h ,c‖ is negligible9. For any scaling factor σ > 0,
δ2J(σ · h ,c) = −σ2
( 3β 4
10 + (βc 2 − 3) 2 − 3c2
) c
3 . (14)
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 c fixed, then the zeros of the numerator are at (15 − 5u ±√
25u2 − 60u+ 225)/(3β), with u := βc2. Since 25u2− 60u+ 225 > 0 for all u ≥ 0, the solution has two real roots. However, only one root 2∗(u, β) is admissible, since the smallest one is always negative10. As a result, for fixed c > 0, δ2J(σh ,c) changes sign only at 2∗(u, β). Note that 2 ∗(u, β) is decreasing as a function of u and 2∗(0, β) = 10/β as well as limu→∞ 2 ∗(u, β) = 3/β. Therefore,
for any c, β > 0, we showed that δ2J(σh ,c) changes sign when ∗ ∈ [ √ 3/β, √ 10/β]. If choosing
8The first crossing time in each direction depends on the sharpness in each direction, hence by the time each coordinate reaches zero, we already have a conjugate point.
9Standard technique in calculus of variation, see e.g. proof of Legendre’s Thm (Gelfand and Fomin, 2000). 10If u > 0, then 15− 5u− √ 25u2 − 60u+ 225 < 0.
big is allowed by the considered interval (h ,c has to vanish at t1, t2), then the second variation is indefinite. This happens if |t2 − t1| > 2 ∗. By taking σ → 0, we get the following result.
Proposition 7 (Sufficient condition for saddle). The second variation of the action of Nesterov’s Lagrangian (damping 3/t) on f(x) = βx2/2 is an indefinite quadratic form for |t2− t1| > √ 40/β. This result generalizes to β-smooth multidimensional convex quadratics.
We remark that the inverse dependency on the square root of β is also predicted by the general proof in Sec. 3.1, where the argument of the Bessel functions is always t √ β.

heading: 3.3 Unboundedness of the action for large integration intervals (from above and below)
text: In Prop. 7, we showed that for big enough integration intervals, Nesterov’s method with damping 3/t on f(x) = βx2/2 is saddle point for the action. This suggests that the action is 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 method with damping 3/t on a β-smooth convex quadratic and J [Y ] = ∫ t2 t1 L(Y, Ẏ , t)dt. Let a, b be two arbitrary vectors in Rd. There exists a sequence of curves (Yk)k∈N, with Yk ∈ C1([t1, t2],Rd) and Yk(t1) = a, Yk(t2) = b for all k ∈ N, such that J [Yk] k→ ∞. In addition, if |t2 − t1| > √
40/β there exists another sequence with the same properties diverging to −∞.
Proof. The proof is based on the computation performed for Prop. 7. Crucially, note that for the quadratic loss function case we have δ2J = J . For the case a = b = 0, we showed that for any interval [t1, t2], by picking small enough, we have J(h ,c) = δ2J(h ,c) > 0 (also illustrated in the figure supporting the proof). Hence, J(σ ·h ,c)→ +∞ as σ →∞. Same argument holds for −∞ in the large interval case. This proves the assertion for a = b = 0. Note that the curves corresponding to the diverging sequences can be modified to start/end at any a, b ∈ Rd at the price of a bounded error in the action. This does not modify the behavior in the limit; hence, the result follows.

heading: 3.4 Optimality of Nesterov with vanishing damping if curvature vanishes (polynomial loss)
text: Note that the bound on |t2 − t1| in Prop. 7 gets loose as β decreases. This is also predicted by the argument with Bessel functions in Sec. 3.1, 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∗)p, with p > 2. As Nesterov’s path approaches the minimizer x∗, the curvature vanishes; hence, for every β > 0 there exists a time interval (t1,∞) where the curvature along Nesterov’s path is less then β. This suggest that, for losses with vanishing curvature at the solution, there exists a time interval (t∗,∞) where Nesterov’s path is actually a 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 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 a 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., 2021). Hence, it is safe to claim that in the machine learning setting Nesterov’s path is only optimal for small time intervals, as shown in Thm. 5.

heading: 4 Analysis of the action of Nesterov’s path with constant damping α
text: In the µ-strongly convex case11, it is well known that a constant damping α = 2 √ µ yields acceleration compared to gradient descent12. This choice completely changes the geometry of Nesterov’s path and needs a separate discussion. The corresponding Lagrangian is
Lα(Y, Ẏ , t) = e αt
( 1
2 ‖Ẏ ‖2 − f(Y )
) . (15)
11Hessian eigenvalues lower bounded by µ > 0. 12The corresponding rate is linear and depends on √ µ/β, as opposed to µ/β (GD case).
Again, we consider the quadratic function f(x) = βx2/2 and examine Jacobi’s ODE ḧ(t) + αḣ(t) + βh(t) = 0. We have to determine whether there exists a non-trivial solution such that h(t1) = h(t2) = 0 and h(t) vanishes also at a point t ∈ (t1, t2), the conjugate point. For the critical damping case α = 2 √ β the general solution such that h(t1) = 0 is
h(t) = Ce− √ βt(t− t1). (16)
There is no non-trivial solution h that vanishes also at t ∈ (t1, t2) — no conjugate points. The same holds for the overdamping case α > 2 √ β, where the solution that vanishes at t1 is
h(t) = Ce− αt 2 ( e 1 2 √ α2−4βt − e 12 √ α2−4β(2t1−t) ) . (17)
For the underdamping case α < 2 √ β, the picture gets more similar to the vanishing damping case (Sec.3.1). The solution under h(t1) = 0 is
h(t) = Ce− αt 2 ( sin (√ 4β − α2
2 t
) − tan (√ 4β − α2
2 t1
) cos (√ 4β − α2
2 t
)) . (18)
Hence all points t > t1 conjugate to t1 satisfy t = t1 + 2kπ/ √
4β − α2 for k ∈ N. Therefore for any t2 > t1 + 2π/ √ 4β − α2 there exists a conjugate point t ∈ (t1, t2).
Theorem 9 (Global optimality of overdamped Nesterov, suboptimality of accelerated Nesterov). Let f : Rd → R be a strongly convex quadratic, and let X : R → Rd be a solution to the ODE Ẍ + αẊ + ∇f(X) = 0. For 0 ≤ t1 < t2, consider the action J [Y ] = ∫ t2 t1 Lα(Y, Ẏ , t)dt. If
α ≥ 2 √ β, where β is the max. eigenvalue of the Hessian of f , then Nesterov’s path minimizes J over all curves s.t. Y (t1) = X(t1) and Y (t2) = X(t2). Else (e.g. acceleration setting α ≈ 2 √ µ),
Nesterov’s path is optimal only for |t2 − t1| ≤ 2π/ √ 4β − α2 and otherwise is a saddle point.
Proof. As for the proof of Thm. 5, the condition on conjugate points has to hold for each eigendirection separately. We conclude by noting that eigenvalues are in the range [µ, β]. For the underdamping case, we give a concrete example for α = β = 1, to show the saddle point nature. Consider the finite-norm perturbation h(t) = sin(kπ(t− t1)/(t1 − t2)), where k ∈ N. Then,
δ2J [γ](σh) = σ2e2t1 ( k2e−(t2−t1)π2(et2−t1 − 1)(2k2π2 − (t2 − t1)2)
(t2 − t1)2(4k2π2 + (t2 − t1)2)
) . (19)
Hence, for any t2 − t1 > √ 2kπ, it holds that δ2J [γ](σh) < 0.
Extending the optimality claims to t2 = ∞ with Γ-convergence. From an optimization viewpoint, the most interesting setting is to study the action over the complete trajectory, i.e. to consider Y ∈ C1([t1,∞),Rd) such that Y (t1) = X(t1) and Y (∞) = x∗, a minimizer. Prop. 7 and Thm. 9 show that the question of optimality in this case deserves a discussion only in the extremely overdamped case α ≥ 2 √ β, where minimality is guaranteed for any time interval. A careful study of the infinite-time setting would require the theory of Γ-convergence (Braides et al., 2002). The usual pipeline consists in defining a sequence of problems Jk, on intervals [t1, tk2 ], with t k 2 → ∞ as k → ∞. Under the assumption that each Jk admits a global minimizer (only true for the overdamped case), one can study convergence of J∗k = min{Jk[Y ] : Y ∈ C1([t1, tk2 ],Rd)} to J∗∞ = min{J∞(Y ) : Y ∈ C1([t1,∞),Rd)}. While existence of J∗∞ and J∞ is not trivial in general, for our setting the pipeline directly yields minimality of overdamped Nesterov’s path until∞.

heading: 5 Discussion of the main findings and directions for future research
text: In this section, we summarize the results of Sec. 3 & 4 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 path for minimization of the action corresponding to the Bregman Lagrangian is strictly linked to the curvature around the minimizer reached by the flow.
2. As the maximal curvature β increases, it gets increasingly difficult for accelerated flows to minimize the action over long integration intervals: both the accelerated ODEs Ẍ + 3/tẊ + ∇f(X) = 0 and Ẍ + 2√µẊ +∇f(X) = 0 are optimal only for intervals of length ∝ 1/ √ β.
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, as long as each coordinate in parameter space decreases monotonically (as it is the case for gradient descent), Nesterov’s path is optimal. See also O’donoghue and Candes (2015). 5. Hence, Nesterov’s method with very high damping α > 2 √ β — which does not oscillate and
hence does not lead to acceleration (see Fig. 3) — minimizes the action.
In a nutshell, locally Nesterov’s method does indeed optimize a 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 Lagrangian. 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) be any function which does not involve the velocity, then it is easy to see that the Lagrangian L is equivalent to
L̃(Y, Ẏ , t) = L(Y, Ẏ , t) + 〈 Ẏ , ∂F
∂Y (X, t)
〉 + ∂F
∂t (X, t).
(20) This simple fact opens up new possibilities for analyzing and interpreting Nesterov’s method using different functionals — which perhaps have both a more intuitive form and better properties. Higher order ODEs. On a similar note, it could be possible to convexify the action functional by considering a logical OR between symmetric ODEs, e.g ( d 2
dt2 + α d dt + β)(
d2 dt2 − α d dt + β)X = 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 to 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) to 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; Głuch and Urbanke, 2021) 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 Theorem and acceleration, but instead study the interaction between the symmetries in neural network landscapes and optimizers. While some preliminary implications of Noether’s theorem for time-rescaling of accelerated flows are discussed in (Wibisono et al., 2016), we suspect that a more in-depth study could lead, in combination with recent work on the Hamiltonian formalism (Diakonikolas and Jordan, 2019), to substantial insights on the hidden invariances of accelerated paths. We note that finding these invariances might not be an easy task, and requires a dedicated work: indeed, even for simple linear damped harmonic oscillators (constant damping), invariance in the dynamics can be quite complex (Choudhuri et al., 2008).

heading: 6 Conclusion
text: We provided an in-depth theoretical analysis of Nesterov’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 a 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’avenir” program, reference ANR-19-P3IA-0001(PRAIRIE 3IA Institute). Hadi Daneshmand acknowledges support from the European Research Council (grant SEQUOIA 724063).

Review summaries:
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. 

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.  The main contributions of the paper are as follows:  1. 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. 2. Constructively proving that the action for the Nesterov trajectory is suboptimal in the quadratic setting (Proposition 7). 3. 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). 

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.