# Near-optimal Closed-loop Method via Lyapunov Damping for Convex Optimization

Severin Maier Camille Castera∗
Department of Mathematics
University of Tübingen
Germany  Peter Ochs
Department of Mathematics and Computer Science
Saarland University
Germany

###### Abstract

We introduce an autonomous system with closed-loop damping for first-order
convex optimization. While, to this day, optimal rates of convergence are only
achieved by non-autonomous methods via open-loop damping (e.g., Nesterov’s
algorithm), we show that our system is the first one featuring a closed-loop
damping while exhibiting a rate arbitrarily close to the optimal one. We do so
by coupling the damping and the speed of convergence of the system via a well-
chosen Lyapunov function. We then derive a practical first-order algorithm
called LYDIA by discretizing our system, and present numerical experiments
supporting our theoretical findings.

11footnotetext: Corresponding author<EMAIL_ADDRESS>
##  1 Introduction

We consider the unconstrained minimization of a smooth convex real-valued and
lower-bounded function $f$ over a Hilbert space $\mathcal{H}$:

$\min_{x\in\mathcal{H}}f(x).$

One of the most famous algorithms for such optimization problems is Nesterov’s
Accelerated Gradient method (NAG) [25], which is known to achieve the optimal
rate of convergence for first-order methods on convex functions with
Lipschitz-continuous gradient. Among several ways to explain the efficiency of
NAG, Su et al. [31] studied the algorithm through the lens of Ordinary
Differential Equations (ODEs) and proposed the following model:

$\ddot{x}(t)+\frac{a}{t}\dot{x}(t)+\nabla f(x(t))=0,\qquad\forall t\geq
t_{0},$ ($\text{AVD}_{a}$)

where $a>0$, $t_{0}\geq 0$ and $\nabla f$ denotes the gradient of the smooth
real-valued convex function $f$. Here,
$\dot{x}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\frac{\mathrm{d}x}{\mathrm{d}t}$,
respectively
$\ddot{x}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\frac{\mathrm{d}^{2}x}{\mathrm{d}t^{2}}$,
denotes the first, resp. second, time-derivative (or velocity, resp.
acceleration) of the solution $x$ of the ODE. AVD stands for Asymptotically
Vanishing Damping and relates to the coefficient $a/t$. NAG is obtained by
(non-straightforward) discretization of ($\text{AVD}_{a}$). Conversely
($\text{AVD}_{a}$) can be seen as NAG with infinitesimal step-sizes. Following
[31], many works studied the system ($\text{AVD}_{a}$), and notably proved
that when $a>3$, the function values along a solution (or trajectory) of
($\text{AVD}_{a}$) converge with the asymptotic rate
$o\left(\frac{1}{t^{2}}\right)$ to the optimal value as $t\to+\infty$ [31, 6,
24]. This matches the rate of NAG in the case of discrete (or iterative)
algorithms [25]. We further discuss additional results for ($\text{AVD}_{a}$)
and other possible choices of $a$ later in Section 2.

The interest in the connection between ODEs (or dynamical systems) and
algorithms comes from the abundance of theory and tools for analyzing ODEs and
the insights that they provide for understanding algorithms. In particular,
continuous-time analyses relying on Lyapunov functions can often be adapted to
the discrete setting, see e.g., [6]. In this work, we are interested in a
special case of the Inertial Damped Gradient (IDG) system:

$\ddot{x}(t)+\gamma(t)\dot{x}(t)+\nabla f(x(t))=0,\qquad\forall t\geq t_{0},$
($\text{IDG}_{\gamma}$)

where $\gamma$ is a positive function and is called “damping” by analogy with
mechanics. There are two inherently different ways of designing the damping
coefficient $\gamma$: the so-called open- and closed-loop manners. While
obtaining fast convergence rates $o\left(\frac{1}{t^{2}}\right)$ with open-
loop damping is known, for example, when $\gamma(t)=\frac{a}{t}$ with $a>3$,
which exactly yields ($\text{AVD}_{a}$), we propose the first closed-loop
damping that provides ($\text{IDG}_{\gamma}$) with near-optimal rate of
convergence. Our special instance of ($\text{IDG}_{\gamma}$) is called (LD)
and is introduced hereafter. We first discuss the problem setup in more
details.

###  1.1 Problem setting

The damping $\frac{a}{t}$ in ($\text{AVD}_{a}$) depends explicitly on the time
variable $t$, making the system non-autonomous. We say that a damping with
such explicit dependence on the time $t$ is _open-loop_. In contrast, a
damping $\gamma$ that does not explicitly depend on $t$ is called _closed-
loop_ and makes ($\text{IDG}_{\gamma}$) an autonomous ODE (since the ODE is
then independent of $t_{0}$): the feedback for the system, in terms of
$\gamma$, may only depend on the state $x$ (and its derivatives) but _not
explicitly_ on the time $t$. For optimization, autonomous ODEs are often
preferable over non-autonomous ones, since the dependence on the time $t$, and
hence on the initial time $t_{0}$, is removed. For example, even though the
asymptotic rate of convergence of ($\text{AVD}_{a}$) does not depend on
$t_{0}$, the trajectory does depend on the choice of $t_{0}$: when choosing a
large $t_{0}$, the damping $a/t$ is very small at all time and the “damping
effect” is almost completely lost. We illustrate this in Figure 1 where we
show how the choice of $t_{0}$ heavily influences the solution of
($\text{AVD}_{a}$). Additionally some important tools for analyzing ODEs only
hold (or are simpler to use) for autonomous ODEs, see e.g., the
Hartman–Grobman Theorem [20, 19], which relates the behavior of autonomous
ODEs around their equilibrium points to that of a linear system. Another such
example is the so-called ODE method [23, 13], which formally states that
algorithms with vanishing step-sizes asymptotically behave like solutions of
corresponding ODEs.

In this work we therefore tackle the following open question:

_Can one design the damping $\gamma$ in ($\text{IDG}_{\gamma}$) in a closed-
loop manner (so as to make the ODE autonomous) while still achieving the same
optimal convergence rate as ($\text{AVD}_{a}$)?_

Figure 1: Comparison of our autonomous system (LD) and the non-autonomous one
($\text{AVD}_{a}$) for different initial times $t_{0}$ on the 2D function
$f(x_{1},x_{2})=x_{1}^{4}+0.1x_{2}^{4}$. The left plot shows the evolution of
the function values over time. The right plot shows the trajectories in the
space $(x_{1},x_{2})$. Different initial times heavily affect the solution of
($\text{AVD}_{a}$), but not (LD). We approximated the solutions using NAG for
($\text{AVD}_{a}$) and LYDIA (see Algorithm 1) for (LD), both with very small
step-sizes.

This question hides a circular argument that makes it hard to solve. Indeed,
according to Cabot et al. [16], a sufficient condition on $\gamma$ for the
convergence of the function values is that
$\int_{t_{0}}^{+\infty}\gamma(t)\mathrm{d}t=+\infty$. The straightforward
choice is then the constant damping $\gamma(t)=a>0$, which in
($\text{IDG}_{\gamma}$) yields the Heavy Ball with Friction (HBF) algorithm
[28], known to be sub-optimal for convex functions. We therefore seek a
closed-loop damping that converges to zero, but not “too fast”. In the open-
loop setting, the natural choice is $\gamma(t)=\frac{a}{t},\ a>0$ because this
is the fastest polynomial decay that converges to zero while being non-
integrable. Further [4] showed that any damping of the form
$\frac{a}{t^{\beta}}$ with $\beta\in(0,1)$ yields a sub-optimal rate.
Therefore we formally seek to design a closed-loop damping $\gamma$ that
behaves like $\frac{1}{t}$. Because it cannot depend directly on the variable
$t$, our closed-loop damping $\gamma$ must be built from other quantities of
the system that may converge to zero, for example
$\mathop{}\left\lVert\dot{x}(t)\right\rVert$. _However, the rate at which such
quantities converge to zero depend themselves on the choice of $\gamma$_. To
escape this loop of thought, we design $\gamma$ using quantities that are
known to behave asymptotically like $\frac{1}{t}$ in the case of
($\text{AVD}_{a}$) and investigate whether this choice of $\gamma$ still gives
fast convergence rates. This idea takes inspiration from [9] which used
$\mathop{}\left\lVert\dot{x}(t)\right\rVert$ as damping, with a key difference
that we now explain.

###  1.2 Our contribution

In the case of ($\text{AVD}_{a}$) with $a>3$, it is known that under standard
assumptions the quantity
$E(t)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}f(x(t))-f^{\star}+\frac{1}{2}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}$
(where
$f^{\star}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\min_{\mathcal{H}}f$) is
such that $E(t)=o\left(\frac{1}{t^{2}}\right)$ [24]. Therefore, following the
aforementioned intuition, we propose a closed-loop damping defined for all
$t\geq t_{0}$ by
$\gamma(t)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sqrt{E(t)}$. Our version
of ($\text{IDG}_{\gamma}$) then reads:

$\ddot{x}(t)+\sqrt{E(t)}\dot{x}(t)+\nabla f(x(t))=0,\qquad\forall t\geq
t_{0},$ (LD)

and is called (LD) for _Lyapunov Damping_ , since it will turn out later that
$E$ is non-increasing, making it a so-called “Lyapunov function” for (LD).
Note that (LD) assumes the availability of the optimal value $f^{\star}$, we
further discuss this later in Remark 4.10. Our main result is then that our
system (LD) which features a closed-loop damping yields the following rate of
convergence.

######  Theorem 1.1.

Assume that $f$ is a continuously differentiable convex function and that
$\operatorname*{\arg\\!\min}_{\mathcal{H}}f\neq\emptyset$. Then, for any
bounded solution $x$ of (LD) and for any $\delta>0$,

$f(x(t))-f^{\star}=o\left(\frac{1}{t^{2-\delta}}\right).$

This means that the rate of our method is arbitrarily close to
$o\left(\frac{1}{t^{2}}\right)$, the optimal one achieved by
($\text{AVD}_{a}$) with $a>3$. To the best of our knowledge, this is the first
system with closed-loop damping featuring such rate. Additionally, note that
(LD) does not make use of the hyper-parameter $a$, whose choice is crucial in
($\text{AVD}_{a}$).

###  1.3 Organization

In Section 2 we review related work regarding ODEs for optimization, closed-
loop damping, and known results in the open-loop case. In Section 3 we make
the setting precise and show the existence of solutions to (LD). Section 4 is
devoted to showing our main result. In Section 5 we derive a practical
algorithm from (LD) and use it to perform numerical experiments. We finish by
drawing conclusions and further discussing our results.

