Convergence and Dynamical Behavior of the ADAM Algorithm for Non-Convex Stochastic Optimization

Introduction

To alleviate these limitations, the popular Adam algorithm adjusts the learning rate coordinate-wise, as a function of the past values of the squared gradient vectors’ coordinates. The algorithm thus combines the assets of inertial methods with an adaptive per-coordinate learning rate selection. Finally, the algorithm includes a so-called bias correction step. Acting on the current estimate of the gradient vector, this step is especially useful during the early iterations.

Despite the growing popularity of the algorithm, only few works investigate its behavior from a theoretical point of view (see the discussion in Section 6). The present paper studies the convergence of Adam from a dynamical system viewpoint.

We introduce a continuous-time version of the Adam algorithm under the form of a non-autonomous ordinary differential equation (ODE). Building on the existence of an explicit Lyapunov function for the ODE, we show the existence of a unique global solution to the ODE. This first result turns out to be non-trivial due to the irregularity of the vector field. We then establish the convergence of the continuous-time Adam trajectory to the set of critical points of the objective function $F$. The proposed continuous-time version of Adam provides useful insights on the effect of the bias correction step. It is shown that, close to the origin, the objective function $F$ is non-increasing along the Adam trajectory, suggesting that early iterations of Adam can only improve the initial guess.

Under a Łojasiewicz-type condition, we prove that the solution to the ODE converges to a single critical point of the objective function $F$. We provide convergence rates in this case.

In discrete time, we first analyze the Adam iterates in the constant stepsize regime as originally introduced in . In this work, it is shown that the discrete-time Adam iterates shadow the behavior of the non-autonomous ODE in the asymptotic regime where the stepsize parameter $\gamma$ of Adam is small. More precisely, we consider the interpolated process ${\mathsf{z}}^{\gamma}(t)$ which consists of a piecewise linear interpolation of the Adam iterates. The random process ${\mathsf{z}}^{\gamma}$ is indexed by the parameter $\gamma$, which is assumed constant during the whole run of the algorithm. In the space of continuous functions on $[0,+\infty)$ equipped with the topology of uniform convergence on compact sets, we establish that ${\mathsf{z}}^{\gamma}$ converges in probability to the solution to the non-autonomous ODE when $\gamma$ tends to zero.

Under a stability condition, we prove the asymptotic ergodic convergence of the probability of the discrete-time Adam iterates to approach the set of critical points of the objective function in the doubly asymptotic regime where $n\to\infty$ then $\gamma\to 0$.

Beyond the original constant stepsize Adam , we propose a decreasing stepsize version of the algorithm. We provide sufficient conditions ensuring the stability and the almost sure convergence of the iterates towards the critical points of the objective function.

We establish a convergence rate of the stochastic iterates of the decreasing stepsize algorithm under the form of a conditional central limit theorem.

We claim that our analysis can be easily extended to other adaptive algorithms such as e.g. RmsProp or AdaGrad and AmsGrad (see Section 6).

The paper is organized as follows. In Section 2, we present the Adam algorithm and the main assumptions. Our main results are stated in Sections 3 to 5. We provide a review of related works in Section 6. The rest of the paper addresses the proofs of our results (Sections 7 to 9).

The Adam Algorithm

It satisfies: $z_{n}=T_{\gamma,\alpha,\beta}(n,z_{n-1},\xi_{n})\,,$ for every $n\geq 1$, where for every $z=(x,m,v)$ in ${{\mathcal{Z}}}_{+}$, $\xi\in\Xi$,

The iterates $z_{n}$ form a non-homogeneous Markov chain, because $T_{\gamma,\alpha,\beta}(n,z,\xi)$ depends on $n$. This is due to the so-called debiasing step, which consists of replacing $m_{n},v_{n}$ in Algorithm 1 by their “debiased” versions $\hat{m}_{n},\hat{v}_{n}$. The motivation becomes clear when expanding the expression:

From this equation, it is observed that, $\hat{m}_{n}$ forms a convex combination of the past gradients. This is unlike $m_{n}$, which may be small during the first iterations.

For almost every $\xi$, the map $f(\,.\,,\xi)$ is continuously differentiable.

2 Asymptotic Regime

We address the constant stepsize regime, where $\gamma$ is fixed along the iterations (the default value recommended in is $\gamma=0.001$). As opposed to the decreasing stepsize context, the sequence $z_{n}^{\gamma}:=z_{n}$ cannot in general converge as $n$ tends to infinity, in an almost sure sense. Instead, we investigate the asymptotic behavior of the family of processes $(n\mapsto z_{n}^{\gamma})_{\gamma>0}$ indexed by $\gamma$, in the regime where $\gamma\to 0$. We use the so-called ODE method (see e.g. ). The interpolated process ${\mathsf{z}}^{\gamma}$ is the piecewise linear function defined on $[0,+\infty)\to{{\mathcal{Z}}}_{+}$ for all $t\in[n\gamma,(n+1)\gamma)$ by:

We establish the convergence in probability of the family of random processes $({\mathsf{z}}^{\gamma})_{\gamma>0}$ as $\gamma$ tends to zero, towards a deterministic continuous-time system defined by an ODE. The latter ODE, which we provide below at Eq. (ODE), will be referred to as the continuous-time version of Adam.

the initialization being chosen as $z_{0}^{\gamma}=(x_{0},0,0)$.

Continuous-Time System

In order to gain insight into the behavior of the sequence $(z_{n}^{\gamma})$ defined by (5), it is convenient to rewrite the Adam iterations under the following equivalent form, for every $n\geq 1$:

where we define for every $\gamma>0$, $z\in{{\mathcal{Z}}}_{+}$,

where $a,b$ are the constants defined in Assumption 2.2. We prove that, for any fixed $(t,z)$, the quantity $h(t,z)$ coincides with the limit of $h_{\gamma}(\lfloor t/\gamma\rfloor,z)$ as $\gamma\downarrow 0$. This remark along with Eq. (6) suggests that, as $\gamma\downarrow 0$, the interpolated process ${\mathsf{z}}^{\gamma}$ shadows the non-autonomous differential equation

2 Existence, Uniqueness, Convergence

Since $h(\,.\,,z)$ is non-continuous at point zero for a fixed $z\in{{\mathcal{Z}}}_{+}$, and since $h(t,\,.\,)$ is not locally Lipschitz continuous for a fixed $t~{}>~{}0$, the existence and uniqueness of the solution to (ODE) do not stem directly from off-the-shelf theorems.

Let $x_{0}$ be fixed. A continuous map $z:[0,+\infty)\to{{\mathcal{Z}}}_{+}$ is said to be a global solution to (ODE) with initial condition $(x_{0},0,0)$ if $z$ is continuously differentiable on $(0,+\infty)$, if Eq. (ODE) holds for all $t>0$, and if $z(0)=(x_{0},0,0)$.

Let Assumptions 2.1 to 2.2 hold true. There exists a unique global solution $z:[0,+\infty)\to{{\mathcal{Z}}}_{+}$ to (ODE) with initial condition $(x_{0},0,0)$. Moreover, $z([0,+\infty))$ is a bounded subset of ${{\mathcal{Z}}}_{+}$.

On the other hand, we note that a solution may not exist for an initial point$(x_{0},m_{0},v_{0})$ with arbitrary (non-zero) values of $m_{0},v_{0}$.

Let Assumptions 2.1 to 2.2 hold true. Assume that $F({{\mathcal{S}}})$ has an empty interior. Let $z:t\mapsto(x(t),m(t),v(t))$ be the global solution to (ODE) with the initial condition $(x_{0},0,0)$. Then, the set ${{\mathcal{S}}}$ is non-empty and $\lim_{t\to\infty}{{\mathsf{d}}}(x(t),{{\mathcal{S}}})=0$, $\lim_{t\to\infty}m(t)=0$, $\lim_{t\to\infty}S(x(t))-v(t)=0$.

Then, $t\mapsto V(t,z(t))$ is decreasing if $z(\cdot)$ is the global solution to (ODE).

Cost decrease at the origin. As $F$ itself is not a Lyapunov function for (ODE), there is no guarantee that $F(x(t))$ is decreasing w.r.t. $t$. Nevertheless, the statement holds at the origin. Indeed, it can be shown that $\lim_{t\downarrow 0}V(t,z(t))=F(x_{0})$ (see Prop. 7.7). As a consequence,

In other words, the (continuous-time) Adam procedure can only improve the initial guess $x_{0}$. This is the consequence of the so-called bias correction steps in Adam (see Algorithm 1) . If these debiasing steps were deleted in the Adam iterations, the early stages of the algorithm could degrade the initial estimate $x_{0}$.

Derivatives at the origin. The proof of Th. 3.1 reveals that the initial derivative is given by $\dot{x}(0)=-\nabla F(x_{0})/(\varepsilon+\sqrt{S(x_{0})})$ (see Lemma 7.1). In the absence of debiasing steps, the initial derivative $\dot{x}(0)$ would be a function of the initial parameters $m_{0}$, $v_{0}$, and the user would be required to tune these hyperparameters. No such tuning is required thanks to the debiasing step. When $\varepsilon$ is small and when the variance of $\nabla f(x_{0},\xi)$ is small (i.e., $S(x_{0})\simeq\nabla F(x_{0})^{\odot 2}$), the initial derivative $\dot{x}(0)$ is approximately equal to $-\nabla F(x_{0})/|\nabla F(x_{0})|$. This suggests that in the early stages of the algorithm, the Adam iterations are comparable to the sign variant of the gradient descent, the properties of which were discussed in previous works, see .

3 Convergence rates

In this paragraph, we establish the convergence to a single critical point of $F$ and quantify the convergence rate, using the following assumption . {assumption}[Łojasiewicz property] For any $x^{*}\in{\mathcal{S}}$, there exist $c>0\,,\sigma>0$ and $\theta\in(0,\frac{1}{2}]$ s.t.

Assumption 3.3 holds for real-analytic functions and semialgebraic functions. We refer to for a discussion and a review of applications. We will call any $\theta$ satisfying (12) for some $c,\sigma>0$, as a Łojasiewicz exponent of $f$ at $x^{*}$. The next result establishes the convergence of the function $x(t)$ generated by the ODE to a single critical point of $f$, and provides the convergence rate as a function of the Łojasiewicz exponent of $f$ at this critical point. The proof is provided in subsection 7.4.

Moreover, if $\theta\in(0,\frac{1}{2}]$ is a Łojasiewicz exponent of $f$ at $x^{*}$, there exists a constant $C>0$ s.t. for all $t\geq 0$,

Discrete-Time System: Convergence of Adam

The sequence $(\xi_{n}:n\geq 1)$ is iid, with the same distribution as $\xi$.

Let $p>0$. Assume either one of the following conditions.

The value of $p$ will be specified in the sequel, in the statement of the results. Clearly, Assumption 4 ii is stronger than Assumption 4 i. We shall use either the latter or the former in our statements.