##  2 Related Work

#### ODEs for optimization.

There is a long line of work in exploiting the interplay between ODEs and
optimization algorithms, going back, at least, to the work of Polyak’s [28]
Heavy Ball with Friction (HBF) method for acceleration. As previously stated,
Su et al. [31] linked NAG [25] to the differential equation
($\text{AVD}_{a}$), hence providing a new view on the heavily used, yet not
perfectly understood algorithm. NAG is however obtained via a non-
straightforward discretization of ($\text{AVD}_{a}$) since the gradient of $f$
is evaluated at an “extrapolated point”. Recently, Alecsa et al. [2] proposed
a model with “implicit Hessian”, whose Euler explicit discretization yields
NAG. Higher-order ODEs have also been introduced to better understand NAG:
Attouch et al. [7] proposed a model with “Hessian damping” based on [3], while
Shi et al. [30] similarly considered higher-resolution ODEs allowing to better
distinguish NAG from other ($\text{IDG}_{\gamma}$) systems.

#### Closed-loop damping.

The closest work to ours is [9], which proposed a closed-loop damping of the
form $\gamma=\mathop{}\left\lVert\dot{x}\right\rVert^{p}$ for several values
of $p\in\mathbb{R}$. Our work builds on [9] since our damping $\sqrt{E}$ also
involves $\mathop{}\left\lVert\dot{x}\right\rVert$. Yet, Attouch et al. [9]
could provide counterexamples for which their systems do not achieve near-
optimal rates, unlike ours. A key difference is that our damping $\sqrt{E}$ is
non-increasing, while $\mathop{}\left\lVert\dot{x}\right\rVert$ may oscillate
heavily. They nonetheless derived rates under additional assumptions (e.g.
strong convexity or the Kurdyka-Łojasiewicz (KL) property).

Lin and Jordan [22] introduced more complex systems of closed-loop dampings
relying on the gradient $\nabla f$ and the speed $\dot{x}$. This was followed
by Attouch et al. [10] who considered a system that is shown to generalize the
systems in [22]. Further Attouch et al. [10] showed that their system can be
interpreted as a time-rescaled gradient flow combined with so-called “time
averaging” techniques. Their time-scaling is expressed in terms of the inverse
of the norms of the speed $\dot{x}$ and the gradient $\nabla f$. However, the
improvement achieved by time rescaling cannot carry through discretization
since it amounts to following the same trajectory but faster, which for
discrete algorithms would boil down to increasing the step-size, yielding
numerical instabilities. Nonetheless, by combining time rescaling and time
averaging, they managed to build a practical method achieving acceleration
compared to the $\mathcal{O}\left(\frac{1}{t}\right)$ rate of gradient flow,
but still sub-optimal compared to ($\text{AVD}_{a}$).

Adly et al. [1] proposed to replace the term $\gamma(t)\dot{x}(t)$ in
($\text{IDG}_{\gamma}$) by a “non-smooth” potential. Their non-smooth
potential provides the solutions of their differential inclusion with finite
length and convergence to a point very close to a minimizer of $f$ (if such a
point exists). However, since the solution does not converge to the minimal
value, it does not have the optimal rate that we seek.

Our damping makes use of the optimality gap $f(x(t))-f^{\star}$ (see Remark
4.10 for further discussion). This idea is not new and is used, for example,
in the Polyak step-size $\frac{f(x_{k})-f^{\star}}{\mathop{}\left\lVert\nabla
f(x_{k})\right\rVert^{2}}$ [27]. In our system (LD) the optimality gap is
rather used for designing the damping $\gamma$ rather than the step-size.

#### Open-loop damping and proof techniques.

The convergence properties of ($\text{AVD}_{a}$) (and more generally
($\text{IDG}_{\gamma}$) in the open-loop setting) have been intensively
studied. First, for ($\text{AVD}_{a}$) with $a>3$, following [31], the
convergence rate $o\left(\frac{1}{t^{2}}\right)$ for function values and the
convergence of the trajectories were proved in [24, 6, 17]. In the setting
$a<3$, [11, 8] derived the sub-optimal rate
$\mathcal{O}\left(\frac{1}{t^{\frac{2a}{3}}}\right)$. For the critical value
$a=3$ only the rate $\mathcal{O}\left(\frac{1}{t^{2}}\right)$ is known and
whether this rate can be improved to $o\left(\frac{1}{t^{2}}\right)$ and
whether the trajectories converge remains open. Rates have also been derived
under additional assumptions such as the KL property [12].

Regarding ($\text{IDG}_{\gamma}$), Attouch and Cabot [4] developed general
conditions for the convergence of the values and of the trajectories, which
unify several results mentioned above. All these results have in common that
they rely on the analysis of Lyapunov functions, like $E$ previously
introduced. We refer to [32, 33] for more details on Lyapunov analyses. The
proof of our main result takes inspiration from those in [15] where sufficient
conditions to derive optimal rates are provided. They must nonetheless be
significantly adapted since some of the conditions in [15] do not hold
generally for closed-loop dampings like ours. We replace them by using a
specific property of our system (see Lemma 4.1 hereafter). A more detailed
comparison follows our main analysis in Remark 4.9.

##  3 Preliminaries and Existence of Solutions

Throughout the paper we fix a real Hilbert space $\mathcal{H}$ with inner
product $\mathop{}\left\langle\cdot,\cdot\right\rangle$ and induced norm
$\mathop{}\left\lVert\cdot\right\rVert$.
We make the following assumptions on the function $f$.

######  Assumption 1.

The function $f:\mathcal{H}\to\mathbb{R}$ is

  1. (i)

convex and continuously differentiable with locally Lipschitz-continuous
gradient $\nabla f$;

  2. (ii)

bounded from below by
$f^{\star}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\inf_{\mathcal{H}}f.$

We also fix an initial time $t_{0}\geq 0$ and initial conditions
$x(t_{0})=x_{0}\in\mathcal{H}$, and
$\dot{x}(t_{0})=\dot{x}_{0}\in\mathcal{H}$.

######  Definition 1.

A function $x:[t_{0},+\infty[\to\mathcal{H}$, which is twice continuously
differentiable on $]t_{0},+\infty[$ and continuously differentiable on
$[t_{0},+\infty[$, is called a (global) _solution_ or _trajectory_ to
($\text{IDG}_{\gamma}$), resp. (LD), if it satisfies ($\text{IDG}_{\gamma}$),
resp. (LD), for all $t>t_{0}$ and satisfies the initial conditions previously
mentioned.

Given the setting above, we can ensure the existence and uniqueness of the
solutions of (LD).

######  Theorem 3.1.

Under Assumption 1, there exists a unique solution $x$ to (LD) with initial
conditions $\left(x_{0},\dot{x}_{0}\right)\in\mathcal{H}\times\mathcal{H}$ and
initial time $t_{0}\geq 0$.

The proof relies on the Picard–Lindelöf Theorem and is postponed to Appendix
A.

######  Remark 3.2.

The local Lipschitz-continuity of $\nabla f$ is only required to guarantee the
existence and uniqueness of the solutions on $[t_{0},+\infty[$ (see below),
but is not used elsewhere in our analysis.

We finally recall a special case of the Landau notation for asymptotic
comparison that we use heavily in the sequel.

######  Definition 2.

For any non-negative function $g\colon\mathbb{R}\to\mathbb{R}$ and
$\forall\alpha\geq 0$,

$\displaystyle g(t)=o\left(\frac{1}{t^{\alpha}}\right)$
$\displaystyle\iff\lim_{t\to+\infty}t^{\alpha}g(t)=0.$

##  4 Main Result: Convergence Rates for (LD)

This section is devoted to proving our main result Theorem 1.1, which states
that the solution of (LD) achieves a convergence rate that is arbitrarily
close to the optimal one for convex functions. First we show that $E$ is
indeed a Lyapunov function for the system (LD).

###  4.1 The Lyapunov function of (LD)

Throughout what follows, let $x$ be the solution of (LD) with the initial
conditions stated in Section 3. Recall that the damping coefficient in (LD) is
$\sqrt{E(t)}$ where for all $t\geq t_{0}$,
$E(t)=f(x(t))-f^{\star}+\frac{1}{2}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}$.
We first show identities that are specific to (LD) and that play a crucial
role in what follows.

######  Lemma 4.1.

Under Assumption 1 the solution $x$ of (LD) is such that $E$ is continuously
differentiable for all $t\geq t_{0}$ and

$\frac{\mathrm{d}E(t)}{\mathrm{d}t}=-\sqrt{E(t)}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2},$
(1)

so in particular $E$ is non-increasing. Furthermore, for all $t\geq t_{0}$ it
holds that

$\frac{\mathrm{d}\sqrt{E(t)}}{\mathrm{d}t}=-\frac{1}{2}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2},\quad\text{or
equivalently,}\quad\int_{t_{0}}^{t}\mathop{}\left\lVert\dot{x}(s)\right\rVert^{2}\mathrm{d}s=2\sqrt{E(t_{0})}-2\sqrt{E(t)}.$
(2)

###### Proof.

We apply the chain rule and use the fact that $x$ solves (LD) to obtain:

$\frac{\mathrm{d}E(t)}{\mathrm{d}t}=\mathop{}\left\langle\nabla
f(x(t)),\dot{x}(t)\right\rangle+\mathop{}\left\langle\ddot{x}(t),\dot{x}(t)\right\rangle\\\
=\mathop{}\left\langle\nabla f(x(t))-\sqrt{E(t)}\dot{x}(t)-\nabla
f(x(t)),\dot{x}(t)\right\rangle=-\sqrt{E(t)}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2},$
(3)

which proves (1). As for the second part, the chain rule and (1) imply

$\frac{\mathrm{d}\sqrt{E(t)}}{\mathrm{d}t}=\frac{1}{2\sqrt{E(t)}}\frac{\mathrm{d}E(t)}{\mathrm{d}t}=-\frac{1}{2\sqrt{E(t)}}\sqrt{E(t)}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}=-\frac{1}{2}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}.$

Finally, by the Fundamental Theorem of Calculus and the continuity of
$\dot{x}$ this is equivalent to

$\int_{t_{0}}^{t}\mathop{}\left\lVert\dot{x}(s)\right\rVert^{2}\mathrm{d}s=2\sqrt{E(t_{0})}-2\sqrt{E(t)}.\qed$

The function $E$ describes a quantity which is non-increasing along the
trajectory $x$, and note that $E(t)=0$ if, and only if, $f(x(t))=f^{\star}$
and $\dot{x}(t)=0$. Such a function is called _a Lyapunov function_ for the
system (LD).

###  4.2 Preliminary convergence results

We make the following assumptions, which are consistent with those in Theorem
1.1.

######  Assumption 2.

We assume that

  1. (i)

$\operatorname*{\arg\\!\min}_{\mathcal{H}}f\neq\emptyset$;

  2. (ii)

the solution $x$ of (LD) is uniformly bounded on $[t_{0},+\infty[$.

######  Remark 4.2.

Assumption 2-(ii) holds, for example, when $f$ is coercive.

We begin our analysis by showing that the trajectory $x$ minimizes the
function $f$. We do so by showing that $E(t)$ tends to zero as $t\to+\infty$.

######  Theorem 4.3.

Under Assumptions 1 and 2, $E(t)$ converges to zero as $t\to+\infty$. This
implies in particular that $\displaystyle
f(x(t))\xrightarrow[t\to+\infty]{}f^{\star}$ and
$\displaystyle\mathop{}\left\lVert\dot{x}(t)\right\rVert\xrightarrow[t\to+\infty]{}0$.

We make use of the following classical result to prove Theorem 4.3.

######  Lemma 4.4.

If $g$ is a non-negative continuous function on $[t_{0},+\infty[$ and
$\int_{t_{0}}^{+\infty}g(t)\mathrm{d}t$ is finite, then either
$\displaystyle\lim_{t\to+\infty}g(t)$ does not exist or
$\displaystyle\lim_{t\to+\infty}g(t)=0$.

The proof of Lemma 4.4 is postponed to Appendix B. We now prove Theorem 4.3.

###### Proof of Theorem 4.3.

Let $z\in\operatorname*{\arg\\!\min}_{\mathcal{H}}f$, and for all $t\geq
t_{0}$ define the so-called “anchor function”
$h_{z}(t)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\frac{1}{2}\mathop{}\left\lVert
x(t)-z\right\rVert^{2}$. Then $h_{z}$ is twice differentiable for all $t\geq
t_{0}$ and we have:

$\displaystyle\dot{h_{z}}(t)$ $\displaystyle=\mathop{}\left\langle
x(t)-z,\dot{x}(t)\right\rangle.$ (4)
$\displaystyle\begin{split}\ddot{h_{z}}(t)&=\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}+\mathop{}\left\langle
x(t)-z,\ddot{x}(t)\right\rangle\\\
&\overset{\mathclap{\eqref{LD}}}{=}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}+\mathop{}\left\langle
x(t)-z,-\sqrt{E(t)}\dot{x}(t)-\nabla f(x(t))\right\rangle\\\
&=\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}+\mathop{}\left\langle
x(t)-z,-\sqrt{E(t)}\dot{x}(t)\right\rangle-\mathop{}\left\langle x(t)-z,\nabla
f(x(t))\right\rangle\\\
&\overset{\eqref{eq::hztdot}}{\leq}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}-\sqrt{E(t)}\dot{h_{z}}(t)+f^{\star}-f(x(t)),\end{split}$
(5)

where we used the first-order characterization of the convexity of $f$ in the
last step. So $h_{z}(t)$ fulfills the following differential inequality:

$\ddot{h_{z}}(t)+\underset{=E(t)}{\underbrace{f(x(t))-f^{\star}+\frac{1}{2}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}}}\leq\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}+\frac{1}{2}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}-\sqrt{E(t)}\dot{h_{z}}(t),$

or equivalently,

$E(t)\leq\frac{3}{2}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}-\ddot{h_{z}}(t)-\sqrt{E(t)}\dot{h_{z}}(t).$
(6)

We integrate (6) from $t_{0}$ to $T>t_{0}$:

$\displaystyle\begin{split}\int_{t_{0}}^{T}E(t)\mathrm{d}t&\leq\frac{3}{2}\int_{t_{0}}^{T}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}\mathrm{d}t-\int_{t_{0}}^{T}\ddot{h_{z}}(t)\mathrm{d}t-\int_{t_{0}}^{T}\sqrt{E(t)}\dot{h_{z}}(t)\mathrm{d}t\\\
&=3\left(\sqrt{E(t_{0})}-\sqrt{E(T)}\right)-\dot{h_{z}}(T)+\dot{h_{z}}(t_{0})-\sqrt{E(t)}h_{z}(T)+\sqrt{E(0)}h_{z}(t_{0})\\\
&\qquad-\frac{1}{2}\int_{t_{0}}^{T}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}h_{z}(t)\mathrm{d}t,\end{split}$
(7)