Convergence in the long run. When the stepsize $\gamma$ is constant, the sequence $(x_{n}^{\gamma})$ cannot converge in the almost sure sense as $n\to\infty$. Convergence may only hold in the doubly asymptotic regime where $n\to\infty$ then $\gamma\to 0$.

A Decreasing Stepsize Adam Algorithm

Adam inherently uses constant stepsizes. Consequently, the iterates (5) do not converge in the almost sure sense. In order to achieve convergence, we introduce in this section a decreasing stepsize version of Adam. The iterations are given in Algorithm 2.

where for every $n,k$, $\rho_{n,k}=\alpha_{n}\cdots\alpha_{k+1}(1-\alpha_{k})$. A similar equation holds for $\hat{v}_{n}$.

2 Almost sure convergence

$\sum_{n}\gamma_{n}=+\infty$ and $\sum_{n}\gamma_{n}^{2}<+\infty$,

There exist $a,b$ s.t. $0<b<4a$, $\gamma_{n}^{-1}(1-\alpha_{n})\to a$ and $\gamma_{n}^{-1}(1-\beta_{n})\to b$ .

Th. 5.1 establishes the almost sure convergence of $x_{n}$ to the set of critical points of $F$, under the assumption that the sequence $((x_{n},m_{n},v_{n}))$ is a.s. bounded. The next result provides a sufficient condition under which almost sure boundedness holds. {assumption} The following holds.

We assume the condition: $\lim\sup_{n\to\infty}\left(\frac{1}{\gamma_{n}}-\left(\frac{1-\alpha_{n+2}}{1-\alpha_{n+1}}\right)\frac{1}{\gamma_{n+1}}\right)<2(a-\frac{b}{4})\,,$ which is satisfied for instance if $b<4a$ and $1-\alpha_{n+1}=a\gamma_{n}$.

3 Central Limit Theorem

Let $x^{*}\in{{\mathcal{S}}}$. There exists a neighborhood ${{\mathcal{V}}}$ of $x^{*}$ s.t.

$F$ is twice continuously differentiable on ${{\mathcal{V}}}$, and the Hessian $\nabla^{2}F(x^{*})$ of $F$ at $x^{*}$ is positive definite.

$S$ is continuously differentiable on ${{\mathcal{V}}}$.

Define $D:=\textrm{diag}\left((\varepsilon+\sqrt{S_{1}(x^{*})})^{-1},\cdots,(\varepsilon+\sqrt{S_{d}(x^{*})})^{-1}\right)\,.$ Let $P$ be an orthogonal matrix s.t. the following spectral decomposition holds:

where $\lambda_{1},\cdots,\lambda_{d}$ are the (positive) eigenvalues of $D^{1/2}\nabla^{2}F(x^{*})D^{1/2}$. Define

where $I_{d}$ represents the $d\times d$ identity matrix and $\nabla S(x^{*})$ is the Jacobian matrix of $S$ at $x^{*}$. The largest real part of the eigenvalues of $H$ coincides with $-L$, where

There exist $\kappa\in(0,1]$, $\gamma_{0}>0$, s.t. the sequence $(\gamma_{n})$ satisfies $\gamma_{n}={\gamma_{0}}/{(n+1)^{\kappa}}$ for all $n$. If $\kappa=1$, we assume moreover that $\gamma_{0}>\frac{1}{2L}$.

The sequences $\left(\frac{1}{\gamma_{n}}(\frac{1-\alpha_{n}}{\gamma_{n}}-a)\right)$ and $\left(\frac{1}{\gamma_{n}}(\frac{1-\beta_{n}}{\gamma_{n}}-b)\right)$ are bounded.

The variable $v_{n}$ has an impact on the limiting covariance $\Sigma_{1}$ through its limit $S(x^{*})$ (used to define $D$), but the fluctuations of $v_{n}$ and the parameter $b$ have no effect on $\Sigma_{1}$. As a matter of fact, $\Sigma_{1}$ coincides with the limiting covariance matrix that would have been obtained by considering iterates of the form

which can be interpreted as a preconditioned version of the stochastic heavy ball algorithm . Of course, the above iterates are not implementable because the preconditioning matrix $D$ is unknown.

When $a$ is large, $\Sigma_{1}$ is close to the matrix $\Sigma_{1}^{(0)}$ obtained when letting $a\to+\infty$ in Eq. (17). The matrix $\Sigma_{1}^{(0)}$ is the solution to the Lyapunov equation

The matrix $\Sigma_{1}^{(0)}$ can be interpreted as the asymptotic covariance matrix of the $x$-variable in the absence of the inertial term (that is, when one considers RmsProp instead of Adam). The matrix $\Sigma_{1}^{(0)}$ approximates $\Sigma_{1}$ in the sense that $\Sigma_{1}=\Sigma_{1}^{(0)}+\frac{1}{a}\Delta+O(\frac{1}{a^{2}})$ for some symmetric matrix $\Delta$ which can be explicited. The matrix $\Delta$ is neither positive nor negative definite in general. This suggests that the question of the potential benefit of the presence of an inertial term is in general problem dependent.

In the statement of Th. 5.3, the conditioning event $\{z_{n}\to z^{*}\}$ can be replaced by the event $\{x_{n}\to x^{*}\}$ under the additional assumption that $\sum_{n}\gamma_{n}^{2}<+\infty$.

Related Works