where we performed integration by parts on the last integral and used Lemma
4.1. Note that by the boundedness of $E$ and the continuity of $f$,
$f(x)-f^{\star}$ and $\mathop{}\left\lVert\dot{x}\right\rVert$ are uniformly
bounded on $[t_{0},+\infty[$. This implies together with Assumption 2 that
$h_{z}$ and $\dot{h_{z}}$ are uniformly bounded as well. Therefore,
$\dot{h_{z}}(T)$, $\sqrt{E(T)}$ and $\sqrt{E(T)}h_{z}(T)$ are uniformly
bounded from above for all $T\in[t_{0},+\infty[$. Further
$-\int_{t_{0}}^{T}\mathop{}\left\lVert\dot{x}(s)\right\rVert^{2}h_{z}(s)\mathrm{d}s\leq
0$ and $\dot{h_{z}}(t_{0})$ and $\sqrt{E(t_{0})}h_{z}(t_{0})$ are constants.
So the right-hand side in (7) is uniformly bounded from above for all
$T\in[t_{0},+\infty[$. Therefore we deduce that

$\int_{t_{0}}^{+\infty}E(t)\mathrm{d}t<+\infty.$ (8)

Finally, $E$ is non-negative and non-increasing by (1), so it _converges_ to
some value $E_{\infty}\in[0,E(t_{0})]$ as $t\to\infty$. Further since $E$ is
continuous we can conclude by Lemma 4.4 that
$\displaystyle\lim_{t\to+\infty}E(t)=0.$ ∎

###  4.3 Rates of convergence for $E$

The proof of our main result Theorem 1.1 relies on the following lemma.

######  Lemma 4.5.

Let $\alpha\geq 0$: If
$\int_{t_{0}}^{+\infty}t^{\alpha}E(t)\mathrm{d}t<+\infty$, then
$\displaystyle\lim_{t\to+\infty}t^{\alpha+1}E(t)=0$.

This result follows from standard calculus arguments and is proved later in
Appendix B.
Observe that (8) already provides us with a first rate by applying Lemma 4.5
with $\alpha=0$.

######  Proposition 4.6.

Under Assumption 1 and 2, it holds that

$E(t)=o\left(\frac{1}{t}\right).$

Since $E$ is a sum of non-negative quantities, any convergence rate of $E$
translates into a rate for $f$, hence in particular Proposition 4.6 implies
$f(x(t))-f^{\star}=o\left(\frac{1}{t}\right)$. The proof of Theorem 1.1
follows similar steps as that of Theorem 4.3. The main idea is that by
combining (8) with (2) we can improve the rate from
$o\left(\frac{1}{t}\right)$ to $o\left(\frac{1}{t^{3/2}}\right)$ and
iteratively repeat this process. This is stated in the following theorem.

######  Theorem 4.7.

Under Assumptions 1 and 2 for all $0<\varepsilon<\frac{1}{2}$ and all
$n\in\mathbb{N}_{\geq 1}$ it holds that

$E(t)=o\left(\frac{1}{t^{\alpha_{n}-\alpha_{n-1}\varepsilon}}\right),\
\text{where}\
\alpha_{n}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}2-\left(\frac{1}{2}\right)^{n-1}.$
(9)

Before proving Theorem 4.7, we show that Theorem 1.1 is a direct consequence
of this result.

###### Proof of Theorem 1.1.

For any $0<\delta<1$, choose $0<\varepsilon<\frac{\delta}{2}$ and observe that

$\lim_{n\to+\infty}\alpha_{n}=2\text{, hence
}\lim_{n\to+\infty}\left(\alpha_{n}-\alpha_{n-1}\varepsilon\right)=2-2\varepsilon>2-\delta,$

which shows that there exists $N\in\mathbb{N}_{\geq 1}$, such that
$\alpha_{N}-\alpha_{N-1}\varepsilon>2-\delta$ and therefore by Theorem 4.7

$0=\lim_{t\to+\infty}t^{\alpha_{N}-\alpha_{N-1}\varepsilon}E(t)\geq\lim_{t\to+\infty}t^{2-\delta}E(t)\geq
0,$

hence

$\lim_{t\to+\infty}t^{2-\delta}E(t)=0.$

Finally the case $\delta\geq 1$ is covered by Proposition 4.6 and, as
previously discussed, the following implication holds for all $\delta>0$:

$E(t)=o\left(\frac{1}{t^{2-\delta}}\right)\Longrightarrow
f(x(t))-f^{\star}=o\left(\frac{1}{t^{2-\delta}}\right).\qed$

It now only remains to prove Theorem 4.7. We make use of the following lemma.

######  Lemma 4.8.

Let $g$ be continuous and non-negative on $[t_{0},+\infty[$. Then for any
$\beta>1$,

$\lim_{t\to+\infty}t^{\beta}g(t)\text{ exists and is finite
}\Longrightarrow\int_{t_{0}}^{+\infty}g(t)\mathrm{d}t<+\infty.$

The proof of Lemma 4.8 is postponed to Appendix B

###### Proof of Theorem 4.7.

Fix $0<\varepsilon<\frac{1}{2}$. We show (9) by induction over
$n\in\mathbb{N}_{>1}$. The case $n=1$ holds from Proposition 4.6. Observe that
for all $n\geq 1$, we have the following:

$\alpha_{n}-1=1-\left(\frac{1}{2}\right)^{n-1}=\frac{1}{2}\left(2-\left(\frac{1}{2}\right)^{n-2}\right)=\frac{\alpha_{n-1}}{2}.$
(10)

Let us now assume that there exists $n\geq 1$ such that:

$E(t)=o\left(\frac{1}{t^{\alpha_{n}-\alpha_{n-1}\varepsilon}}\right)\iff\sqrt{E(t)}=o\left(\frac{1}{t^{\frac{\alpha_{n}}{2}-\frac{\alpha_{n-1}}{2}\varepsilon}}\right).$
(I.H.)

To proceed by induction we need to show that (I.H.) implies

$E(t)=o\left(\frac{1}{t^{\alpha_{n+1}-\alpha_{n}\varepsilon}}\right).$ (11)

To this aim, it is actually sufficient to prove that

$\int_{t_{0}}^{+\infty}t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}E(t)\mathrm{d}t<+\infty.$
(12)

Indeed, according to Lemma 4.5 if (12) holds, then

$0=\lim_{t\to+\infty}t^{\frac{\alpha_{n}}{2}+1-\alpha_{n}\varepsilon}E(t)\overset{\eqref{eq::alphan}}{=}\lim_{t\to+\infty}t^{\alpha_{n+1}-\alpha_{n}\varepsilon}E(t),$

which is equivalent to (11).

To show (12) we multiply both sides of (6) by
$t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}$ and integrate from $t_{0}$ to
$T\geq t_{0}$:

$\int_{t_{0}}^{T}t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}E(t)\mathrm{d}t\leq\frac{3}{2}\int_{t_{0}}^{T}t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}\mathrm{d}t-\int_{t_{0}}^{T}t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\ddot{h_{z}}(t)\mathrm{d}t\\\
-\int_{t_{0}}^{T}t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\sqrt{E(t)}\dot{h_{z}}(t)\mathrm{d}t.$
(13)

Now it only remains to show that the limit as $T\to+\infty$ of each term on
the right-hand side of (13) is uniformly bounded from above for
$T\in[t_{0},+\infty[$, which will imply that the left-hand side remains
uniformly bounded as $T\to+\infty$. This approach is similar to the proof of
Theorem 4.3, but the key equation (2) allows deducing further integrability
results for $\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}$ by using the
induction hypothesis (I.H.), which is new and specific to the system (LD).
We first make the following observation using (10):

$\frac{t^{1+\varepsilon}}{t^{1-\frac{\alpha_{n}}{2}+\alpha_{n}\varepsilon}}\sqrt{E(t)}=t^{\frac{\alpha_{n}}{2}-\frac{\alpha_{n-1}}{2}\varepsilon}\sqrt{E(t)}\xrightarrow[t\to+\infty]{\eqref{I.H}}0.$

Therefore according to Definition 2, we have

$\frac{1}{t^{1-\frac{\alpha_{n}}{2}+\alpha_{n}\varepsilon}}\sqrt{E(t)}=o\left(\frac{1}{t^{1+\varepsilon}}\right),$
(14)

and using Lemma 4.8 with
$g(t)=\frac{1}{t^{1-\frac{\alpha_{n}}{2}+\alpha_{n}\varepsilon}}\sqrt{E(t)}$
and $\beta=1+\varepsilon$,

$\int_{t_{0}}^{+\infty}\frac{1}{t^{1-\frac{\alpha_{n}}{2}+\alpha_{n}\varepsilon}}\sqrt{E(t)}\mathrm{d}t<+\infty.$
(15)

We now use (15) to show the integrability of
$t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}$,
which shows the uniform boundedness of the first term on the right-hand side
of (13) as $T\to+\infty$. For any $T\geq t_{0}$:

$\int_{t_{0}}^{T}t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}\mathrm{d}t\overset{I.P.,\eqref{eq::dersqrtE}}{=}\left[-2t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\sqrt{E(t)}\right]_{t_{0}}^{T}-\int_{t_{0}}^{T}\left(\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon\right)t^{\frac{\alpha_{n}}{2}-1-\alpha_{n}\varepsilon}(-2\sqrt{E(t)})\mathrm{d}t\\\
\overset{\eqref{eq::alphan}}{=}-2T^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\sqrt{E(T)}+2t_{0}^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\sqrt{E(t_{0})}+2\left(\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon\right)\int_{t_{0}}^{T}\frac{1}{t^{1-\frac{\alpha_{n}}{2}+\alpha_{n}\varepsilon}}\sqrt{E(t)}\mathrm{d}t,$

where the second term is constant, the last integral is finite as
$T\to+\infty$ by (15) and

$-2\lim_{T\to+\infty}T^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\sqrt{E(T)}\leq
0.$

Therefore the first term in (13) is bounded:

$\int_{t_{0}}^{+\infty}t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}\mathrm{d}t<+\infty.$
(16)

Looking at the second term in (13) we have:

$-\int_{t_{0}}^{T}t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\ddot{h_{z}}(t)\mathrm{d}t\overset{I.P.}{=}-\left[t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\dot{h_{z}}(t)\right]_{t_{0}}^{T}+\left(\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon\right)\int_{t_{0}}^{T}t^{\frac{\alpha_{n}}{2}-1-\alpha_{n}\varepsilon}\dot{h_{z}}(t)\mathrm{d}t\\\
\overset{I.P.}{=}-T^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\dot{h_{z}}(T)+t_{0}^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\dot{h_{z}}(t_{0})+\left(\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon\right)\left[t^{\frac{\alpha_{n}}{2}-1-\alpha_{n}\varepsilon}h_{z}(t)\right]_{t_{0}}^{T}\\\
-\left(\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon\right)\left(\frac{\alpha_{n}}{2}-1-\alpha_{n}\varepsilon\right)\int_{t_{0}}^{T}t^{\frac{\alpha_{n}}{2}-2-\alpha_{n}\varepsilon}h_{z}(t)\mathrm{d}t.$
(17)

Recall that there exists a $0\leq M<+\infty$ such that$\ \forall t\geq t_{0}$
$h_{z}(t)\in[0,M]$, since by Assumption 2, $x$ is bounded. Due to $-\
\underset{>0}{\underbrace{\left(\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon\right)}}\underset{<0}{\underbrace{\left(\frac{\alpha_{n}}{2}-1-\alpha_{n}\varepsilon\right)}}>0$
and $\frac{\alpha_{n}}{2}-2-\alpha_{n}\varepsilon<-1$, we can bound the limit
of the last term in (17) as $T\to+\infty$:

$-\left(\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon\right)\left(\frac{\alpha_{n}}{2}-1-\alpha_{n}\varepsilon\right)\int_{t_{0}}^{+\infty}t^{\frac{\alpha_{n}}{2}-2-\alpha_{n}\varepsilon}h_{z}(t)\mathrm{d}t\\\
\leq-M\left(\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon\right)\left(\frac{\alpha_{n}}{2}-1-\alpha_{n}\varepsilon\right)\int_{t_{0}}^{+\infty}t^{\frac{\alpha_{n}}{2}-2-\alpha_{n}\varepsilon}\mathrm{d}t<+\infty.$

Again by boundedness of $x$ and by the definition of $\dot{h_{z}}$ we get:

$\begin{split}-\lim_{T\to+\infty}T^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\dot{h_{z}}(T)&\overset{\mathclap{\text{C.S.}}}{\leq}\lim_{T\to+\infty}T^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\mathop{}\left\lVert
x(T)-z\right\rVert\mathop{}\left\lVert\dot{x}(T)\right\rVert\\\
&\leq\sqrt{M}\lim_{T\to+\infty}T^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\mathop{}\left\lVert\dot{x}(T)\right\rVert=0.\end{split}$

Indeed,

$0\overset{\text{\eqref{I.H}}}{=}\lim_{t\to+\infty}t^{\alpha_{n}-\alpha_{n-1}\varepsilon}E(t)=\lim_{t\to+\infty}t^{\alpha_{n}-\alpha_{n-1}\varepsilon}\left(f(x(t))-f^{\star}+\frac{1}{2}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}\right)\\\
\geq\lim_{t\to+\infty}t^{\alpha_{n}-\alpha_{n-1}\varepsilon}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}\geq
0,$

hence:

$\displaystyle\lim_{t\to+\infty}t^{\alpha_{n}-\alpha_{n-1}\varepsilon}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}=0\iff$
$\displaystyle\lim_{t\to+\infty}t^{\frac{\alpha_{n}}{2}-\frac{\alpha_{n-1}}{2}\varepsilon}\mathop{}\left\lVert\dot{x}(t)\right\rVert=0$
$\displaystyle\Rightarrow\lim_{t\to+\infty}t^{\frac{\alpha_{n}}{2}-\frac{\alpha_{n-1}}{2}\varepsilon-\varepsilon}\mathop{}\left\lVert\dot{x}(t)\right\rVert=0\overset{\eqref{eq::alphan}}{\iff}$
$\displaystyle\lim_{t\to+\infty}t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\mathop{}\left\lVert\dot{x}(t)\right\rVert=0.$

To conclude that the limit $T\to+\infty$ of the right-hand side of (17) is
bounded from above, we observe that two of the three remaining terms are
constant and

$\lim_{T\to+\infty}\left(\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon\right)T^{\frac{\alpha_{n}}{2}-1-\alpha_{n}\varepsilon}h_{z}(T)=0,$

since $\frac{\alpha_{n}}{2}-1-\alpha_{n}\varepsilon<0$ and $h_{z}$ is bounded.
We finish the proof by bounding the third term of (13). For $T\geq t_{0}$ we
have:

$-\int_{t_{0}}^{T}t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\sqrt{E(t)}\dot{h_{z}}(t)\mathrm{d}t\overset{I.P.,\eqref{eq::dersqrtE}}{=}-\left[t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\sqrt{E(t)}h_{z}(t)\right]_{t_{0}}^{T}\\\
+\int_{t_{0}}^{T}\left(\left({\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\right)t^{{\frac{\alpha_{n}}{2}-1-\alpha_{n}\varepsilon}}\sqrt{E(t)}-\frac{1}{2}t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}\right)h_{z}(t)\mathrm{d}t\\\
=-T^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\sqrt{E(T)}h_{z}(T)\
+t_{0}^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\sqrt{E(t_{0})}h_{z}(t_{0})+\left({\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\right)\int_{t_{0}}^{T}t^{\frac{\alpha_{n}}{2}-1-\alpha_{n}\varepsilon}\sqrt{E(t)}h_{z}(t)\mathrm{d}t\\\
-\frac{1}{2}\int_{t_{0}}^{T}t^{\frac{\alpha_{n}}{2}-\alpha_{n}\varepsilon}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}h_{z}(t)dt.$
(18)

Only the third term on the right-hand side of (18) is neither constant nor
non-positive. Using again the boundedness of $h_{z}$, it holds that:

$\int_{t_{0}}^{+\infty}t^{\frac{\alpha_{n}}{2}-1-\alpha_{n}\varepsilon}\sqrt{E(t)}h_{z}(t)\mathrm{d}t\leq
M\int_{t_{0}}^{+\infty}t^{\frac{\alpha_{n}}{2}-1-\alpha_{n}\varepsilon}\sqrt{E(t)}\mathrm{d}t\overset{\eqref{eq::integrable_arbitrary_n}}{<}+\infty.$

Hence the limit as $T\to+\infty$ of the third term of (13) is bounded from
above as well. Therefore all limits as $T\to+\infty$ of the terms on the
right-hand side of (13) are bounded from above, hence (12) holds. By
induction, we conclude that (9) holds for all $n\in\mathbb{N}_{\geq 1}$. ∎

######  Remark 4.9.

The induction step of Theorem 4.7 resembles the proof of [15, Lemma 3.10].
Yet, their result is not directly applicable to (LD) because it requires the
knowledge of an asymptotic lower-bound on the damping, which we do not know a
priori. Furthermore, Cabot and Frankel [15] showed how to iteratively repeat
the application of this result but their proof relies on a strong
integrability statement on $\mathop{}\left\lVert\dot{x}(t)\right\rVert$ that
may not hold in general. The specific nature of our system (LD) allows us to
deduce this integrability statement instead of assuming it.

###  4.4 Drawbacks of the approach

Now that we presented the main benefits of using a Lyapunov function as
damping in (LD), we discuss some drawbacks of our approach, starting with the
following remark.

######  Remark 4.10.

Our system (LD) makes use of the optimal value $f^{\star}$. The latter might
be unknown in general but is known in several practical cases such as over-
determined regression with squared loss, or empirical risk minimization of
some over-parameterized machine learning problems [18]. We refer to [14] for
more examples and further discussion. All the results above do not require the
knowledge of $f^{\star}$, only its existence. However Algorithm 1 presented in
Section 5 is only practical when $f^{\star}$ is known.

The second drawback of our approach is that we can lower bound the convergence
rate of our damping $\sqrt{E(t)}$. This not surprising as the bound actually
matches the sufficient condition from [16] mentioned in the introduction.

######  Proposition 4.11.

The convergence rate of the damping $\sqrt{E}$ of the dynamical system (LD)
_cannot_ be asymptotically faster than $\frac{1}{t}$, i.e., there exists no
$\alpha>1$ such that $\sqrt{E(t)}=o\left(\frac{1}{t^{\alpha}}\right)$ for a
non-constant bounded solution of (LD).

######  Remark 4.12.

Proposition 4.11 expresses that $E$ can never vanish faster than
$o(\frac{1}{t^{2}})$. However, this does not mean that the convergence rate of
$f(x(t))-f^{\star}$ can never be faster than the worst-case
$o(\frac{1}{t^{2}})$; one can sometimes obtain faster convergence of function
values, as we will observe in the numerical experiments.

###### Proof of Proposition 4.11.

Assume that $\sqrt{E(t)}=o\left(\frac{1}{t^{\alpha}}\right)$ for some
$\alpha>1$, then by Lemma 4.8,

$\int_{t_{0}}^{\infty}\sqrt{E(t)}\mathrm{d}t<+\infty.$ (19)

Let us make a similar computation as in [16, Prop. 3.5]:

$\begin{split}\frac{\mathrm{d}E(t)}{\mathrm{d}t}+2\sqrt{E(t)}E(t)&\overset{\mathclap{\eqref{eq::derE}}}{=}-\sqrt{E(t)}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}+2\sqrt{E(t)}\left(f(x(t))-f^{\star}+\frac{1}{2}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}\right)\\\
&=2\sqrt{E(t)}(f(x(t))-f^{\star})\geq 0.\end{split}$ (20)

Multiply (20) by $e^{2\int_{t_{0}}^{t}\sqrt{E(s)}\mathrm{d}s}>0$ to obtain

$\begin{split}0\leq
e^{2\int_{t_{0}}^{t}\sqrt{E(s)}\mathrm{d}s}\frac{\mathrm{d}E(t)}{\mathrm{d}t}+2\sqrt{E(t)}e^{2\int_{t_{0}}^{t}\sqrt{E(s)}\mathrm{d}s}E(t)=\frac{\mathrm{d}}{\mathrm{d}t}\left[e^{2\int_{t_{0}}^{t}\sqrt{E(s)}\mathrm{d}s}E(t)\right].\end{split}$
(21)

Now integrate 21 from $t_{0}$ to $t$:

$\begin{split}0&\leq
e^{2\int_{t_{0}}^{t}\sqrt{E(s)}\mathrm{d}s}E(t)-E(t_{0})\\\ \iff E(t)&\geq
e^{-2\int_{t_{0}}^{t}\sqrt{E(s)}\mathrm{d}s}E(t_{0}).\end{split}$

This implies that

$\lim_{t\to\infty}E(t)\geq
e^{-2\int_{t_{0}}^{\infty}\sqrt{E(s)}\mathrm{d}s}E(t_{0})\overset{\eqref{eq::notfasterAss}}{>}0,$

which contradicts Proposition 4.3, since
$\displaystyle\lim_{t\to\infty}E(t)=0.$ Therefore, we conclude that

$\displaystyle\int_{t_{0}}^{\infty}\sqrt{E(t)}\mathrm{d}t=\infty,$ (22)

and by Lemma 4.8 the limit of $t^{\alpha}\sqrt{E(t)}$ for $t\to+\infty$ does
not exist or is not finite for any $\alpha>1$, hence $E(t)\neq
o\left(\frac{1}{t^{\alpha}}\right)$ for $\alpha>1$. ∎

##  5 Algorithms and Numerical Experiments

###  5.1 Practical algorithms from (LD)

We first detail how we discretize (LD). We use an explicit discretization with
fixed step-size $\sqrt{s}>0$: for $k\in\mathbb{N}$ we approximate the solution
$x$ of (LD) at times $t_{k}=k\sqrt{s}$ and define
$x_{k}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}x(t_{k})$. We use the
approximations $\dot{x}(t)\approx\frac{x_{k}-x_{k-1}}{\sqrt{s}}$ and
$\ddot{x}(t)\approx\frac{x_{k+1}-2x_{k}+x_{k-1}}{s}$. We also define the
discrete version of the damping accordingly by first defining

$E_{k}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}f(x_{k})-f^{\star}+\frac{1}{2}\mathop{}\left\lVert\frac{x_{k}-x_{k-1}}{\sqrt{s}}\right\rVert^{2}.$
(23)

and our damping then reads
$\gamma(x_{k},x_{k-1})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sqrt{E_{k}}$.
Using this in (LD) we then propose the following discretization scheme for all
$k\in\mathbb{N}$:

$\begin{split}\frac{x_{k+1}-2x_{k}+x_{k-1}}{s}+\gamma(x_{k},x_{k-1})\frac{x_{k}-x_{k-1}}{\sqrt{s}}+\nabla
f(y_{k})=0\\\ \iff
x_{k+1}=x_{k}+\left(1-\sqrt{s}\gamma(x_{k},x_{k-1})\right)\left[x_{k}-x_{k-1}\right]-s\nabla
f(y_{k}),\end{split}$ (24)

where the gradient $\nabla f$ is evaluated at
$y_{k}=x_{k}+\left(1-\sqrt{s}\gamma(x_{k},x_{k-1})\right)\left[x_{k}-x_{k-1}\right]$,
in the same fashion as it is done in NAG. One can optionally rather evaluate
the gradient at $x_{k}$.

We call the resulting algorithm LYDIA, for LYapunov Damped Inertial Algorithm,
which is summarized in Algorithm 1.

input : $x_{0},x_{-1}\in\mathbb{R}^{n}$, step-size $s>0$,
$k_{\max}\in\mathbb{N}$

1 for  _$k=1$ to $k_{\text{max}}$_ do

2 $y_{k}\leftarrow
x_{k}+\left(1-\frac{\sqrt{E_{k}}}{\sqrt{E_{0}}}\right)\left[x_{k}-x_{k-1}\right]$

3 $x_{k+1}\leftarrow y_{k}-s\nabla f(y_{k})$

4 end for

Algorithm 1 LYDIA

Note that compared to (24), we actually scaled the damping term
$\sqrt{s}\sqrt{E_{k}}$ by $\sqrt{s}\sqrt{E_{0}}$ in Algorithm 1. This scaling
is optional but improves numerical stability111An alternative to scaling is to
choose $s$ so that $\sqrt{s}\sqrt{E_{0}}\leq 1$. as it ensures that the
coefficient in front of $\left[x_{k}-x_{k-1}\right]$ remains non-negative.
More specifically, we have the following lemma that shows that $E_{k}$ is non-
increasing under standard assumptions.

######  Lemma 5.1.

Let $f$ be a continuously differentiable convex functions whose gradient is
Lipschitz continuous with constant $L>0$. Let
$\left(x_{k},y_{k}\right)_{k\in\mathbb{N}}$ be the sequence generated by
Algorithm 1, where $s<\frac{1}{L}$. Then, for all $k\in\mathbb{N}$,

$E_{k+1}\leq E_{k}-\frac{s}{2}\mathop{}\left\lVert\nabla f(x_{k})-\nabla
f(y_{k})\right\rVert^{2}.$ (25)

In particular $\left(E_{k}\right)_{k\in\mathbb{N}}$ is non-increasing, hence
it is a “discrete” Lyapunov function for Algorithm 1.

###### Proof.

Consider for any $x,y\in\mathcal{H}$ and $s\in(0,1/L]$ the following refined
version of the Descent Lemma [5, Remark 5.2.]:

$f(y-s\nabla f(y))\leq f(x)+\mathop{}\left\langle\nabla
f(y),y-x\right\rangle-\frac{s}{2}\mathop{}\left\lVert\nabla
f(y)\right\rVert^{2}-\frac{s}{2}\mathop{}\left\lVert\nabla f(x)-\nabla
f(y)\right\rVert^{2}.$ (26)

Take $y=y_{k}$ and $x=x_{k}$ in (26) and subtract $f^{\star}$ on both sides:

$f(x_{k+1})-f^{\star}\leq f(x_{k})-f^{\star}+\mathop{}\left\langle\nabla
f(y_{k}),y_{k}-x_{k}\right\rangle-\frac{s}{2}\mathop{}\left\lVert\nabla
f(y_{k})\right\rVert^{2}-\frac{s}{2}\mathop{}\left\lVert\nabla f(x_{k})-\nabla
f(y_{k})\right\rVert^{2}.$ (27)

Observe that we have the following identities:

$\displaystyle\mathop{}\left\lVert x_{k+1}-x_{k}\right\rVert^{2}$
$\displaystyle=\mathop{}\left\lVert s\nabla
f(y_{k})-(y_{k}-x_{k})\right\rVert^{2}$
$\displaystyle=s^{2}\mathop{}\left\lVert\nabla
f(y_{k})\right\rVert^{2}-2s\mathop{}\left\langle\nabla
f(y_{k}),y_{k}-x_{k}\right\rangle+\mathop{}\left\lVert
y_{k}-x_{k}\right\rVert^{2},\quad\text{and,}$ (28)
$\displaystyle\mathop{}\left\lVert y_{k}-x_{k}\right\rVert^{2}$
$\displaystyle\stackrel{{\scriptstyle\eqref{algo::LD}}}{{=}}\mathop{}\left\lVert\left(1-\frac{\sqrt{E_{k}}}{\sqrt{E_{0}}}\right)\left(x_{k}-x_{k-1}\right)\right\rVert^{2}.$
(29)

Therefore,

$\displaystyle\mathop{}\left\langle\nabla f(y_{k}),y_{k}-x_{k}\right\rangle=$
$\displaystyle\frac{s}{2}\mathop{}\left\lVert\nabla
f(y_{k})\right\rVert^{2}-\frac{1}{2s}\mathop{}\left\lVert
x_{k+1}-x_{k}\right\rVert^{2}+\frac{1}{2s}\mathop{}\left\lVert
y_{k}-x_{k}\right\rVert^{2}$ $\displaystyle=$
$\displaystyle\frac{s}{2}\mathop{}\left\lVert\nabla
f(y_{k})\right\rVert^{2}-\frac{1}{2s}\mathop{}\left\lVert
x_{k+1}-x_{k}\right\rVert^{2}+\frac{1}{2s}\mathop{}\left\lVert\left(1-\frac{\sqrt{E_{k}}}{\sqrt{E_{0}}}\right)\left(x_{k}-x_{k-1}\right)\right\rVert^{2}.$

Substitute this in (27) to get

$f(x_{k+1})-f^{\star}+\frac{1}{2s}\mathop{}\left\lVert
x_{k+1}-x_{k}\right\rVert^{2}\leq
f(x_{k})-f^{\star}+\frac{1}{2s}\mathop{}\left\lVert\left(1-\frac{\sqrt{E_{k}}}{\sqrt{E_{0}}}\right)\left(x_{k}-x_{k-1}\right)\right\rVert^{2}\\\
-\frac{s}{2}\mathop{}\left\lVert\nabla f(x_{k})-\nabla
f(y_{k})\right\rVert^{2}.$ (30)

Observe that for the first iteration $k=0$, (30) reads

$f(x_{1})-f^{\star}+\frac{1}{2s}\mathop{}\left\lVert
x_{1}-x_{0}\right\rVert^{2}\\\ \leq
f(x_{0})-f^{\star}+\frac{1}{2s}\mathop{}\left\lVert\left(1-\frac{\sqrt{E_{0}}}{\sqrt{E_{0}}}\right)\left(x_{0}-x_{-1}\right)\right\rVert^{2}-\frac{s}{2}\mathop{}\left\lVert\nabla
f(x_{0})-\nabla f(y_{0})\right\rVert^{2}$

which is equivalent to $E_{1}\leq
f(x_{0})-f^{\star}-\frac{s}{2}\mathop{}\left\lVert\nabla f(x_{0})-\nabla
f(y_{0})\right\rVert^{2}$ and therefore

$\displaystyle E_{1}$ $\displaystyle\leq
f(x_{0})-f^{\star}+\frac{1}{2s}\mathop{}\left\lVert
x_{0}-x_{-1}\right\rVert^{2}-\frac{s}{2}\mathop{}\left\lVert\nabla
f(x_{0})-\nabla f(y_{0})\right\rVert^{2}$
$\displaystyle=E_{0}-\frac{s}{2}\mathop{}\left\lVert\nabla f(x_{0})-\nabla
f(y_{0})\right\rVert^{2}.$

So $E_{1}\leq E_{0}$. Let $k\in\mathbb{N}_{>0}$ such that $\forall\ 1\leq
i\leq k,\ E_{i}\leq E_{i-1}$, then in particular $E_{k}\leq E_{0}$ and we
deduce from (29) that:

$\mathop{}\left\lVert\left(1-\frac{\sqrt{E_{k}}}{\sqrt{E_{0}}}\right)\left(x_{k}-x_{k-1}\right)\right\rVert^{2}\leq\mathop{}\left\lVert
x_{k}-x_{k-1}\right\rVert^{2},$ (31)

which simplifies (30) into

$f(x_{k+1})-f^{\star}+\frac{1}{2s}\mathop{}\left\lVert
x_{k+1}-x_{k}\right\rVert^{2}\leq
f(x_{k})-f^{\star}+\frac{1}{2s}\mathop{}\left\lVert
x_{k}-x_{k-1}\right\rVert^{2}-\frac{s}{2}\mathop{}\left\lVert\nabla
f(x_{k})-\nabla f(y_{k})\right\rVert^{2}.$

This is exactly (25) after using (23), hence by induction, (25) holds for all
$k\in\mathbb{N}$. ∎

###  5.2 Numerical experiments

Figure 2: Rate of convergence of LD, AVD, HBF and GD on the test-function
$f_{\text{flat}}$. Left: Evolution of the function values. Right: Evolution of
the Lyapunov function.

Figure 3: Rate of convergence of LD, AVD, HBF and GD on the test-function
$f_{\text{non-KL}}$. Left: Evolution of the function values. Right: Evolution
of the Lyapunov function.

Figure 4: Rate of convergence of LD, AVD, HBF and GD on the test-function
$f_{\text{uneven}}$. Left: Evolution of the function values. Right: Evolution
of the Lyapunov function.

Figure 5: Rate of convergence of LD, AVD, HBF and GD on the test-function
$f_{\text{contmin}}$. Left: Evolution of the function values. Right: Evolution
of the Lyapunov function.

#### Methodology.

We evaluate the performance of our system and empirically corroborate Theorem
1.1. We consider the following 1-dimensional test functions, defined for all
$x\in\mathbb{R}$ by:

$\displaystyle f_{\text{flat}}(x)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}x^{24},$
$\displaystyle f_{\text{non-KL}}(x)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\begin{cases}0,&\text{if
}x=0;\\\ \exp\left({-\frac{1}{x^{2}}}\right),&\text{else},\end{cases}$
$\displaystyle f_{\text{uneven}}(x)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\begin{cases}x^{3},&\text{if
}x>0;\\\ x^{2},&\text{if }x\leq 0,\end{cases}$ $\displaystyle
f_{\text{contmin}}(x)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\begin{cases}(x-\varepsilon)^{2},&\text{if
}x>\varepsilon;\\\ (x+\varepsilon)^{2},&\text{if }x<\varepsilon;\\\
0,&\text{else}.\end{cases}$

Since (LD) and ($\text{AVD}_{a}$) are second-order ODEs that do not have
closed-form solutions in general, we approximate them by using the LYDIA
algorithm and NAG respectively, both with small step-sizes. We take $a=3.1$ in
NAG. We also consider Gradient Descent (GD) and the HBF algorithms mentioned
in the introduction. For each test function222Some of these functions do not
have a globally Lipschitz continuous gradient which could cause numerical
instabilities. We overcome this by using small-enough step-sizes to ensure
boundedness of the iterates of all the algorithms considered., we present the
evolution of the optimality gap $f(x(t))-f^{\star}$ as a function of the time
$t$. Since this value is not monotonous and may oscillate heavily, we also
display the evolution of the (discretized) Lyapunov function $E$.

#### Results.

The function $f_{\text{flat}}$ is a convex polynomial that is very flat around
its minimizer. As discussed in [6, Example 2.12] such polynomials of large
degree allow emphasizing the worst-case bounds on the rates of convergence.
Indeed, we observe on the right of Figure 2 that the rate for GD and HBF is
asymptotically close to $\mathcal{O}\left(\frac{1}{t}\right)$ while that of LD
and ($\text{AVD}_{a}$) gets close to $\mathcal{O}\left(\frac{1}{t^{2}}\right)$
which empirically validates our main result Theorem 1.1.

Some convex functions are not strongly convex but possess the KL property
which allows deriving faster rates of convergence (as done in the closed-loop
setting by [9]). Since Theorem 1.1 does not assume such a property, we
evaluate the algorithms on a function that is known for not having the KL
property on Figure 3. The results again match the theoretical ones. Similarly,
properties such as $f$ being even (i.e., $f(-x)=f(x),\ \forall x$) or
$\operatorname*{\arg\\!\min}_{\mathcal{H}}f$ being a singleton can allow one
to derive faster convergence results than for general convex functions. Our
last-two test functions in Figures 4 and 5 illustrate that the rate of (LD)
also holds without such properties.

Finally, while Figures 2 and 3 evidence cases where the solution of (LD)
yields very fast minimization of function values, Figure 4 shows a case where
(LD) is faster than GD and HBF but not as fast as ($\text{AVD}_{a}$) and
Figure 5 shows a case where (LD) is behind all other methods. Nonetheless, in
all cases observe that $E$ is non-increasing and that it exhibits the rate
predicted by Theorem 1.1.

##  6 Conclusions and Perspectives

We introduced a new system (LD) which, as initially intended, is independent
of the choice of the initial time $t_{0}$, unlike ($\text{AVD}_{a}$), and
which does require the hyper-parameter $a>3$ compared to the latter, but
however assumes knowledge of the optimal value $f^{\star}$. We showed that it
is possible to design closed-loop dampings that achieve near-optimal rates of
convergence for convex optimization. The key ingredient is the coupling
between the damping and the speed of convergence of the system. This yielded
in particular the identity (1), specific to (LD) and essential to adapt the
proofs from the open-loop to the closed-loop setting. This coupling provides a
new understanding on how to choose the damping term in second-order ODEs for
optimization which may prove to be useful beyond the specific cases of (LD)
and ($\text{AVD}_{a}$). We provided numerical experiment corroborating our
theoretical results as well as a new practical first-order algorithm LYDIA,
derived from (LD), and for which we showed that $E$ a still a (discrete)
Lyapunov function.

As for future work, it remains open to know whether we can improve the rate
from “arbitrarily close to optimal” to optimal (i.e., can we take $\delta=0$
in Theorem 1.1?). We also suspect that one can drop Assumption 2-(ii) as it is
not required for ($\text{AVD}_{a}$) [24, 21], but we could not yet do it in
the closed-loop setting. On the algorithmic side, our experiments suggest that
the rate of (LD) is transferred to the LYDIA algorithm, which remains to be
shown. One might also consider other discretization schemes. Finally, it is
worth investigating whether one can find systems and algorithms with the same
properties that do not require the optimal value $f^{\star}$.