Although the idea of adapting the (per-coordinate) learning rates as a function of past gradient values is not new (see e.g. variable metric methods such as the BFGS algorithms), AdaGrad led the way to a new class of algorithms that are sometimes referred to as adaptive gradient methods. AdaGrad consists of dividing the learning rate by the square root of the sum of previous gradients squared componentwise. The idea was to give larger learning rates to highly informative but infrequent features instead of using a fixed predetermined schedule. However, in practice, the division by the cumulative sum of squared gradients may generate small learning rates, thus freezing the iterates too early. Several works proposed heuristical ways to set the learning rates using a less aggressive policy. The work introduced an unpublished, yet popular, algorithm referred to as RmsProp where the cumulative sum used in AdaGrad is replaced by a moving average of squared gradients. Adam combines the advantages of both AdaGrad, RmsProp and inertial methods.

As opposed to AdaGrad, for which theoretical convergence guarantees exist , Adam is comparatively less studied. The initial paper suggests a $\mathcal{O}(\frac{1}{\sqrt{T}})$ average regret bound in the convex setting, but exhibits a counterexample in contradiction with this statement. The latter counterexample implies that the average regret bound of Adam does not converge to zero. A first way to overcome the problem is to modify the Adam iterations themselves in order to obtain a vanishing average regret. This led to propose a variant called AmsGrad with the aim to recover, at least in the convex case, the sought guarantees. The work interprets Adam as a variance-adapted sign descent combining an update direction given by the sign and a magnitude controlled by a variance adaptation principle. A “noiseless” version of Adam is considered in . Under quite specific values of the Adam-hyperparameters, it is shown that for every $\delta>0$, there exists some time instant for which the norm of the gradient of the objective at the current iterate is no larger than $\delta$. The recent paper provides a similar result for AmsGrad and AdaGrad, but the generalization to Adam is subject to conditions which are not easily verifiable. The paper provides a convergence result for RmsProp using the objective function $F$ as a Lyapunov function. However, our work suggests that unlike RmsProp, Adam does not admit $F$ as a Lyapunov function. This makes the approach of hardly generalizable to Adam. Moreover, considers biased gradient estimates instead of the debiased estimates used in Adam.

In the present work, we study the behavior of an ODE, interpreted as the limit in probability of the (interpolated) Adam iterates as the stepsize tends to zero. Closely related continuous-time dynamical systems are also studied in . We leverage the idea of approximating a discrete time stochastic system by a deterministic continuous one, often referred to as the ODE method. A recent work fruitfully exploits this method to study a stochastic version of the celebrated heavy ball algorithm. We refer to for the reader interested in the non-differentiable setting with an analysis of the stochastic subgradient algorithm for non-smooth non-convex objective functions.

Concomitant to the present paper, Da Silva and Gazeau (posted only four weeks after the first version of the present work) study the asymptotic behavior of a similar dynamical system as the one introduced here. They establish several results in continuous time, such as avoidance of traps as well as convergence rates in the convex case; such aspects are out of the scope of this paper. However, the question of the convergence of the (discrete-time) iterates is left open. In the current paper, we also exhibit a Lyapunov function which allows, amongst others, to draw useful conclusions on the effect of the debiasing step of Adam . Finally, studies a slightly modified version of Adam allowing to recover an ODE with a locally Lipschitz continuous vector field, whereas the original Adam algorithm leads to an ODE with an irregular vector field. This technical issue is tackled in the present paper.

Proofs of Section 3

When $\eta=0$, Eq. (ODEη) boils down to the equation of interest (ODE). The choice $\eta\in(0,+\infty)$ will be revealed useful to prove Th. 3.1. Indeed, for $\eta>0$, a solution to Eq. (ODEη) can be shown to exist (on some interval) due to the continuity of the map $h(\,.+\eta,\,.\,)$. Considering a family of such solutions indexed by $\eta\in(0,1]$, the idea is to prove the existence of a solution to (ODE) as a cluster point of the latter family when $\eta\downarrow 0$. Indeed, as the family is shown to be equicontinuous, such a cluster point does exist thanks to the Arzelà-Ascoli theorem. When $\eta=+\infty$, Eq. (ODEη) rewrites

where $h_{\infty}(z):=\lim_{t\to\infty}h(t,z)$. It is useful to note that for $(x,m,v)\in{{\mathcal{Z}}}_{+}$,

Contrary to Eq. (ODE), Eq. (ODE∞) defines an autonomous ODE. The latter admits a unique global solution for any initial condition in ${{\mathcal{Z}}}_{+}$, and defines a dynamical system ${{\mathcal{D}}}$. We shall exhibit a strict Lyapunov function for this dynamical system ${{\mathcal{D}}}$, and deduce that any solution to (ODE∞) converges to the set of equilibria of ${{\mathcal{D}}}$ as $t\to\infty$. On the otherhand, we will prove that the solution to (ODE) with a proper initial condition is a so-called asymptotic pseudotrajectory (APT) of ${{\mathcal{D}}}$. Due to the existence of a strict Lyapunov function, the APT shall inherit the convergence behavior of the autonomous system as $t\to\infty$, which will prove Th. 3.2.