## Acknowledgment

C. Castera and P. Ochs are supported by the ANR-DFG joint project TRINOM-DS
under number DFG-OC150/5-1.

Appendices

##  Appendix A Proof of Existence and Uniqueness

This section is devoted to proving Theorem 3.1. We recall some result from the
theory of ODEs.

######  Theorem A.1.

[29, Theorem 4.2.6] (Classical Version of Picard–Lindelöf)
Let $\mathcal{H}$ be a Hilbert space, let
$\Omega\subseteq\mathbb{R}\times\mathcal{H}$ be open. Let
$G:\Omega\rightarrow\mathcal{H}$ be continuous and let
$\left(t_{0},x_{0}\right)\in\Omega$. Assume that there exists $L\geq 0$ such
that for all $(t,x),(t,y)\in\Omega$ we have

$\mathop{}\left\lVert G(t,x)-G(t,y)\right\rVert\leq L\mathop{}\left\lVert
x-y\right\rVert.$

Then, there exists $\delta>0$ such that the initial value problem

$\left\\{\begin{array}[]{l}u^{\prime}(t)=G(t,u(t))\quad\left(t\in\left(t_{0},t_{0}+\delta\right)\right),\\\
u\left(t_{0}\right)=x_{0},\end{array}\right.$

admits a unique continuously differentiable solution
$u:\left[t_{0},t_{0}+\delta\right[\rightarrow\mathcal{H}$, which satisfies
$(t,u(t))\in\Omega$ for all $t\in\left[t_{0},t_{0}+\delta\right[$.

######  Definition 3.

[26, Definition 3.20] Let $\phi:I\to\mathbb{R}^{n}$, $n\in\mathbb{N}$, be a
solution to an ODE defined on some open interval $I\subset\mathbb{R}$.

  1. (a)

We say $\phi$ admits an extension or continuation to the right (resp. to the
left) if, and only if, there exists a solution $\psi:J\to\mathbb{R}^{n}$ to
the same ODE, defined on some open interval $J\supset I$ such that
$\psi|_{I}=\phi$ and

$\sup J>\sup I\quad(\text{resp.\ }\inf J<\inf I)$

An extension or continuation of $\phi$ is a function that is an extension to
the right or an extension to the left (or both).

  2. (b)

The solution $\phi$ is called a _maximal_ solution if, and only if, it does
not admit any extension in the sense defined in (a).

######  Theorem A.2.

[26, Theorem 3.22] Every solution $\phi_{0}:I_{0}\to\mathbb{R}^{n}$ to some
ODE, defined on an open interval $I_{0}\subset\mathbb{R}$, can be extended to
a maximal solution of this ODE.

######  Remark A.3.

Definition 3 is easily generalized to Hilbert spaces and Theorem A.2 is valid
for an ODE in an infinite dimensional space as well, since the proof relies on
Zorn’s Lemma.

###### Proof of Theorem 3.1.

We first reduce the system (LD) to an equivalent first-order system:

$\frac{\mathrm{d}}{\mathrm{d}t}\begin{pmatrix}x(t)\\\
\dot{x}(t)\end{pmatrix}=\begin{pmatrix}\dot{x}(t)\\\
-\sqrt{f(x(t))-f^{\star}+\frac{1}{2}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}}\dot{x}(t)-\nabla
f(x(t))\end{pmatrix}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}G(t,(x(t),\dot{x}(t))).$
(32)

We first show the claim in the case
$\operatorname*{\arg\\!\min}_{\mathcal{H}}f\neq\emptyset$ and later for the
case $\operatorname*{\arg\\!\min}_{\mathcal{H}}f=\emptyset$.

First, if
$\left(x_{0},\dot{x}_{0}\right)\in\operatorname*{\arg\\!\min}_{\mathcal{H}}f\times\left\\{0\right\\}$,
then $(x(t),\dot{x}(t))\equiv(x_{0},0)$ is the unique global solution, since
$\ddot{x}(t)=0$ for all $t\geq t_{0}$. Now assume that
$\left(x_{0},\dot{x}_{0}\right)\not\in\operatorname*{\arg\\!\min}_{\mathcal{H}}f\times\left\\{0\right\\}$
and let us check that for all $t\geq t_{0}$, the function

$(u,v)\mapsto G(t,(u,v))=\begin{pmatrix}v\\\
-\sqrt{f(u)-f^{\star}+\frac{1}{2}\mathop{}\left\lVert
v\right\rVert^{2}}v(t)-\nabla f(u)\end{pmatrix}$

is Lipschitz continuous on the open set

$\mathcal{A}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}(\mathcal{H}\times\mathcal{H})\setminus(\operatorname*{\arg\\!\min}_{\mathcal{H}}f\times\left\\{0\right\\}).$

The first coordinate of $G$ is clearly locally Lipschitz continuous w.r.t.
$(u,v)$ and therefore it suffices to check that the second coordinate of $G$
is also locally Lipschitz continuous w.r.t. $(u,v)$ on $\mathcal{A}$.
The square root function is locally Lipschitz continuous everywhere except at
0 and $f(u)-f^{\star}+\frac{1}{2}\mathop{}\left\lVert v\right\rVert^{2}\neq 0$
for all $(u,v)\in\mathcal{A}$. Therefore
$(u,v)\in\mathcal{A}\mapsto\sqrt{f(u)-f^{\star}+\frac{1}{2}\mathop{}\left\lVert
v\right\rVert^{2}}v$ is locally Lipschitz continuous as a product of locally
Lipschitz-continuous functions. Finally $\nabla f$ is locally Lipschitz
continuous by Assumption 1-(i) , hence $G$ is locally Lipschitz continuous on
$\mathcal{A}$. We can now apply the Picard–Lindelöf Theorem A.1 to any open
and bounded neighborhood of the initial conditions
$(t_{0},(x_{0},\dot{x}_{0}))$ to find some $\delta>0$ and a unique solution
$(x,\dot{x})$ to (32) on $[t_{0},t_{0}+\delta[$.

It now remains to show that the solution exists on $[t_{0},+\infty[$. Let
$T\in\,]t_{0},+\infty]$ be the maximal time of existence (as stated in Theorem
A.2) of the solution $(x,\dot{x})$ of (32). Assume that $T<+\infty$, then the
limits of $x$ and $\dot{x}(t)$ exist as $t\to T$. Indeed, first note that the
uniform boundedness of $E$ implies that $\dot{x}$ is bounded on $[t_{0},T[$
and by (LD) $\ddot{x}$ is bounded on $[t_{0},T[$ as well. Now consider a
Cauchy sequence $\left(t_{n}\right)_{n\in\mathbb{N}}$ converging to $T$ and
let $m,n\in\mathbb{N}$. Then by the mean value Theorem we have:

$\begin{split}\mathop{}\left\lVert
x(t_{n})-x(t_{m})\right\rVert&\leq\sup_{s\in]t_{0},T[}\mathop{}\left\lVert\dot{x}(s)\right\rVert\left|t_{n}-t_{m}\right|,\text{
and}\\\
\mathop{}\left\lVert\dot{x}(t_{n})-\dot{x}(t_{m})\right\rVert&\leq\sup_{s\in]t_{0},T[}\mathop{}\left\lVert\ddot{x}(s)\right\rVert\left|t_{n}-t_{m}\right|.\end{split}$

Therefore $\left(x(t_{n})\right)_{n\in\mathbb{N}}$ and
$\left(\dot{x}(t_{n})\right)_{n\in\mathbb{N}}$ are Cauchy sequences which
implies that $\displaystyle\lim_{t\to T}x(t)\text{ and }\lim_{t\to
T}\dot{x}(t)$ exist.

Then, if $(x(T),\dot{x}(T))\in\mathcal{A}$ then we can extend the solution by
applying Picard–Lindelöf to an open and bounded neighborhood of
$\left((T,\left(x(T),\dot{x}(T)\right)\right)$ which contradicts the fact that
$T$ was the maximal time of existence. If
$(x(T),\dot{x}(T))\in\partial\mathcal{A}\subset\operatorname*{\arg\\!\min}_{\mathcal{H}}f\times\left\\{0\right\\}$,
where $\partial\mathcal{A}$ denotes the boundary of $\mathcal{A}$, then
$\ddot{x}(T)=0$ and we can extend the solution on $[T,T+\delta[$, for some
$\delta>0$, by taking $(x(t),\dot{x}(t))=(x(T),0)$. This is again a
contradiction, therefore we necessarily have $T=+\infty$.

Finally, in the case where
$\operatorname*{\arg\\!\min}_{\mathcal{H}}f=\emptyset$, we see similarly to
before that $G(t,(u,v))$ is locally Lipschitz continuous w.r.t. $(u,v)$
everywhere on $\mathcal{H}\times\mathcal{H}$. So the Picard–Lindelöf Theorem
implies the existence of a unique local solution for any initial value, which
we can again extend to a global solution on $[t_{0},+\infty[$. ∎

##  Appendix B Missing Proofs of Lemmas

###### Proof of Lemma 4.4.

Assume that there exists $c>0$ such that
$\displaystyle\lim_{t\to+\infty}g(t)=c$, which implies the existence of
$t_{1}\geq t_{0}$ such that $\forall t\geq t_{1}$, $g(t)\geq\frac{c}{2}$. Then

$\int_{t_{0}}^{+\infty}g(t)\mathrm{d}t\geq\int_{t_{1}}^{+\infty}g(t)\mathrm{d}t\geq\int_{t_{1}}^{+\infty}\frac{c}{2}\mathrm{d}t=+\infty,$

which contradicts the assumption that
$\int_{t_{0}}^{+\infty}g(t)\mathrm{d}t<+\infty$. ∎

###### Proof of Lemma 4.5.

Denote the positive and negative parts of a function $g$ by

$\left[g(\cdot)\right]_{+}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\max(g(\cdot),0)\text{
and
}\left[g(\cdot)\right]_{-}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\max(-g(\cdot),0)\geq
0,$

so that $\forall x\in\mathcal{H}$,

$g(x)=\left[g(x)\right]_{+}-\left[g(x)\right]_{-}.$

Then note that

$\left[\left(t^{\alpha+1}E(t)\right)^{\prime}\right]_{+}\overset{\eqref{eq::derE}}{=}\left[(\alpha+1)t^{\alpha}E(t)-t^{\alpha+1}\sqrt{E(t)}\mathop{}\left\lVert\dot{x}(t)\right\rVert^{2}\right]_{+}=(\alpha+1)t^{\alpha}E(t),$
(33)

and that,

$\begin{split}\int_{t_{0}}^{+\infty}\left(t^{\alpha+1}E(t)\right)^{\prime}\mathrm{d}t&=\int_{t_{0}}^{+\infty}\left[\left(t^{\alpha+1}E(t)\right)^{\prime}\right]_{+}-\left[\left(t^{\alpha+1}E(t)\right)^{\prime}\right]_{-}\mathrm{d}t\\\
&\leq\int_{t_{0}}^{+\infty}\left[\left(t^{\alpha+1}E(t)\right)^{\prime}\right]_{+}\mathrm{d}t\overset{\eqref{eq::integrable_little0_1}}{=}(\alpha+1)\int_{t_{0}}^{+\infty}t^{\alpha}E(t)\mathrm{d}t\overset{Ass.}{<}+\infty.\end{split}$
(34)

Therefore by definition of the improper integral,
$\displaystyle\lim_{t\to+\infty}t^{\alpha+1}E(t)$ admits a finite limit
$l\in\mathbb{R}_{\geq 0}$.

Now, assume that $l>0$, then for any $\varepsilon\in]0,l[$ there exists
$t_{1}\geq t_{0}$ such for all $t\geq t_{1}$ we have
$E(t)>\frac{l-\varepsilon}{t^{\alpha+1}}$. Then,

$\int_{t_{0}}^{+\infty}t^{\alpha}E(t)\mathrm{d}t\geq\int_{t_{1}}^{+\infty}t^{\alpha}E(t)\mathrm{d}t>\int_{t_{1}}^{+\infty}t^{\alpha}\frac{l-\varepsilon}{t^{\alpha+1}}\mathrm{d}t=(l-\varepsilon)\int_{t_{1}}^{+\infty}\frac{1}{t}\mathrm{d}t=+\infty,$

which contradicts the integrability assumption on $t^{\alpha}E(t)$. ∎

###### Proof of Lemma 4.8.

Let
$l\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\displaystyle\lim_{t\to\infty}t^{\beta}g(t)\geq
0$. Then for any $\varepsilon>0$ we can find $t_{1}\geq t_{0}$ such that
$\forall t\geq t_{1}$,

$g(t)\leq\frac{(l+\varepsilon)}{t^{\beta}}\ .$

Therefore,

$\int_{t_{0}}^{+\infty}g(t)\mathrm{d}t=\underset{\stackrel{{\scriptstyle\mathrm{def}}}{{=}}I<+\infty}{\underbrace{\int_{t_{0}}^{t_{1}}g(t)\mathrm{d}t}}+\int_{t_{1}}^{+\infty}g(t)\mathrm{d}t\leq
I+(l+\varepsilon)\int_{t_{1}}^{+\infty}\frac{1}{t^{\beta}}\mathrm{d}t<+\infty,$

since $\beta>1$, which proves the result. ∎

## References

  * Adly et al. [2006] Samir Adly, Hedy Attouch, and Alexandre Cabot.  Finite time stabilization of nonlinear oscillators subject to dry friction.  In _Nonsmooth Mechanics and Analysis_ , pages 289–304, 2006.
  * Alecsa et al. [2021] Cristian Daniel Alecsa, Szilárd Csaba László, and Titus Pinţa.  An extension of the second order dynamical system that models Nesterov’s convex gradient method.  _Applied Mathematics & Optimization_, 84:1687–1716, 2021\.
  * Alvarez et al. [2002] Felipe Alvarez, Hedy Attouch, Jérôme Bolte, and Patrick Redont.  A second-order gradient-like dissipative dynamical system with Hessian-driven damping: Application to optimization and mechanics.  _Journal de mathématiques pures et appliquées_ , 81(8):747–779, 2002.
  * Attouch and Cabot [2017] Hedy Attouch and Alexandre Cabot.  Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity.  _Journal of Differential Equations_ , 263(9):5412–5458, 2017.
  * Attouch and Fadili [2022] Hedy Attouch and Jalal Fadili.  From the Ravine method to the Nesterov method and vice versa: a dynamical system perspective.  _SIAM Journal on Optimization_ , 32(3):2074–2101, 2022.
  * Attouch et al. [2015] Hedy Attouch, Zaki Chbani, Juan Peypouquet, and Patrick Redont.  Fast convergence of inertial dynamics and algorithms with asymptotic vanishing damping.  _Mathematical Programming_ , 168:123–175, 2015.
  * Attouch et al. [2016] Hedy Attouch, Juan Peypouquet, and Patrick Redont.  Fast convex optimization via inertial dynamics with Hessian driven damping.  _Journal of Differential Equations_ , 261(10):5734–5783, 2016.
  * Attouch et al. [2019] Hedy Attouch, Zaki Chbani, and Hassan Riahi.  Rate of convergence of the Nesterov accelerated gradient method in the subcritical case $\alpha\leq$ 3\.  _ESAIM: Control, Optimisation and Calculus of Variations_ , 25:2, 2019.
  * Attouch et al. [2022] Hedy Attouch, Radu Ioan Boţ, and Ernö Robert Csetnek.  Fast optimization via inertial dynamics with closed-loop damping.  _Journal of the European Mathematical Society_ , 25(5):1985–2056, 2022.
  * Attouch et al. [2023] Hedy Attouch, Radu Ioan Boţ, and Dang-Khoa Nguyen.  Fast convex optimization via closed-loop time scaling of gradient dynamics.  _arXiv preprint arXiv:2301.00701_ , 2023.
  * Aujol and Dossal [2017] Jean-François Aujol and Charles Dossal.  Optimal rate of convergence of an ODE associated to the fast gradient descent schemes for $b>0$.  _HAL Preprint hal-01547251_ , 2017.
  * Aujol et al. [2019] Jean-Francois Aujol, Charles Dossal, and Aude Rondepierre.  Optimal convergence rates for Nesterov acceleration.  _SIAM Journal on Optimization_ , 29(4):3131–3153, 2019.
  * Benaïm et al. [2005] Michel Benaïm, Josef Hofbauer, and Sylvain Sorin.  Stochastic approximations and differential inclusions.  _SIAM Journal on Control and Optimization_ , 44(1):328–348, 2005.
  * Boyd et al. [2003] Stephen Boyd, Lin Xiao, and Almir Mutapcic.  Subgradient methods.  _Lecture notes of EE392o, Stanford University_ , 2003.
  * Cabot and Frankel [2012] Alexandre Cabot and Pierre Frankel.  Asymptotics for some semilinear hyperbolic equations with non-autonomous damping.  _Journal of Differential Equations_ , 252(1):294–322, 2012.
  * Cabot et al. [2009] Alexandre Cabot, Hans Engler, and Sébastien Gadat.  On the long time behavior of second order differential equations with asymptotically small dissipation.  _Transactions of the American Mathematical Society_ , 361(11):5983–6017, 2009.
  * Chambolle and Dossal [2015] Antonin Chambolle and Charles Dossal.  On the convergence of the iterates of the “fast iterative shrinkage/thresholding algorithm”.  _Journal of Optimization theory and Applications_ , 166:968–982, 2015.
  * Cybenko [1989] George Cybenko.  Approximation by superpositions of a sigmoidal function.  _Mathematics of control, signals and systems_ , 2(4):303–314, 1989.
  * Grobman [1959] David M Grobman.  Homeomorphism of systems of differential equations.  _Doklady Akademii Nauk SSSR_ , 128(5):880–881, 1959.
  * Hartman [1960] Philip Hartman.  A lemma in the theory of structural stability of differential equations.  _Proceedings of the American Mathematical Society_ , 11(4):610–620, 1960.
  * Jendoubi and May [2015] Mohamed Ali Jendoubi and Ramzi May.  Asymptotics for a second-order differential equation with nonautonomous damping and an integrable source term.  _Applicable Analysis_ , 94(2):435–443, 2015.
  * Lin and Jordan [2022] Tianyi Lin and Michael I Jordan.  A control-theoretic perspective on optimal high-order optimization.  _Mathematical Programming_ , 195(1):929–975, 2022\.
  * Ljung [1977] Lennart Ljung.  Analysis of recursive stochastic algorithms.  _IEEE transactions on automatic control_ , 22(4):551–575, 1977.
  * May [2017] Ramzi May.  Asymptotic for a second-order evolution equation with convex potential and vanishing damping term.  _Turkish Journal of Mathematics_ , 41(3):681–685, 2017.
  * Nesterov [1983] Yurii Nesterov.  A method of solving a convex programming problem with convergence rate O$\left(\frac{1}{k^{2}}\right)$.  In _Doklady Akademii Nauk_ , volume 269(3), pages 543–547, 1983.
  * Philip [2023] Peter Philip.  Ordinary differential equations, lecture notes, 2023.  URL https://www.math.lmu.de/~philip/publications/lectureNotes/philipPeter_ODE.pdf.  [Online; accessed 17.07.2023].
  * Polyak [1987] Boris Polyak.  _Introduction to optimization_.  New York, Optimization Software, 1987.
  * Polyak [1964] B.T. Polyak.  Some methods of speeding up the convergence of iteration methods.  _USSR Computational Mathematics and Mathematical Physics_ , 4(5):1–17, 1964.
  * Seifert et al. [2022] Christian Seifert, Sascha Trostorff, and Marcus Waurick.  _Evolutionary Equations: Picard’s Theorem for Partial Differential Equations, and Applications_.  Springer Nature, 2022.
  * Shi et al. [2021] Bin Shi, Simon S Du, Michael I Jordan, and Weijie J Su.  Understanding the acceleration phenomenon via high-resolution differential equations.  _Mathematical Programming_ , 195(1):79–148, 2021\.
  * Su et al. [2014] Weijie Su, Stephen Boyd, and Emmanuel Candes.  A differential equation for modeling Nesterov’s accelerated gradient method: Theory and insights.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , volume 27, pages 1–9. Curran Associates, Inc., 2014.
  * Wibisono et al. [2016] Andre Wibisono, Ashia C Wilson, and Michael I Jordan.  A variational perspective on accelerated methods in optimization.  _Proceedings of the National Academy of Sciences_ , 113(47):E7351–E7358, 2016.
  * Wilson et al. [2021] Ashia C Wilson, Ben Recht, and Michael I Jordan.  A Lyapunov analysis of accelerated methods in optimization.  _Journal of Machine Learning Research_ , 22(1):5040–5073, 2021.