It is convenient to extend the map $h:(0,+\infty)\times{{\mathcal{Z}}}_{+}\to{{\mathcal{Z}}}$ on $(0,+\infty)\times{{\mathcal{Z}}}\to{{\mathcal{Z}}}$ by setting $h(t,(x,m,v)):=h(t,(x,m,|v|))$ for every $t>0$, $(x,m,v)\in{{\mathcal{Z}}}$. Similarly, we extend $h_{\infty}$ as $h_{\infty}((x,m,v)):=h_{\infty}((x,m,|v|))$. For any $T\in(0,+\infty]$ and any $\eta\in[0,+\infty]$, we say that a map $z:[0,T)\to{{\mathcal{Z}}}$ is a solution to (ODEη) on $[0,T)$ with initial condition $z_{0}\in{{\mathcal{Z}}}_{+}$, if $z$ is continuous on $[0,T)$, continuously differentiable on $(0,T)$, and if (ODEη) holds for all $t\in(0,T)$. When $T=+\infty$, we say that the solution is global. We denote by $Z^{\eta}_{T}(z_{0})$ the subset of $C([0,T),{{\mathcal{Z}}})$ formed by the solutions to (ODEη) on $[0,T)$ with initial condition $z_{0}$. For any $K\subset{{\mathcal{Z}}}_{+}$, we define $Z^{\eta}_{T}(K):=\bigcup_{z\in K}Z^{\eta}_{T}(z)$.

Let Assumptions 2, 7.1 and 7.1 hold. For every $\eta\in[0,+\infty]$, $T\in(0,+\infty]$, $z_{0}\in{{\mathcal{Z}}}_{+}$, $z\in Z_{T}^{\eta}(z_{0})$, it holds that $z((0,T))\subset{{\mathcal{Z}}}_{+}^{*}$.

Set $z(t)=(x(t),m(t),v(t))$ for all $t$. Consider $i\in\{1,\dots,d\}$. Assume by contradiction that there exists $t_{0}\in(0,T)$ s.t. $v_{i}(t_{0})<0$. Set $\tau:=\sup\{t\in[0,t_{0}]:v_{i}(t)\geq 0\}$. Clearly, $\tau<t_{0}$ and $v_{i}(\tau)=0$ by the continuity of $v_{i}$. Since $v_{i}(t)\leq 0$ for all $t\in(\tau,t_{0}]$, it holds that $\dot{v}_{i}(t)=b(S_{i}(x(t))-v_{i}(t))$ is nonnegative for all $t\in(\tau,t_{0}]$. This contradicts the fact that $v_{i}(\tau)>v_{i}(t_{0})$. Thus, $v_{i}(t)\geq 0$ for all $t\in[0,T)$. Now assume by contradiction that there exists $t\in(0,T)$ s.t. $v_{i}(t)=0$. Then, $\dot{v}_{i}(t)=bS_{i}(x(t))>0$. Thus, $\lim_{\delta\downarrow 0}\frac{v_{i}(t-\delta)}{-\delta}=bS_{i}(x(t))\,.$ In particular, there exists $\delta>0$ s.t. $v_{i}(t-\delta)\leq-\frac{\delta b}{2}S_{i}(x(t))\,.$ This contradicts the first point.

Recall the definitions of $V$ and $U$ from Eqs. (9) and (10). Clearly, $U_{\infty}(v):=\lim_{t\to\infty}U(t,v)=a(\varepsilon+\sqrt{v})$ is well defined for every $v\in[0,+\infty)^{d}$. Hence, we can also define $V_{\infty}(z):=\lim_{t\to\infty}V(t,z)$ for every $z\in{{\mathcal{Z}}}_{+}$.

Let Assumptions 7.1 and 7.1 hold. Assume that $0<b\leq 4a$. Consider $(t,z)\in(0,+\infty)\times{{\mathcal{Z}}}_{+}^{*}$ and set $z=(x,m,v)$. Then, $V$ and $V_{\infty}$ are differentiable at points $(t,z)$ and $z$ respectively. Moreover, $\langle\nabla V_{\infty}(z),h_{\infty}(z)\rangle\leq-\varepsilon\left\|\frac{am}{U_{\infty}(v)}\right\|^{2}\,$ and

We only prove the second point, the proof of the first point follows the same line. Consider $(t,z)\in(0,+\infty)\times{{\mathcal{Z}}}_{+}^{*}$. We decompose $\langle\nabla V(t,z),(1,h(t,z))\rangle=\partial_{t}V(t,z)+\langle\nabla_{z}V(t,z),h(t,z)\rangle$. After tedious but straightforward derivations, we get:

where $U(t,v_{i})=a(1-e^{-at})\left(\varepsilon+\sqrt{\frac{v_{i}}{1-e^{-bt}}}\right)$ and $\langle\nabla_{z}V(t,z),h(t,z)\rangle$ is equal to:

2 Proof of Th. 3.1

Let Assumptions 2, 2, 7.1 and 7.1 hold. Assume that $0<b\leq 4a$. For every $z_{0}\in{{\mathcal{Z}}}_{0}$, there exists a compact set $K\subset{{\mathcal{Z}}}_{+}$ s.t. for all $\eta\in[0,+\infty)$, all $T\in(0,+\infty]$ and all $z\in Z_{T}^{\eta}(z_{0})$, $\left\{\bar{e}(t+\eta,z(t)):t\in(0,T)\right\}\subset K\,.$ Moreover, choosing $z_{0}$ of the form $z_{0}=(x_{0},0,0)$ and $z(t)=(x(t),m(t),v(t))$, it holds that $F(x(t))\leq F(x_{0})$ for all $t\in[0,T)$.

Let $\eta\in[0,+\infty)$. Consider a solution $z_{\eta}(t)=(x_{\eta}(t),m_{\eta}(t),v_{\eta}(t))$ as in the statement, defined on some interval $[0,T)$. Define $\hat{m}_{\eta}(t)=m_{\eta}(t)/(1-e^{-a(t+\eta)})$, $\hat{v}_{\eta}(t)=v_{\eta}(t)/(1-e^{-b(t+\eta)})$. By Lemma 7.3, $t\mapsto V(t+\eta,z(t))$ is continuous on $[0,T)$, and continuously differentiable on $(0,T)$. By Lemma 7.5, $\dot{V}(t+\eta,z_{\eta}(t))\leq 0$ for all $t>0$. As a consequence, $t\mapsto V(t+\eta,z_{\eta}(t))$ is non-increasing on $[0,T)$. Thus, for all $t\geq 0$, $F(x_{\eta}(t))\leq\lim_{t^{\prime}\downarrow 0}V(t^{\prime}+\eta,z_{\eta}(t^{\prime}))$. Note that $V(t+\eta,z_{\eta}(t))\leq F(x_{\eta}(t))+\frac{1}{2}\sum_{i=1}^{d}\frac{m_{\eta,i}(t)^{2}}{a(1-e^{-a(t+\eta)})\varepsilon}\,.$ If $\eta>0$, every term in the sum in the righthand side tends to zero, upon noting that $m_{\eta}(t)\to 0$ as $t\to 0$. The statement still holds if $\eta=0$. Indeed, by Lemma 7.1, for a given $i\in\{1,\dots,d\}$, there exists $\delta>0$ s.t. for all $0<t<\delta$, $m_{\eta,i}(t)^{2}\leq 2a^{2}(\partial_{i}F(x_{0}))^{2}t^{2}$ and $1-e^{-at}\geq(at)/2$. As a consequence, each term of the sum is no larger than $4(\partial_{i}F(x_{0}))^{2}t/\varepsilon$, which tends to zero as $t\to 0$. We conclude that for all $t\geq 0$, $F(x_{\eta}(t))\leq F(x_{0})$. In particular, $\{x_{\eta}(t):t\in[0,T)\}\subset\{F\leq F(x_{0})\}$, the latter set being bounded by Assumption 2.

As $V(t+\eta,z_{\eta}(t))\leq F(x_{0})$, we obtain: $F(x_{0})\geq F(x_{\eta}(t))+\frac{1}{2}\left\|m_{\eta}(t)\right\|^{2}_{U(t+\eta,v_{\eta}(t))^{-1}}$. Thus, $F(x_{0})\geq\inf F+\frac{1}{2a(\varepsilon+\sqrt{M})}\|m_{\eta}(t)\|^{2}\,$. Therefore, $m_{\eta}(\,.\,)$ is bounded on $[0,T)$, uniformly in $\eta$. The same holds for $\hat{m}_{\eta}$ by using the mean value theorem in the same way as for $\hat{v}_{\eta}$. The proof is complete.

Let Assumptions 2, 2, 7.1 and 7.1 hold. Assume that $0<b\leq 4a$. Let $K$ be a compact subset of ${{\mathcal{Z}}}_{+}$. Then, there exists an other compact set $K^{\prime}\subset{{\mathcal{Z}}}_{+}$ s.t. for every $T\in(0,+\infty]$ and every $z\in Z_{T}^{\infty}(K)$, $z([0,T))\subset K^{\prime}$.

The proof follows the same line as Prop. 7.7 and is omitted.

For any $K\subset{{\mathcal{Z}}}_{+}$, define $v_{\min}(K):=\inf\{v_{k}:(x,m,v)\in K,i\in\{1,\dots,d\}\}$.

Under Assumptions 2, 2, 7.1 and 7.1, the following holds true.

For every compact set $K\subset{{\mathcal{Z}}}_{+}$, there exists $c>0$, s.t. for every $z\in Z^{\infty}_{\infty}(K)$, of the form $z(t)=(x(t),m(t),v(t))$, $v_{i}(t)\geq c\min\left(1,\frac{v_{\min}(K)}{2c}+t\right)\qquad(\forall t\geq 0,\forall i\in\{1,\dots,d\})\,.$

For every $z_{0}\in{{\mathcal{Z}}}_{0}$, there exists $c>0$ s.t. for every $\eta\in[0,+\infty)$ and every $z\in Z_{\infty}^{\eta}(z_{0})$, $v_{i}(t)\geq c\min(1,t)\qquad(\forall t\geq 0,\forall i\in\{1,\dots,d\})\,.$

Set $\kappa_{1}:=0.5(v_{\min}+bS_{\min}\tau)$. Note that $v_{i}(\tau)\geq\kappa_{1}$. Define $S_{\min}^{\prime}:=\inf\{S_{i}(x):i\in\{1,\dots,d\},(x,m,v)\in K^{\prime}\}\,.$ Note that $S_{\min}^{\prime}>0$ by Assumptions 7.1 and 2. Finally, define $\kappa=0.5\min(\kappa_{1},S_{\min}^{\prime})$. By contradiction, assume that the set $\{t\geq\tau:v_{i}(t)<\kappa\}$ is non-empty, and denote by $\tau^{\prime}$ its infimum. It is clear that $\tau^{\prime}>\tau$ and $v_{i}(\tau^{\prime})=\kappa$. Thus, $b^{-1}\dot{v}_{i}(\tau^{\prime})=S_{i}(x(\tau^{\prime}))-\kappa$. We obtain that $b^{-1}\dot{v}_{i}(\tau^{\prime})\geq 0.5S_{\min}^{\prime}>0$. As a consequence, there exists $t\in(\tau,\tau^{\prime})$ s.t. $v_{i}(t)<v_{i}(\tau^{\prime})$. This contradicts the definition of $\tau^{\prime}$. We have shown that for all $t\geq\tau$, $v_{i}(t)\geq\kappa$. Putting this together with Eq. (21) and using that $\kappa\leq v_{\min}+bS_{\min}\tau$, we conclude that: $\forall t\geq 0,\ v_{i}(t)\geq\min\left(\kappa\,,\frac{v_{\min}}{2}+\frac{bS_{\min}t}{2}\right)\,.$ Setting $c:=\min(\kappa,bS_{\min}/2)$, the result follows.

We prove the second point. By Prop. 7.7, there exists a compact set $K\subset{{\mathcal{Z}}}_{+}$ s.t. for every $\eta\geq 0$, every $z\in Z_{\infty}^{\eta}(x_{0})$ of the form $z(t)=(x(t),m(t),v(t))$ satisfies $\{(x(t),\hat{m}(t),\hat{v}(t)):t\geq 0\}\subset K$, where $\hat{m}(t)=m(t)/(1-e^{-a(t+h)})$ and $\hat{v}(t)=v(t)/(1-e^{-b(t+h)})$. Denote by $L_{S}$ the Lipschitz constant of $S$ on the set $\{x:(x,m,v)\in K\}$. Introduce the constants $M_{1}:=\sup\{\|m/(\varepsilon+\sqrt{v})\|_{\infty}:(x,m,v)\in K\}$, $M_{2}:=\sup\{\|S(x)\|_{\infty}:(x,m,v)\in K^{\prime}\}$. These constants being introduced, the rest of the proof follows the same line as the proof of the first point.

2.2 Existence

Let Assumptions 2, 2, 7.1 and 7.1 hold. Assume that $0<b\leq 4a$. For every $z_{0}\in{{\mathcal{Z}}}_{+}$,$Z_{\infty}^{\infty}(z_{0})\neq\emptyset$. For every $(z_{0},\eta)\in{{\mathcal{Z}}}_{0}\times(0,+\infty)$,$Z_{\infty}^{\eta}(z_{0})\neq\emptyset$.

We prove the first point (the proof of the second point follows the same line). Under Assumptions 7.1 and 7.1, $h_{\infty}$ is continuous. Therefore, Cauchy-Peano’s theorem guarantees the existence of a solution to the (ODE) issued from $z_{0}$, which we can extend over a maximal interval of existence $[0,T_{\max})$.We conclude that the solution is global ($T_{\max}=+\infty$) using the boundedness of the solution given by Prop. 7.9.

Let Assumptions 2, 2, 7.1 and 7.1 hold. Assume that $0<b\leq 4a$. Consider $z_{0}\in{{\mathcal{Z}}}_{0}$. Denote by $(z_{\eta}:\eta\in(0,+\infty))$ a family of functions on $[0,+\infty)\to{{\mathcal{Z}}}_{+}$ s.t. for every $\eta>0$, $z_{\eta}\in Z_{\infty}^{\eta}(z_{0})$. Then, $(z_{\eta})_{\eta>0}$ is equicontinuous.

Let Assumptions 2, 2, 7.1 and 7.1 hold. Assume that $0<b\leq 4a$. For every $z_{0}\in{{\mathcal{Z}}}_{0}$, $Z_{\infty}^{0}(z_{0})\neq\emptyset$ i.e., (ODE) admits a global solution issued from $z_{0}$.

and the righthand side converges to zero. As a consequence, for all $t>s$, $z(t)=z(s)+\int_{s}^{t}h(u,z(u))du\,.$ Moreover, $z(0)=z_{0}$. This proves that $z\in Z^{0}_{\infty}(z_{0})$.

2.3 Uniqueness

Let Assumptions 2, 2, 7.1 and 7.1 hold. Assume $b\leq 4a$. For every $z_{0}\in{{\mathcal{Z}}}_{0}$, $Z_{\infty}^{0}(z_{0})$ is a singleton i.e., there exists a unique global solution to (ODE) with initial condition $z_{0}$.

Consider solutions $z$ and $z^{\prime}$ in $Z^{0}_{\infty}(z_{0})$. We denote by $(x(t),m(t),v(t))$ the blocks of $z(t)$, and we define $(x^{\prime}(t),m^{\prime}(t),v^{\prime}(t))$ similarly. For all $t>0$, we define $\hat{m}(t):=m(t)/(1-e^{-at})$, $\hat{v}(t):=v(t)/(1-e^{-bt})$, and we define $\hat{m}^{\prime}(t)$ and $\hat{v}^{\prime}(t)$ similarly. By Prop. 7.7, there exists a compact set $K\subset{{\mathcal{Z}}}_{+}$ s.t. $(x(t),\hat{m}(t),\hat{v}(t))$ and $(x^{\prime}(t),\hat{m}^{\prime}(t),\hat{v}^{\prime}(t))$ are both in $K$ for all $t>0$. We denote by $L_{S}$ and $L_{\nabla F}$ the Lipschitz constants of $S$ and $\nabla F$ on the compact set $\{x:(x,m,v)\in K\}$. These constants are finite by Assumptions 7.1 and 7.1. We define $M:=\sup\{\|m\|_{\infty}:(x,m,v)\in K\}$. Define $u_{x}(t):=\|x(t)-x^{\prime}(t)\|^{2}$, $u_{m}(t):=\|\hat{m}(t)-\hat{m}^{\prime}(t)\|^{2}$ and $u_{v}(t):=\|\hat{v}(t)-\hat{v}^{\prime}(t)\|^{2}$. Let $\delta>0$. Define: $u^{(\delta)}(t):=u_{x}(t)+\delta u_{m}(t)+\delta u_{v}(t)\,.$ By the chain rule and the Cauchy-Schwarz inequality, $\dot{u}_{x}(t)\leq 2\|x(t)-x^{\prime}(t)\|\|\frac{\hat{m}(t)}{\varepsilon+\sqrt{\hat{v}(t)}}-\frac{\hat{m}^{\prime}(t)}{\varepsilon+\sqrt{\hat{v}^{\prime}(t)}}\|$. Thus, using Lemma 7.11, there exists $c>0$ s.t.

For any $\delta>0$, $2\|x(t)-x^{\prime}(t)\|\,\|\hat{m}(t)-\hat{m}^{\prime}(t)\|\leq\delta^{-1/2}(u_{x}(t)+\delta u_{m}(t))\leq\delta^{-1/2}u^{(\delta)}(t)$. Similarly, $2\|x(t)-x^{\prime}(t)\|\,\|\hat{v}(t)-\hat{v}^{\prime}(t)\|\leq\delta^{-1/2}u^{(\delta)}(t)$. Thus, for any $\delta>0$,

We now study $u_{m}(t)$. For all $t>0$, we obtain after some algebra: $\frac{d}{dt}\hat{m}(t)=a(\nabla F(x(t))-\hat{m}(t))/(1-e^{-at})\,.$ Therefore, $\dot{u}_{m}(t)\leq\frac{2aL_{\nabla F}}{1-e^{-at}}\|\hat{m}(t)-\hat{m}^{\prime}(t)\|\,\|x(t)-x^{\prime}(t)\|\,.$ For any $\theta>0$, it holds that $2\|\hat{m}(t)-\hat{m}^{\prime}(t)\|\,\|x(t)-x^{\prime}(t)\|\leq\theta u_{x}(t)+\theta^{-1}u_{m}(t)$. In particular, letting $\theta:=2L_{\nabla F}$, we obtain that for all $\delta>0$,

where the last inequality is due to the fact that $y/(1-e^{-y})\leq 1+y$ for all $y>0$. Using the exact same arguments, we also obtain that

We now choose any $\delta$ s.t. $4\delta\leq 1/\max(L_{S}^{2},L_{\nabla F}^{2})$. Then, Eq. (23) and (24) respectively imply that $\delta\dot{u}_{m}(t)\leq 0.5(a+t^{-1})u^{(\delta)}(t)$ and $\delta\dot{u}_{v}(t)\leq 0.5(b+t^{-1})u^{(\delta)}(t)$. Summing these inequalities along with Eq. (22), we obtain that for every $t>0$, $\dot{u}^{(\delta)}(t)\leq\psi(t)u^{(\delta)}(t)\,$, where: $\psi(t):=\frac{a+b}{2}+\frac{1}{\varepsilon\sqrt{\delta}}+\frac{M}{2\varepsilon^{2}\sqrt{\delta c\min(1,t)}}+\frac{1}{t}\,.$ From Grönwall’s inequality, it holds that for every $t>s>0$, $u^{(\delta)}(t)\leq u^{(\delta)}(s)\exp\left(\int_{s}^{t}\psi(s^{\prime})ds^{\prime}\right)\,$. We first consider the case where $t\leq 1$. We set $c_{1}:=(a+b)/2+(\varepsilon\sqrt{\delta})^{-1}$ and $c_{2}:=M/(\varepsilon^{2}\sqrt{\delta c})$. With these notations, $\int_{s}^{t}\psi(s^{\prime})ds^{\prime}\leq c_{1}t+c_{2}\sqrt{t}+\ln\frac{t}{s}\,.$ Therefore, $u^{(\delta)}(t)\leq\frac{u^{(\delta)}(s)}{s}\exp\left(c_{1}t+c_{2}\sqrt{t}+\ln t\right)\,$. By Lemma 7.1, recall that $\dot{x}(0)$ and $\dot{x}^{\prime}(0)$ are both well defined (and coincide). Thus,

By Lemma 7.1, $z$ and $z^{\prime}$ are differentiable at point zero. Then, the above inequality gives $\limsup_{s\downarrow 0}\frac{|\hat{m}_{i}(s)-\hat{m}_{i}^{\prime}(s)|}{s}\leq 4(L_{\nabla F}\vee 1)\|\dot{z}(0)\|$ and $\limsup_{s\downarrow 0}\frac{u_{m}(s)}{s^{2}}\leq 16d(L_{\nabla F}^{2}\vee 1)\|\dot{z}(0)\|^{2}\,.$Therefore, $u_{m}(s)/s$ converges to zero as $s\downarrow 0$. By similar arguments, it can be shown that $\limsup_{s\downarrow 0}{u_{v}(s)}/{s^{2}}\leq 16d(L_{S}^{2}\vee 1)\|\dot{z}(0)\|^{2}$, thus $\lim u_{v}(s)/s=0$. Finally, we obtain that ${u^{(\delta)}(s)}/{s}$ converges to zero as $s\downarrow 0$. Letting $s$ tend to zero, we obtain that for every $t\leq 1$, $u^{(\delta)}(t)=0$. Setting $s=1$ and $t>1$, and noting that $\psi$ is integrable on $[1,t]$, it follows that $u^{(\delta)}(t)=0$ for all $t>1$. This proves that $z=z^{\prime}$.