# Convergence rates for the Adam optimizer

Steffen Dereich1 and Arnulf Jentzen2,3

1 Institute for Mathematical Stochastics, University of Münster,
Germany; e-mail: steffen.dereich\texttt{a}⃝uni-muenster.de
2 School of Data Science and Shenzhen Research Institute of Big Data,
The Chinese University of Hong Kong, Shenzhen (CUHK-Shenzhen),
China; e-mail: ajentzen\texttt{a}⃝cuhk.edu.cn
3 Applied Mathematics: Institute for Analysis and Numerics,
University of Münster, Germany; e-mail: ajentzen\texttt{a}⃝uni-muenster.de

###### Abstract

Stochastic gradient descent (SGD) optimization methods are nowadays the method
of choice for the training of deep neural networks (DNNs) in artificial
intelligence systems. In practically relevant training problems, usually not
the plain vanilla standard SGD method is the employed optimization scheme but
instead suitably accelerated and adaptive SGD optimization methods are
applied. As of today, maybe the most popular variant of such accelerated and
adaptive SGD optimization methods is the famous Adam optimizer proposed by
Kingma & Ba in 2014. Despite the popularity of the Adam optimizer in
implementations, it remained an open problem of research to provide a
convergence analysis for the Adam optimizer even in the situation of simple
quadratic stochastic optimization problems where the objective function (the
function one intends to minimize) is strongly convex. In this work we solve
this problem by establishing optimal convergence rates for the Adam optimizer
for a large class of stochastic optimization problems, in particular, covering
simple quadratic stochastic optimization problems. The key ingredient of our
convergence analysis is a new vector field function which we propose to refer
to as the _Adam vector field_. This Adam vector field accurately describes the
macroscopic behaviour of the Adam optimization process but differs from the
negative gradient of the objective function (the function we intend to
minimize) of the considered stochastic optimization problem. In particular,
our convergence analysis reveals that the Adam optimizer does typically not
converge to critical points of the objective function (zeros of the gradient
of the objective function) of the considered optimization problem but
converges with rates to zeros of this Adam vector field. Even though our
convergence results are only formulated for the Adam optimizer, the arguments
in our convergence analysis can also be applied to other related SGD
optimization methods and open the door for a systematic mathematical treatment
of a large class of adaptive and/or accelerated SGD optimization methods.

###### Contents

  1. 1 Introduction
    1. 1.1 Literature review
    2. 1.2 Structure of this article
  2. 2 Adam sequence space, Adam vector field and main convergence result
  3. 3 The innovation viewed as a non-expansive mapping on the Adam sequence space
  4. 4 Analysis of the Adam evolution with fixed $\theta$-parameter
  5. 5 Introducing approximations of the Adam optimization processes
  6. 6 Ordinary differential equation (ODE) based error analyses for the Adam optimizer
  7. 7 Proof of the main result of this article (Theorem 2.5 in Section 2)
  8. 8 Regularity properties and perturbation analysis for the Adam vector field
  9. 9 Proof of the theorem in the introduction (Theorem 1.1 in Section 1)

##  1 Introduction

_Stochastic gradient descent_ (SGD) optimization methods are nowadays the
method of choice for the training of deep _artificial neural networks_ (ANNs)
in artificial intelligence systems. In practically relevant training problems,
usually not the plain vanilla standard SGD method is the employed optimization
scheme but instead suitably accelerated and adaptive SGD optimization methods
are considered, such as the momentum SGD (cf. [27]), the Nesterov accelerated
SGD (cf. [25, 31]), the Adagrad (cf. [9]), the RMSprop (cf. [15]), the
Adadelta (cf. [35]), and the Adam (cf. [22]) optimizers. As of today, maybe
the most popular variant of such accelerated and adaptive SGD optimization
methods is the famous Adam optimizer proposed in Kingma & Ba [22], which is
essentially a combination of the accelerated momentum SGD optimizer and the
adaptive RMSprop optimizer. We also refer, for instance, to the overview
articles [29, 30] and the monograph [20, Chapters 6 and 7] for details and
further references on such and related accelerated and adaptive SGD
optimization methods.

Despite the popularity of the Adam optimizer in implementations, it remained
an open problem of research to provide a convergence analysis for the Adam
optimizer even in the situation of simple quadratic _stochastic optimization
problems_ (SOPs) (such as 1 and 2 below) where the objective function (the
function one intends to minimize) is strongly convex (see also below for a
brief overview on results in the literature analyzing accelerated and adaptive
SGD optimization methods).

In this work we solve this problem by establishing optimal convergence rates
for the Adam optimizer for a large class of SOPs (cf. Theorem 2.5 in Section 2
below for the main result of this work), in particular, covering simple
quadratic SOPs. To outline the findings of this work, within this introductory
section we now present in Theorem 1.1 below a consequence of our general
convergence analysis in the situation of the simple examplary quadratic SOPs
to minimize the function

${\mathbb{R}}^{d}\ni\theta\mapsto{\mathbb{E}}[\ell(\theta,U^{(1)})]\in{\mathbb{R}}$
(1)

with $U^{(1)}\colon\Omega\to{\mathbb{R}}^{d}$ being an
${\mathbb{R}}^{d}$-valued random variable on a probability space
$(\Omega,\mathcal{F},{\mathbb{P}})$ and with the loss function
$\ell\colon{\mathbb{R}}^{d}\times{\mathbb{R}}^{d}\to{\mathbb{R}}$ being111Note
that for all $n\in{\mathbb{N}}$, $x=(x_{1},\dots,x_{n})\in{\mathbb{R}}^{n}$ it
holds that $|x|=[\sum_{k=1}^{n}(x_{k})^{2}]^{1/2}$ is the standard norm of the
vector $x$. the standard mean square error loss
$\ell(\theta,u)=|\theta-u|^{2}$ for $\theta,u\in{\mathbb{R}}^{d}$. We note
that in this simple example the negative gradient of $\ell$ with respect to
the parameter space variable satisfes that for all
$\theta,u\in{\mathbb{R}}^{d}$ it holds that
$-(\nabla_{\theta}\ell)(\theta,u)=u-\theta$ (see 2 in Theorem 1.1 below).

######  Theorem 1.1 (Convergence rates for the Adam optimizer in a special
case).

Let

  1. (i)

$d\in{\mathbb{N}}$, $\alpha,\beta\in[0,1)$, $\epsilon\in(0,\infty)$ with
$\alpha<\sqrt{\beta}$,

  2. (ii)

$U=(U^{(i)})_{i\in{\mathbb{N}}}$ be a sequence of bounded i.i.d.
${\mathbb{R}}^{d}$-valued random variables,

  3. (iii)

$(\gamma_{n})_{n\in{\mathbb{N}}}$ be a decreasing $(0,\infty)$-valued zero-
sequence with
$\lim_{n\to\infty}\frac{\gamma_{n}-\gamma_{n+1}}{\gamma_{n}^{2}}=0$ and

  4. (iv)

for every $M\in{\mathbb{N}}$,

$\displaystyle\begin{split}X_{M}\colon({\mathbb{R}}^{d})^{\infty}\times{\mathbb{R}}^{d}\to{\mathbb{R}}^{d},\
((u^{(i)})_{i\in{\mathbb{N}}},\theta)\mapsto\frac{1}{M}\sum_{i=1}^{M}(u^{(i)}-\theta).\end{split}$
(2)

Then for every $p\in(0,\infty)$, $\xi\in{\mathbb{R}}^{d}$ there exist
$M_{0}\in{\mathbb{N}}$, $\eta\in(0,\infty)$ and a ${\mathbb{R}}^{d}$-valued
sequence $(\vartheta_{M})_{M\in{\mathbb{N}}\cap[M_{0},\infty)}$ such that for
every $M\in{\mathbb{N}}\cap[M_{0},\infty)$ the Adam algorithm
$(\theta_{n})_{n\in{\mathbb{N}}_{0}}$ with innovation $(X_{M},U)$, damping
parameters $(\alpha,\beta,\epsilon)$ and step-sizes
$(\gamma_{n})_{n\in{\mathbb{N}}}$ started in $\xi$ (cf. 2.2 below) satisfies

  1. (a)

$\lim_{n\to\infty}\theta_{n}=\vartheta_{M},$ almost surely,

  2. (b)

${\mathbb{E}}[|\theta_{n}-\vartheta_{M}|^{p}]^{1/p}\leq\eta\sqrt{\gamma_{n}}$,
for all $n\in{\mathbb{N}}$, and

  3. (c)

$|\vartheta_{M}-{\mathbb{E}}[U^{(1)}]|\leq\eta\,M^{-1}$.

Roughly speaking, Theorem 1.1 establishes that the Adam optimizer applied to
the simple examplary quadratic SOP in 1 converges for a sufficiently large
mini-batch size $M\in{\mathbb{N}}$ almost surely to a random limit point
$\vartheta_{M}$ (see item (a) in Theorem 1.1), shows that the strong
$L^{p}$-distance between the Adam optimization process and the random limit
point $\vartheta_{M}$ is bounded by a constant multiplied with the square root
of the learning rate (optimal convergence rate $\nicefrac{{1}}{{2}}$ in
dependence of the size of the learning rate) (see item (b) in Theorem 1.1),
and proves that the random limit point $\vartheta_{M}$ converges with
convergence rate $1$ to the global minimizer of the SOP in 1 as the size of
the mini-batch $M$ increases to infinity (see item (c) in Theorem 1.1). We
note that the assumption in item (iii) in Theorem 1.1 that the sequence of
learning rates $(\gamma_{n})_{n\in{\mathbb{N}}}$ is a zero-sequence in the
sense that

$\limsup_{n\to\infty}\gamma_{n}=0$ (3)

is necessary and can not be avoided. Indeed, in [5] it is proved for several
SOPs that every component of the Adam optimizer fails to converge to any
possible random point if the learning rates do not decay to zero.

Theorem 1.1 is a consequence of the more general convergence analysis for the
Adam algorithm that we develop within this article. To be more specific, in
the main result of this article, Theorem 2.5 in Section 2 below, we provide an
_ordinary differential equation_ (ODE) based convergence analysis for the Adam
optimizer and, in praticular, we establish optimal convergence rates for the
Adam optimizer for a large class of SOPs, in particular, covering simple
quadratic SOPs (such as 1 above).

The key ingredient of our convergence analysis is a new vector field function
which we propose to refer to as the _Adam vector field_ (cf. 2.4 below). This
Adam vector field accurately describes the macroscopic behaviour of the Adam
optimization process but differs from the negative gradient of the objective
function (the function we intend to minimize) of the considered SOP (cf. 2.4
and 2.5). In particular, our convergence analysis reveals that the Adam
optimizer does typically not converge to critical points of the objective
function (zeros of the gradient of the objective function) of the considered
optimization problem (cf. LABEL:def:linApp, Theorem 8.1, and 8.2 in Section 8
below) but converges with rates to zeros of this Adam vector field (cf.
Theorem 2.5). Loosely speaking, in Theorem 2.5 we provide for every
sufficiently large $n\in{\mathbb{N}}$ an upper bound for the strong
$L^{p}$-distance between the Adam optimization process at time
$n\in{\mathbb{N}}$ and the solution process of the ODE with the vector field
in the ODE given by the Adam vector field (cf. 17 in Theorem 2.5). In
particular, if the solution process of the ODE starts in a zero of the Adam
vector field, then the solution process of the ODE reduces to a constant
function and, in such a situation, we have that Theorem 2.5 provides for every
sufficiently large $n\in{\mathbb{N}}$ an upper bound for the strong
$L^{p}$-distance between the Adam optimization process at time
$n\in{\mathbb{N}}$ and this zero of the Adam vector field (cf. 17 in Theorem
2.5). Even though our convergence results in Theorems 1.1 and 2.5 are only
formulated for the Adam optimizer, the arguments in our convergence analysis
can also be applied to other SGD optimization methods and open the door for a
systematic mathematical treatment of a large class of possibly adaptive and/or
accelerated SGD optimization methods.

###  1.1 Literature review

In the following we supply a brief survey on selected works in the literature
providing error or regret analyses for the Adam optimizer or related SGD based
optimization procedures.

First, we refer, for example, to [3, 21, 24, 11, 28] for non-
convergence/divergence results or lower error or regret bounds for the Adam
optimizer and related gradient based optimization procedures. In particular,
the work Reddi et al. [28, Theorems 1, 2, and 3] shows that for any choice of
the damping paramters $\alpha,\beta\in[0,1)$ with $\alpha<\sqrt{\beta}$ there
exists a convex stochastic optimization problem in which (a slightly modified
variant of) the Adam optimizer with the damping parameters $\alpha$ and
$\beta$ does not converge to the optimal solution.

Moreover, in the work [5] it is shown for several SOPs that every component of
the Adam optimizer and related SGD optimization methods fail to converge to
any possible scalar random variable if the learning rate do not decay to zero
(cf. 3 above).

Furthermore, in the situation of the training of shallow ANNs with the
_rectified linear unit_ (ReLU) activation the paper [21] proves, in
particular, that a class of SGD optimization methos including the Adam
optimizer as a special case fails to converge to _global minimizers_ in the
ANN optimization training landscape (cf. also [3, 24, 11, 26]). The findings
in [21] (and [3, 24], respectively) do, however, not exclude the possibility
that the Adam optimizer converges to a good non-optimal local minimizer whose
value under the objective function is close to the infimal value of the
objective function (cf. also [12, 18, 32, 33] for convergence results to good
non-optimal critical points in simplified shallow ANN training setups).

Moreover, we refer, for instance, to [13, 6, 36, 1, 23, 28, 16, 37, 4, 7, 14,
9, 22, 2, 36, 37, 8, 34, 17] for works providing convergence results or
(possibly asymptotic) upper error or regret bounds for Adam and related SGD
based optimization procedures. For example, in Reddi et al. [28, Algorithm 2]
a modified variant of the Adam optimizer (referred to as AMSGrad optimizer),
in which, loosely speaking, the componentwise maximum over previously
calculated componentwise squared gradients is incorporated (so that the non-
convergence issue in [28, Theorems 1, 2, and 3] can be avoided), is proposed
and studied. In particular, the work [28, Theorem 4 and Corollary 1] provides
upper bounds for the regret of this modified variant of the Adam optimizer.

Furthermore, in the situation of suitable strongly convex SOPs the article
Godichon-Baggioni & Tarrago [13, Theorems 3.1 and 3.2 and Propositions 3.1 and
3.2] provides an error analysis for a general abstract class of adaptive SGD
optimization methods, which is then specialized for the Adagrad optimizer (cf.
[13, Theorems 3.4, 4.2, and 5.2]) and stochastic Newton algorithms (cf. [13,
Theorems 3.3, 4.1, and 5.1 and Corollary 3.1]).

Moreover, in the situation of SOPs fulfilling coercivity-type conditions the
work Dereich et al. [6, Corollary 4.11] establishes convergence to the optimal
solution of the considered SOP for certain SGD optimization methods with
random learning rates. In the case of certain simple quadratic SOPs (cf. 1
above) the article [6, Theorem 7.1] also establishes convergence to the
optimal solution of the considered SOP for the SGD method with suitable
adaptive learning rates.

Furthermore, in Dereich & Kassing [7] convergence of possibly accelerated SGD
optimization methods such as the momentum SGD optimizer to a critical point is
shown (cf., for example, also [17, Section 3]) under the assumption that the
objective function satisfies the Kurdyka–Łojasiewicz inequality.

An ODE based convergence result for the Adam algorithm of a different type
than in Theorem 2.5 below is given in the work Barakat & Bianchi [1].
Specifically, in [1] it is, among other things, shown that the Adam optimizer
with constant learning rates
$\forall\,n,m\in{\mathbb{N}}\colon\gamma_{n}=\gamma_{m}$ (cf. item (iii) in
Theorem 1.1 above) converges to the solution of a suitable non-autonomous ODE
(see (3.3) and (ODE) in [1]) as the constant learning rate $\gamma_{1}$
converges to zero. We note that the Adam vector field in this work (see 2.4
below) is autonomous and significantly different to the non-autonomous vector
field in [1, (3.3) and (ODE)].

We also refer, for instance, to [34, Theorem 1, Corollary 1, Corollary 2,
Corollary 3, Theorem 5, and Theorem 6] and [8, Theorem 3.8, Corollary 3.11,
Theorem 4.8, Theorem 5.2, and Theorem 5.3] and the references therein for
convergence analyses for Adam-type optimizers in the situation of non-smooth
objective functions. In this context, we also refer, for example, to [23,
Theorem 4.1, Theorem 4.2, and Theorem 6.2] (and the references mentioned
therein) for upper regret bounds for the Adam optimizer and a variance-reduced
variant of the Adam optimizer (referred to as VRAdam optimizer) under less
restrictive global boundedness/growth assumptions on the gradient of the
objective function.

For further references and more detailed reviews on the literature on Adam and
related SGD optimization methods we also refer, for instance, to [29, 19, 10,
30, 20].

###  1.2 Structure of this article

The remainder of this article is organized as follows. In Section 2 we
introduce the Adam algorithm in full details (cf. 2.1 and 2.2 below), we
introduce our concept of the Adam vector field (cf. 2.4 below), we present in
Theorem 2.5 below the main convergence result of this work, and we introduce a
suitable space of vector valued sequences, which we refer to as Adam sequence
space, used to formulate Theorem 2.5 (cf. 2.3 below).

Our main goal in Section 3 is, loosely speaking, to establish that the
innovation in the Adam optimizer (cf. 2.1) considered as a function on the
Adam sequence space is a uniformly bounded non-expansive mapping (weak
contraction) on the Adam sequence space (cf. Lemma 3.1 below).

In Section 4 we analyze the evolution of a simplified variant of the Adam
optimizer in which we do not employ the current state of the Adam optimizer in
the recursions for the momentum and daming terms (cf. 2.2) but in which we
instead employ a fixed predetermined external vector
$\theta\in{\mathbb{R}}^{d}$ in the recursions for the momentum and daming
terms (cf. Lemmas 4.1 and 4.2 in Section 4).

A key idea in our proof for convergence rates for the Adam optimizer (cf.
Theorem 1.1 above and Theorem 2.5 below) is to not study Adam optimization
processes directly but instead, first, to analyse suitable approximations of
Adam optimization processes and, thereafter, to estimate the differences
between the Adam optimization processes and their approximations. Our main
subject in Section 5 is precisely to study such approximations of the Adam
optimization processes (cf. 64, 66, 5.2, and Lemma 5.5 in Section 5). Our
proof of 5.2 (the main result of Section 5) employs applications of the
results established in Section 4, that is, we employ Lemmas 4.1 and 4.2 from
Section 4 in our proof of 5.2.

In Section 6 we apply the findings of Section 5 (cf. 5.2, 5.5, and 5.6 in
Section 5) to establish ODE based non-uniform (cf. 111 in 6.1) and uniform
(cf. 137 in 6.2) error analyses for the Adam optimizer.

In Section 7 we combine the findings from Sections 3 and 6 (cf. Lemma 3.1 in
Section 3 and 6.1 and 6.2 in Section 6) to complete the proof of our main
convergence rate result for the Adam optimizer in Theorem 2.5 below.

In Section 8 we establish regularity properties (cf. Theorem 8.3 and Lemma
8.5) and a perturbation analysis (cf. Theorem 8.1) for the Adam vector field.

In Section 9 we combine the regularity properties established in Section 8
(cf. Theorem 8.3 and Lemma 8.5) with an application of Theorem 2.5 to the
simple quadratic SOP in 1 to deliver the proof of our specialized convergence
rate result for the Adam optimizer in Theorem 1.1 above.

##  2 Adam sequence space, Adam vector field and main convergence result

In this section, we introduce the central objects and the main theorems of
this article. For this we denote by $(\Omega,\mathcal{F},{\mathbb{P}})$ a
probability space and by $d\in{\mathbb{N}}$ the dimension of the underlying
problem. Let us introduce the Adam algorithm with full details.

######  Definition 2.1 (Innovation).

Let $\mathcal{U}$ be a measurable space. A pair $(X,U)$ consisting of

  1. (i)

a $\mathcal{U}$-valued random variable $U$ and

  2. (ii)

a product measurable mapping
$X\colon\mathcal{U}\times{\mathbb{R}}^{d}\to{\mathbb{R}}^{d}$

is called _innovation_.

######  Definition 2.2 (Adam optimizer).

Let

  1. (i)

$\alpha,\beta\in[0,1)$, $\epsilon\in(0,\infty)$ with $\alpha<\sqrt{\beta}$
(the _damping parameters_),

  2. (ii)

$n_{0}\in{\mathbb{N}}_{0}$, $\theta_{n_{0}},m_{n_{0}}\in{\mathbb{R}}^{d}$,
$v_{n_{0}}\in[0,\infty)^{d}$ (the _initialisation_),

  3. (iii)

a decreasing $(0,\infty)$-valued sequence $(\gamma_{n})_{n\in{\mathbb{N}}}$
(the _sequence of step-sizes_) and

  4. (iv)

$(X,U)$ an innovation.

An ${\mathbb{R}}^{d}$-valued stochastic process
$(\theta_{n})_{n\in{\mathbb{N}}_{0}\cap[n_{0},\infty)}$ is called _Adam
algorithm with damping parameters $(\alpha,\beta,\epsilon)$ and step-sizes
$(\gamma_{n})$ started at time $n_{0}$ in
$(\theta_{n_{0}},m_{n_{0}},v_{n_{0}})$_, if it satisfies for every
$n\in{\mathbb{N}}\cap(n_{0},\infty)$ and $i=1,\dots,d$

$\displaystyle\begin{split}\theta^{(i)}_{n}=\theta^{(i)}_{n-1}+\gamma_{n}\,\sigma^{(i)}_{n}\,m^{(i)}_{n},\end{split}$
(4)

where $(U_{n})_{n\in{\mathbb{N}}\cap(n_{0},\infty)}$ is a family of
independent copies of $U$ and for $n\in{\mathbb{N}}\cap(n_{0},\infty)$ and
$i=1,\dots,d$,

  * •

$m_{n}=\alpha\,m_{n-1}+(1-\alpha)\,X(U_{n},\theta_{n-1})$,

  * •

$v^{(i)}_{n}=\beta\,v^{(i)}_{n-1}+(1-\beta)\,(X^{(i)}(U_{n},\theta_{n-1}))^{2}$
and

  * •

$\displaystyle\sigma^{(i)}_{n}=\frac{1}{\sqrt{v_{n}^{(i)}/(1-\beta^{n})}+\epsilon}$.

We call the sequence $(t_{n})_{n\in{\mathbb{N}}_{0}}$ given by

$\displaystyle\begin{split}t_{n}=\sum_{k=1}^{n}\gamma_{k}\end{split}$ (5)

the _training times_ of the Adam algorithm.

Technically, the Adam algorithm defines a Markov chain when considering the
tuple $(\theta_{n},m_{n},v_{n})_{n\geq n_{0}}$ as the process of states. When
doing so one faces the difficulty that the $\sqrt{v_{n}^{(i)}}$-term in the
definition of $\sigma_{n}^{(i)}$ is not Lipschitz which makes it hard to
analyse the system. We bypass that problem by interpreting the Adam algorithm
as a delay equation where the evolution is governed by the whole history of
innovations that are considered as an element of an infinite dimensional
sequence space which we refer to as Adam sequence space.

######  Definition 2.3 (Adam sequence space).

Let $\alpha,\beta\in[0,1)$, $\epsilon\in(0,\infty)$ with $\alpha<\sqrt{\beta}$
be damping factors. We let

$\displaystyle\varrho_{k}=(1-\alpha)\epsilon^{-1}\Bigl{(}\alpha^{-k}+\frac{1}{\sqrt{1-\alpha^{2}/\beta}}\beta^{-k/2}\Bigr{)},\qquad\text{
for all $k\in-{\mathbb{N}}_{0}$},$ (6)

and denote by $\ell^{d}_{\varrho}$ the space of all sequences
$\mathbf{x}=(x_{k})_{k\in-{\mathbb{N}}_{0}}\in({\mathbb{R}}^{d})^{-{\mathbb{N}}_{0}}$
with

$\displaystyle\begin{split}\|\mathbf{x}\|_{\ell_{\varrho}^{d}}:=\sum_{k\in-{\mathbb{N}}_{0}}\rho_{k}\,|x_{k}|<\infty.\end{split}$
(7)

We equip the space with the norm $\|\cdot\|_{\ell_{\varrho}^{d}}$. Moreover,
we let for a tuple $(m,v)\in{\mathbb{R}}^{d}\times[0,\infty)^{d}$

$\displaystyle\begin{split}(m,v)_{\ell_{\varrho}^{d}}=\inf\Bigl{\\{}\|\mathbf{x}\|_{\ell_{\varrho}^{d}}:\mathbf{x}\in\ell_{\varrho}^{d},\
&m=(1-\alpha)\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}x_{k}\text{ \ and }\\\
&v^{(i)}=(1-\beta)\sum_{k\in-{\mathbb{N}}_{0}}\beta^{-k}(x_{k}^{(i)})^{2}\text{
for }i=1,\dots,d\Bigr{\\}},\end{split}$ (8)

where the infimum of the empty set is $\infty$.

Our main result is an ODE approximation for the Adam algorithm. The respective
vector field driving the ODE is defined in the following definition.

######  Definition 2.4 (Adam vector field).

For a tuple $(\alpha,\beta,\epsilon)$ of damping parameters and an innovation
$(X,U)$ we call the mapping $f:{\mathbb{R}}^{d}\to{\mathbb{R}}^{d}$ given by

$\displaystyle\begin{split}f^{(i)}(\theta)=(1-\alpha)\,{\mathbb{E}}^{\theta}\Bigl{[}1/\Bigl{(}\sqrt{(1-\beta)\sum_{k\in-{\mathbb{N}}_{0}}\beta^{-k}X^{(i)}(U_{k},\theta)^{2}}+\epsilon\Bigr{)}\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}X^{(i)}(U_{k},\theta)\Bigr{]}\end{split}$
(9)

with $(U_{k})_{k\in-{\mathbb{N}}_{0}}$ being a family of independent copies of
$U$, the _Adam vector field of the innovation $(X,U)$ for the damping
parameters $(\alpha,\beta,\epsilon)$_.

######  Theorem 2.5 (Convergence rates for the Adam optimizer).

Let

  1. (I)

$\alpha,\beta\in[0,1)$ with $\alpha<\sqrt{\beta}$ and $\epsilon\in(0,\infty)$
(the _damping parameters_),

  2. (II)

a decreasing $(0,\infty)$-valued zero-sequence
$(\gamma_{n})_{n\in{\mathbb{N}}}$ (_sequence of step-sizes_),

  3. (III)

${\mathcal{K}},c_{1},c_{2}\in[0,\infty)$ and $p\in(2,\infty)$,

  4. (IV)

$\|\cdot\|$ a norm on ${\mathbb{R}}^{d}$ being induced by a scalar product
$\llangle\cdot,\cdot\rrangle$

and suppose that

$\displaystyle\begin{split}\limsup_{n\to\infty}\frac{\gamma_{n}-\gamma_{n+1}}{\gamma_{n}^{2}}\leq
2c_{2}<2c_{1}.\end{split}$ (10)

Then for every $c\in(0,c_{1}-c_{2})$ and $\varepsilon\in(0,\infty)$ there
exist $\mathfrak{n}\in{\mathbb{N}}_{0}$ and $\eta\in(0,\infty)$ so that the
following statement is true.

  1. (i)

_Innovation._ Let $(X,U)$ be an innovation and $V\subset{\mathbb{R}}^{d}$ a
measurable set such that for every $\theta,\theta^{\prime}\in V$

$\displaystyle\begin{split}{\mathbb{E}}[|X(U,\theta)|^{p}]^{1/p}\leq{\mathcal{K}}\text{
\ and \
}{\mathbb{E}}[|X(U,\theta)-X(U,\theta^{\prime})|^{p}]^{1/p}\leq{\mathcal{K}}\,|\theta-\theta^{\prime}|.\end{split}$
(11)

  2. (ii)

_Adam algorithm._ Let $n_{0}\in{\mathbb{N}}_{0}\cap[\mathfrak{n},\infty)$ and
$(\theta_{n})_{n\geq n_{0}}$ be an Adam algorithm with innovation $(X,U)$
started at time $n_{0}$ in a state
$(\theta_{n_{0}},m_{n_{0}},v_{n_{0}})\in{\mathbb{R}}^{d}\times{\mathbb{R}}^{d}\times[0,\infty)^{d}$
so that

$\displaystyle\begin{split}\sqrt{\gamma_{n_{0}+1}}\,(m_{n_{0}},v_{n_{0}})_{\ell_{\varrho}^{d}}\leq{\mathcal{K}}.\end{split}$
(12)

  3. (iii)

_ODE._ Let $f:{\mathbb{R}}^{d}\to{\mathbb{R}}^{d}$ the Adam vector field of
the innovation $(X,U)$ for the damping parameters $(\alpha,\beta,\epsilon)$
and $\Psi:[t_{n_{0}},\infty)\to{\mathbb{R}}^{d}$ a solution to the ODE

$\dot{\Psi}_{t}=f(\Psi_{t})$

staying in $V\subset{\mathbb{R}}^{d}$ and satisfying

$\displaystyle\begin{split}\|\theta_{n_{0}}-\Psi_{t_{n_{0}}}\|\leq{\mathcal{K}}.\end{split}$
(13)

  4. (iv)

_Local monotonicity of ODE._ Let $(\mathfrak{R}_{t})_{t\geq t_{n_{0}}}$ be a
$(0,\infty]$-valued function so that one has, for all $t\in[t_{n_{0}},\infty)$
and $x\in V\cap\overline{B(\Psi_{t},\mathfrak{R}_{t})}$ , that

$\displaystyle\begin{split}{\llangle f(x)-f(\Psi_{t}),x-\Psi_{t}\rrangle\leq-
c_{1}\|x-\Psi_{t}\|^{2}.}\end{split}$ (14)

  5. (v)

Let $(R_{s})_{s\geq t_{n_{0}}}$ be a decreasing $(0,\infty)$-valued function
such that for every $s\geq t_{n_{0}}$

$\displaystyle\begin{split}R_{s}/R_{s+1}\leq{\mathcal{K}}.\end{split}$ (15)

Let

$\displaystyle\begin{split}\mathfrak{N}=\inf\\{n\geq n_{0}:\theta_{n}\not\in
V\text{ \ or \
}{\|\theta_{n}-\Psi_{t_{n}}\|>\mathfrak{R}_{t_{n}}}\\}.\end{split}$ (16)

One has, for all $n\in{\mathbb{N}}_{0}\cap[n_{0},\infty)$, that

$\displaystyle\begin{split}{\mathbb{E}}[1\mathrm{l}_{\\{\mathfrak{N}\geq
n\\}}{\|\theta_{n}-\Psi_{t_{n}}\|^{p}}]^{1/p}\leq\Bigl{(}\eta+\Bigl{(}(1+\varepsilon)\frac{{\|\theta_{n_{0}}-\Psi_{t_{n_{0}}}\|}}{\sqrt{\gamma_{n_{0}+1}}}+\eta\sqrt{(m_{n_{0}},v_{n_{0}})_{\ell_{\varrho}^{d}}}\Bigr{)}e^{-c(t_{n}-t_{n_{0}})}\Bigr{)}\sqrt{\gamma_{n+1}}\end{split}$
(17)

and

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}&\Bigl{(}\sup_{n:n_{0}\leq
n\leq\mathfrak{N}}\frac{\|\theta_{n}-\Psi_{t_{n}}\|}{R_{t_{n}}}\Bigr{)}^{p}\Bigr{]}\\\
&\leq\eta\int_{t_{n_{0}}}^{\infty}R_{s}^{-p}\Bigl{(}1+\Bigl{(}\frac{\|\theta_{n_{0}}-\Psi_{t_{n_{0}}}\|}{\sqrt{\gamma_{n_{0}+1}}}+\sqrt{(m_{n_{0}},v_{n_{0}})_{\ell_{\varrho}^{d}}}\Bigr{)}e^{-c(s-t_{n_{0}})}\Bigr{)}^{p}\,\Gamma_{s}^{(p-1)/2}\,\mathrm{d}s,\end{split}$
(18)

where $(\Gamma_{t})_{t>0}$ is the real-valued function given by
$\Gamma_{t}=\gamma_{n}$, for $n\in{\mathbb{N}}$ and $t\in(t_{n-1},t_{n}]$.

##  3 The innovation viewed as a non-expansive mapping on the Adam sequence
space

Let $\alpha,\beta,\epsilon\in[0,\infty)$ with $\alpha<\sqrt{\beta}<1$ and let
$(\varrho_{k})_{k\in-{\mathbb{N}}_{0}}$ as in 6. In this section our main goal
is to analyse the mapping

$\displaystyle\begin{split}g\colon\ell_{\varrho}^{d}\to{\mathbb{R}}^{d},\qquad\mathbf{x}=(x_{k})_{k\in-{\mathbb{N}}_{0}}\mapsto\Biggl{(}\frac{(1-\alpha)\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}x^{(i)}_{k}}{\epsilon+\sqrt{(1-\beta)\sum_{k\in-{\mathbb{N}}_{0}}\beta^{-k}(x^{(i)}_{k})^{2}}}\Biggr{)}_{i\in\\{1,\dots,d\\}}\end{split}$
(19)

(see Lemma 3.1 below). First, we note that $g$ is well defined since for every
$\mathbf{x}\in\ell_{\varrho}^{d}$ and $i\in\\{1,\dots,d\\}$ we have that the
series in the nominator in 19 is summable. The denominator in 19 may attain
the value $\infty$ in which case $g$ is defined to be zero.

######  Lemma 3.1.

Let $\alpha,\beta,\epsilon\in[0,\infty)$ with $\alpha<\sqrt{\beta}<1$ and let
$(\varrho_{k})_{k\in-{\mathbb{N}}_{0}}$ and $g$ as defined in 6 and 19,
respectively. Then $g$ is Lipschitz continuous with Lipschitz constant $1$ and
$g$ is uniformly bounded by
$\sqrt{d}\frac{1-\alpha}{\sqrt{1-\beta}}\frac{1}{\sqrt{1-\alpha^{2}/\beta}}$.

###### Proof.

We first assume that $d=1$ and briefly write
$\ell_{\varrho}=\ell_{\varrho}^{1}$ and
$\|\cdot\|_{\ell_{\varrho}}=\|\cdot\|_{\ell_{\varrho}^{1}}$. For
$\mathbf{x}\in\ell_{\varrho}$, let

$\displaystyle\begin{split}m(\mathbf{x})=(1-\alpha)\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}x_{k}\text{
\ and \
}v(\mathbf{x})=(1-\beta)\sum_{k\in-{\mathbb{N}}_{0}}\beta^{-k}x_{k}^{2}\end{split}$
(20)

so that

$\displaystyle\begin{split}g(\mathbf{x})=\frac{m(\mathbf{x})}{\sqrt{v(\mathbf{x})}+\epsilon}.\end{split}$
(21)

Using Cauchy-Schwarz and the fact that $\alpha<\sqrt{\beta}$ we get that for
all $\mathbf{x}\in\ell_{\varrho}$

$\displaystyle\begin{split}|m(\mathbf{x})|&=\Bigl{|}(1-\alpha)\sum_{k=-\infty}^{0}(\alpha/\sqrt{\beta})^{-k}\sqrt{\beta}^{-k}x_{k}\Bigr{|}\leq(1-\alpha)\Bigl{(}\sum_{k=0}^{\infty}(\alpha/\sqrt{\beta})^{2k}\Bigr{)}^{1/2}\Bigl{(}\sum_{k=-\infty}^{0}\beta^{-k}x_{k}^{2}\Bigr{)}^{1/2}\\\
&\leq\frac{1-\alpha}{\sqrt{1-\beta}}\frac{1}{\sqrt{1-\alpha^{2}/\beta}}\sqrt{v(\mathbf{x})}\end{split}$
(22)

which entails the uniform bound for $g$ that is stated in the lemma for $d=1$.
The multivariate estimates follows immediately by applying this estimate onto
the individual components.

To prove the Lipschitz continuity we again focus at first on the case $d=1$.
Fix $n\in{\mathbb{N}}$ and let
$\mathbf{x}=(x_{0},\dots,x_{-n},0,\dots)\in\ell_{\varrho}$. One has for all
$k=0,\dots,-n$ that

$\displaystyle\begin{split}\partial_{x_{k}}g(\mathbf{x})=(1-\alpha)\alpha^{-k}\frac{1}{\sqrt{v(\mathbf{x})}+\epsilon}-(1-\beta)\beta^{-k}\frac{m(\mathbf{x})}{(\sqrt{v(\mathbf{x})}+\epsilon)^{2}}\frac{1}{\sqrt{v(\mathbf{x})}}x_{k}\end{split}$
(23)

so that by using (22) and
$\sqrt{v(\mathbf{x})}\geq\sqrt{1-\beta}\beta^{-k/2}|x_{k}|$ we get that

$\displaystyle\begin{split}|\partial_{x_{k}}g(\mathbf{x})|\leq(1-\alpha)\epsilon^{-1}\alpha^{-k}+\frac{1-\alpha}{\sqrt{1-\alpha^{2}/\beta}}\epsilon^{-1}\beta^{-k/2}=\varrho_{k}.\end{split}$
(24)

For another
$\tilde{\mathbf{x}}=(\tilde{x}_{0},\dots,\tilde{x}_{-n},0,\dots)\in\ell_{\varrho}$
we let, for $\ell=0,\dots,n+1$,

$\displaystyle\begin{split}\mathbf{x}^{\ell}=(\tilde{x}_{0},\dots,\tilde{x}_{-\ell+1},x_{-\ell},\dots,x_{-n},0,\dots).\end{split}$
(25)

Note that $\mathbf{x}^{0}=\mathbf{x}$ and
$\mathbf{x}^{n+1}=\tilde{\mathbf{x}}$ and we get with the triangle inequality
and the mean value theorem that

$\displaystyle\begin{split}|g(\mathbf{x})-g(\tilde{\mathbf{x}})|\leq\sum_{\ell=0}^{n}|g(\mathbf{x}^{\ell})-g(\mathbf{x}^{\ell+1})|\leq\sum_{\ell=0}^{n}\varrho_{-\ell}|x_{-\ell}-\tilde{x}_{-\ell}|=\|\mathbf{x}-\tilde{\mathbf{x}}\|_{\ell_{\varrho}}.\end{split}$
(26)

This inequality remains true for general
$\mathbf{x},\tilde{\mathbf{x}}\in\ell_{\varrho}$ since

$\displaystyle\begin{split}g(\mathbf{x})=\lim_{n\to\infty}g(x_{0},\dots,x_{-n},0,\dots).\end{split}$
(27)

Indeed, this entails that

$\displaystyle\begin{split}|g(\mathbf{x})-g(\tilde{\mathbf{x}})|\leq\limsup_{n\to\infty}|g(x_{0},\dots,x_{-n},0,\dots)-g(\tilde{x}_{0},\dots,\tilde{x}_{-n},0,\dots)|\leq\|\mathbf{x}-\tilde{\mathbf{x}}\|_{\ell_{\varrho}}.\end{split}$
(28)

To obtain the result in the multivariate setting we proceed as above. Fix
$n\in{\mathbb{N}}$,
$\mathbf{x}=(x_{0},\dots,x_{-n},0,\dots)\in\ell_{\varrho}^{d}$ and
$\tilde{\mathbf{x}}=(\tilde{x}_{0},\dots,\tilde{x}_{-n},0,\dots)\in\ell_{\varrho}^{d}$
and define for every $\ell=0,\dots,n+1$,
$\mathbf{x}^{\ell}\in\ell_{\varrho}^{d}$ accordingly. Then one has for every
$\ell=0,\dots,n$ that

$\displaystyle\begin{split}|g(\mathbf{x}^{\ell})-g(\mathbf{x}^{\ell+1})|=\Bigl{(}\sum_{i=1}^{d}|g(\mathbf{x}^{\ell,(i)})-g(\mathbf{x}^{\ell+1,(i)})|^{2}\Bigr{)}^{1/2}\leq\varrho_{-\ell}\Bigl{(}\sum_{i=1}^{d}|x_{\ell}^{(i)}-\tilde{x}_{\ell}^{(i)}|^{2}\Bigr{)}^{1/2},\end{split}$
(29)

where we applied (24) for each of the $d$ components. This entails the
multivariate variant of estimate (26) that is

$\displaystyle\begin{split}|g(\mathbf{x})-g(\tilde{\mathbf{x}})|\leq\|\mathbf{x}-\tilde{\mathbf{x}}\|_{\ell^{d}_{\varrho}}.\end{split}$
(30)

The rest follows in complete analogy to the one dimensional setting. ∎

######  Lemma 3.2.

For every $k\in-{\mathbb{N}}_{0}$, one has that
$\varrho_{k-1}\leq\sqrt{\beta}\varrho_{k}$ and the translation operator

$\displaystyle\begin{split}T\colon\ell_{\varrho}^{d}\to\ell_{\varrho}^{d},\qquad\mathbf{x}=(x_{k})_{k\in-{\mathbb{N}}_{0}}\mapsto(1\mathrm{l}_{\\{k\not=0\\}}x_{k+1})_{k\in-{\mathbb{N}}_{0}}\end{split}$
(31)

is Lipschitz continuous with Lipschitz constant $\sqrt{\beta}<1$. In
particular, it maps $\ell_{\varrho}$ to $\ell_{\varrho}$.

###### Proof.

By definition of $(\varrho_{k})$ it immediately follows that, for every
$k\in-{\mathbb{N}}_{0}$,

$\displaystyle\begin{split}\varrho_{k-1}\leq\sqrt{\beta}\varrho_{k}.\end{split}$
(32)

Consequently, one has that, for every $\mathbf{x}\in\ell_{\varrho}^{d}$,

$\displaystyle\begin{split}\|T(\mathbf{x})\|_{\ell_{\varrho}^{d}}=\sum_{k\in-{\mathbb{N}}_{0}}\varrho_{k-1}|x_{k}|\leq\sqrt{\beta}\sum_{k\in-{\mathbb{N}}_{0}}\varrho_{k}|x_{k}|=\sqrt{\beta}\,\|\mathbf{x}\|_{\ell_{\varrho}^{d}}.\end{split}$
(33)

The statement follows by linearity of $T$. ∎

##  4 Analysis of the Adam evolution with fixed $\theta$-parameter

Let us introduce the setting of this section. Let $(X,U)$ be an innovation and
$(\alpha,\beta,\epsilon)$ be damping parameters with
$0\leq\alpha<\sqrt{\beta}<1$. The Adam algorithm for the innovation $(X,U)$ is
a stochastic process where in its iterative definition in 4 the momentum and
damping terms are updated by using the current $\theta$-value of the process.
In this section, we analyse a similar process where we keep the $\theta$-value
that is used when updating the momentum and damping term fixed.

In the following, fix $\theta\in{\mathbb{R}}^{d}$ and let
$(U_{k})_{k\in{\mathbb{Z}}}$ be an i.i.d. sequence of copies of $U$. Moreover,
for every $n\in{\mathbb{Z}}$, let $X_{n}=X(U_{n},\theta)$ and
$\mathbf{X}(n)=(X_{n+k})_{k\in-{\mathbb{N}}_{0}}$. We fix
$n_{0}\in{\mathbb{N}}_{0}$ and consider the process $(\bar{\Theta}_{n})_{n\geq
n_{0}}$ given by

$\displaystyle\begin{split}\bar{\Theta}_{n}=\sum_{k=n_{0}+1}^{n}\gamma_{k}\,g(\mathbf{X}(k)).\end{split}$
(34)

######  Lemma 4.1.

Let $p\in[2,\infty)$. One has for every $n\in{\mathbb{N}}_{0}$ with $n\geq
n_{0}$ that

$\displaystyle\begin{split}{\mathbb{E}}\bigl{[}|\bar{\Theta}_{n}-{\mathbb{E}}[\bar{\Theta}_{n}]|^{p}\bigr{]}^{2/p}\leq\kappa^{2}\sum_{k=n_{0}+1}^{n}\gamma_{k}^{2}\,{\mathbb{E}}\bigl{[}|X(U,\theta)-{\mathbb{E}}[X(U,\theta)]|^{p}\bigr{]}^{2/p},\end{split}$
(35)

where

$\displaystyle\begin{split}\kappa=2C_{p}\bigl{(}(1-\sqrt{\beta})^{-2}\varrho_{0}\|\varrho\|_{\ell_{1}}+\|\varrho\|_{\ell_{1}}^{2}\bigr{)},\end{split}$
(36)

$\varrho$ is as in (6) and $C_{p}$ is the constant appearing in the the
Burkholder-Davis-Gundy inequality for the $p$-th moment.

###### Proof.

For ease of notation we prove the statement for $d=1$. The generalisation to
general $d$ is straight-forward. Let $\tilde{X}_{0}$ be identically
distributed as $X_{0}$ and independent of the sequence
$(X_{n})_{n\in{\mathbb{Z}}}$ and set $\tilde{X}_{n}=X_{n}$ for
$n\in{\mathbb{Z}}\backslash\\{0\\}$. We let

$\displaystyle\begin{split}\tilde{\mathbf{X}}(n)=(\tilde{X}_{n+k})_{k\in-{\mathbb{N}}_{0}}.\end{split}$
(37)

Thus $\tilde{\mathbf{X}}(n)$ agrees with $\mathbf{X}(n)$ in all but at most
one component.

We let $(\mathcal{F}_{n})_{n\in{\mathbb{Z}}}$ be the filtration generated by
$(X_{n})$ and consider for fixed $N\geq n_{0}$ the martingale
$(M_{n})_{n\in{\mathbb{Z}}}$ given by

$\displaystyle\begin{split}M_{n}={\mathbb{E}}[\bar{\Theta}_{N}|\mathcal{F}_{n}]-{\mathbb{E}}[\bar{\Theta}_{N}]\end{split}$
(38)

We denote by $([M]_{n})_{n\in{\mathbb{Z}}}$ its quadratic variation process
being defined by

$\displaystyle\begin{split}[M]_{n}=\sum_{r=-\infty}^{n}(M_{r}-M_{r-1})^{2}\end{split}$
(39)

and analyse the $q/2$-th moment of its increments
$\Delta[M]_{n}:=(M_{n}-M_{n-1})^{2}$. Note that for every
$n\in{\mathbb{Z}}\cap(-\infty,N]$, one has that

$\displaystyle\begin{split}\Delta
M_{n}={\mathbb{E}}[\bar{\Theta}_{N}|\mathcal{F}_{n}]-{\mathbb{E}}[\bar{\Theta}_{N}|\mathcal{F}_{n-1}]={\mathbb{E}}\Bigl{[}\sum_{r=n_{0}+1}^{N}\gamma_{r}g(\mathbf{X}(r))|\mathcal{F}_{n}\Bigr{]}-{\mathbb{E}}\Bigl{[}\sum_{r=n_{0}+1}^{N}\gamma_{r}g(\mathbf{X}(r))|\mathcal{F}_{n-1}\Bigr{]}.\end{split}$
(40)

Now using that $(X_{n})$ is an i.i.d. sequence we conclude that, for almost
all $\omega\in\Omega$,

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\sum_{r=n_{0}+1}^{N}\gamma_{r}g(\mathbf{X}(r))\Big{|}\mathcal{F}_{n}\Bigr{]}(\omega)={\mathbb{E}}\Bigl{[}\sum_{r=n_{0}+1}^{N}\gamma_{r}g(\mathbf{X}(r-n))\Big{|}\forall
k\in-{\mathbb{N}}_{0}:X_{k}=X_{k+n}(\omega)\Bigr{]}\end{split}$ (41)

and

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\sum_{r=n_{0}+1}^{N}\gamma_{r}g(\mathbf{X}(r))\Big{|}\mathcal{F}_{n-1}\Bigr{]}(\omega)&={\mathbb{E}}\Bigl{[}\sum_{r=n_{0}+1}^{N}\gamma_{r}g(\mathbf{X}(r-n))\Big{|}\forall
k\in-{\mathbb{N}}:X_{k}=X_{k+n}(\omega)\Bigr{]}\\\
&={\mathbb{E}}\Bigl{[}\sum_{r=n_{0}+1}^{N}\gamma_{r}g(\tilde{\mathbf{X}}(r-n))\Big{|}\forall
k\in-{\mathbb{N}}_{0}:X_{k}=X_{k+n}(\omega)\Bigr{]}.\end{split}$ (42)

Consequently,

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}&\sum_{r=n_{0}+1}^{N}\gamma_{r}g(\mathbf{X}(r))\Big{|}\mathcal{F}_{n}\Bigr{]}(\omega)-{\mathbb{E}}\Bigl{[}\sum_{r=n_{0}+1}^{N}\gamma_{r}g(\mathbf{X}(r))\Big{|}\mathcal{F}_{n-1}\Bigr{]}(\omega)\\\
&={\mathbb{E}}\Bigl{[}\underbrace{\sum_{r=n_{0}+1}^{N}\gamma_{r}(g(\mathbf{X}(r-n))-g(\tilde{\mathbf{X}}(r-n)))}_{=:\Upsilon_{n}[N]}\Big{|}\forall
k\in-{\mathbb{N}}_{0}:X_{k}=X_{k+n}(\omega)\Bigr{]}.\end{split}$ (43)

By stationarity, the distribution of the conditional expectation

$\displaystyle\begin{split}\omega\mapsto{\mathbb{E}}\bigl{[}\Upsilon_{n}[N]\big{|}\forall
k\in-{\mathbb{N}}_{0}:X_{k}=X_{k+n}(\omega)\bigr{]}\end{split}$ (44)

is the same as the distribution of
${\mathbb{E}}\bigl{[}\Upsilon_{n}[N]\big{|}X_{0},X_{-1},\dots\bigr{]}$. Using
this and Jensen’s inequality we get that

$\displaystyle\begin{split}{\mathbb{E}}\bigl{[}\Delta[M]_{n}^{p/2}\bigr{]}={\mathbb{E}}\bigl{[}|M_{n}-M_{n-1}|^{p}\bigr{]}={\mathbb{E}}\bigl{[}\bigl{|}{\mathbb{E}}\bigl{[}\Upsilon_{n}[N]\big{|}X_{0},X_{-1},\dots\bigr{]}\bigr{|}^{p}\bigr{]}\leq{\mathbb{E}}\bigl{[}|\Upsilon_{n}[N]|^{p}\bigr{]}.\end{split}$
(45)

It follows with the triangle inequality that

$\displaystyle\begin{split}{\mathbb{E}}\bigl{[}[M]_{N}^{p/2}\bigr{]}^{2/p}={\mathbb{E}}\Bigl{[}\Bigl{(}\sum_{n=-\infty}^{N}\Delta[M]_{n}\Bigr{)}^{p/2}\Bigr{]}^{2/p}\leq\sum_{n=-\infty}^{N}{\mathbb{E}}\bigl{[}(\Delta[M]_{n})^{p/2}\bigr{]}^{2/p}\leq\sum_{n=-\infty}^{N}{\mathbb{E}}\bigl{[}|\Upsilon_{n}[N]|^{p}\bigr{]}^{2/p}.\end{split}$
(46)

Now for $n\in{\mathbb{Z}}$ with $n\leq N$ we get with Lemma 3.1 that

$\displaystyle\begin{split}|\Upsilon_{n}[N]|\leq\sum_{r=n\vee(n_{0}+1)}^{N}\gamma_{r}|g(\mathbf{X}(r-n))-g(\tilde{\mathbf{X}}(r-n))|\leq\sum_{r=n\vee(n_{0}+1)}^{N}\gamma_{r}\varrho_{n-r}|X_{0}-\tilde{X}_{0}|\end{split}$
(47)

and again by the triangle inequality we have in terms of
$C:={\mathbb{E}}[|X_{0}-{\mathbb{E}}[X_{0}]|^{p}]^{1/p}$,

$\displaystyle\begin{split}{\mathbb{E}}[|\Upsilon_{n}[N]|^{p}]^{1/p}&\leq\sum_{r=n\vee(n_{0}+1)}^{N}\gamma_{r}\varrho_{n-r}\,{\mathbb{E}}[|X_{0}-\tilde{X}_{0}|^{p}]^{1/p}\\\
&\leq\begin{cases}2C\|\varrho\|_{\ell_{1}}\gamma_{n},&\text{ if }n\geq
n_{0}+1,\\\
2C(1-\sqrt{\beta})^{-1}\varrho_{n-(n_{0}+1)}\gamma_{n_{0}+1},&\text{ if }n\leq
n_{0}.\end{cases}\end{split}$ (48)

Together with (46) we conclude that

$\displaystyle\begin{split}{\mathbb{E}}\bigl{[}[M]_{N}^{p/2}\bigr{]}^{2/p}&\leq\sum_{n=-\infty}^{N}{\mathbb{E}}[|\Upsilon_{n}[N]|^{p}]^{2/p}\\\
&\leq
4C^{2}(1-\sqrt{\beta})^{-2}\gamma_{n_{0}+1}^{2}\sum_{n=-\infty}^{n_{0}}\varrho_{n-(n_{0}+1)}^{2}+4C^{2}\|\varrho\|_{\ell_{1}}^{2}\sum_{n=n_{0}+1}^{N}\gamma_{n}^{2}\\\
&\leq
4C^{2}\Bigl{(}(1-\sqrt{\beta})^{-2}\varrho_{0}\|\varrho\|_{\ell_{1}}\gamma_{n_{0}+1}^{2}+\|\varrho\|_{\ell_{1}}^{2}\sum_{n=n_{0}+1}^{N}\gamma_{n}^{2}\Bigr{)}.\end{split}$
(49)

The statement follows with the Burkholder-Davis-Gundy inequality since
$\bar{\Theta}_{N}={\mathbb{E}}[\bar{\Theta}_{N}]+M_{N}$. ∎

Next, we derive an extension of the previous lemma that considers whole
trajectories instead of single time instances.

######  Lemma 4.2.

Let $p\in(2,\infty)$. One has for every $n\in{\mathbb{N}}_{0}$ with $n\geq
n_{0}$

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\max_{k=n_{0},\dots,n}|\bar{\Theta}_{k}-{\mathbb{E}}[\bar{\Theta}_{k}]|^{p}\Bigr{]}^{1/p}\leq(1-2^{-(\frac{1}{2}-\frac{1}{p})})^{-1}\kappa\gamma_{n_{0}+1}\sqrt{n-n_{0}}\,{\mathbb{E}}\bigl{[}|X_{0}-{\mathbb{E}}[X_{0}]|^{p}\bigr{]}^{1/p},\end{split}$
(50)

where $\kappa$ is as in (36).

###### Proof.

Without loss of generality we can assume that $n_{0}=0$ since the general
statement then follows by an index shift.

Suppose that $m\in{\mathbb{N}}$ and $2^{m-1}\leq N\leq 2^{m}-1$. We call for
every $k=1,\dots,m$, all intervals of the form

$\displaystyle\begin{split}[j,j+2^{m-k})\qquad(j\in(2^{m-k+1}{\mathbb{N}}_{0})\cap\\{0,\dots,N\\})\end{split}$
(51)

and additionally the empty set an interval of the $k$-th layer. Note that by
construction for every natural number $n\in\\{0,\dots,N\\}$ the interval
$[0,n)$ can be uniquely written as pairwise disjoint union

$\displaystyle\begin{split}[0,n)=[0,n_{1})\cup[n_{1},n_{2})\cup\ldots\cup[n_{m-1},n_{m})\end{split}$
(52)

with each $[n_{k-1},n_{k})$ being an interval of the $k$-th layer. Indeed, the
representation is obtained for $n_{k}=2^{m-k}\lfloor 2^{-(m-k)}n\rfloor$. We
let
$\bar{\Theta}_{k,\ell}:=\bar{\Theta}_{\ell}-\bar{\Theta}_{k}-{\mathbb{E}}[\bar{\Theta}_{\ell}-\bar{\Theta}_{k}]$
for every $k,\ell\in{\mathbb{N}}_{0}$ with $0\leq k\leq\ell$. Then for $n$ as
above we have

$\displaystyle\begin{split}\bar{\Theta}_{0,n}=\sum_{k=1}^{m}\bar{\Theta}_{n_{k-1},n_{k}}.\end{split}$
(53)

Consequently,

$\displaystyle\begin{split}\max_{n\in\\{0,\dots,N\\}}|\bar{\Theta}_{0,n}|\leq\sum_{k=1}^{m}\max_{[n_{k-1},n_{k}):\text{
interval of $k$th layer}}|\bar{\Theta}_{n_{k-1},n_{k}}|\end{split}$ (54)

and

$\displaystyle{\mathbb{E}}\Bigl{[}\max_{n\in\\{0,\dots,N\\}}|\bar{\Theta}_{0,n}|^{p}\Bigr{]}^{1/p}\leq\sum_{k=1}^{m}{\mathbb{E}}\Bigl{[}\max_{[n_{k-1},n_{k}):\text{
interval of $k$th layer}}|\bar{\Theta}_{n_{k-1},n_{k}}|^{p}\Bigr{]}^{1/p}.$
(55)

Now note that by Lemma 4.1 one has in terms of
$C:={\mathbb{E}}[|X_{0}-{\mathbb{E}}[X_{0}]|^{p}]^{1/p}$ that for an arbitrary
non-empty interval $[n_{k-1},n_{k})$ of the $k$-th layer

$\displaystyle\begin{split}{\mathbb{E}}[|\bar{\Theta}_{n_{k-1}:n_{k}}|^{p}]^{2/p}\leq\kappa^{2}\gamma_{1}^{2}2^{m-k}C^{2}\end{split}$
(56)

so that

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\max_{[n_{k-1},n_{k}):\text{
interval of $k$th
layer}}|\bar{\Theta}_{n_{k-1},n_{k}}|^{p}\Bigr{]}&\leq\sum_{[n_{k-1},n_{k}):\text{
interval of $k$th layer}}{\mathbb{E}}[|\bar{\Theta}_{n_{k-1},n_{k}}|^{p}]\\\
&\leq\kappa^{p}\gamma_{1}^{p}C^{p}2^{k-1}(2^{m-k})^{p/2}.\end{split}$ (57)

Together with (55) we obtain that

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\max_{n\in\\{0,\dots,N\\}}|\bar{\Theta}_{0,n}|^{p}\Bigr{]}^{1/p}\leq\kappa\gamma_{1}C\sqrt{2^{m-1}}\sum_{k=1}^{m}2^{-(\frac{1}{2}-\frac{1}{p})(k-1)}\leq(1-2^{-(\frac{1}{2}-\frac{1}{p})})^{-1}\kappa\gamma_{1}C\sqrt{N}.\end{split}$
(58)

∎

##  5 Introducing approximations of the Adam optimization processes

In the proof of Theorem 2.5, we will work with approximations to the Adam
algorithm that are sufficiently close but easier to analyse. For this we fix
damping parameters $\alpha,\beta,\epsilon\in[0,\infty)$ with
$\alpha<\sqrt{\beta}<1$ and an innovation $(X,U)$ and denote by
$(\theta_{n})_{n\geq n_{0}}$ an Adam algorithm started at time
$n_{0}\in{\mathbb{N}}_{0}$ in a state $(\theta_{n_{0}},m_{n_{0}},v_{n_{0}})$.
We assume that there exists a deterministic
$\mathbf{x}=(x_{k})_{k\in-{\mathbb{N}}_{0}}\in\ell_{\varrho}^{d}$ such that
for all $i\in\\{1,\dots,d\\}$ we have

$\displaystyle\begin{split}m_{n_{0}}=(1-\alpha)\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}x_{k}\qquad\text{and}\qquad
v^{(i)}_{n_{0}}=(1-\beta)\sum_{k\in-{\mathbb{N}}_{0}}\beta^{-k}(x^{(i)}_{k})^{2}.\end{split}$
(59)

We consider the ${\mathbb{R}}^{d}$-valued process $(X_{k})_{k\in{\mathbb{Z}}}$
given by

$\displaystyle\begin{split}X_{k}=\begin{cases}x_{k-n_{0}},&\text{ if }k\leq
n_{0},\\\ X(U_{k},\theta_{k-1}),&\text{ if }k>n_{0}\end{cases}\end{split}$
(60)

and we set for every $n\geq n_{0}$,
$\mathbf{X}(n)=(X_{n+k})_{k\in-{\mathbb{N}}_{0}}$.

The terms $m_{n}$ and $v_{n}$ (defined as in Def. 2.2) may be directly
represented as weighted series over the past innovations and we get that for
every $n\in{\mathbb{N}}$ and $i=1,\dots,d$ one has that

$\displaystyle\begin{split}\sigma^{(i)}_{n}m_{n}^{(i)}=\frac{(1-\alpha)\sum_{k=-\infty}^{0}\alpha^{-k}X^{(i)}_{n+k}}{\epsilon+\sqrt{(1-\beta)/(1-\beta^{n})\,\sum_{k=-\infty}^{0}\beta^{-k}(X^{(i)}_{n+k})^{2}}}.\end{split}$
(61)

Note that up to an additional factor $(1-\beta^{n})$ the latter expression
agrees with $g(\mathbf{X}^{(i)}(n))$ (cf. 19). This means that for large $n$
the increments of the process $(\theta_{n})$ are similar to the ones of the
process $(\Theta_{n})_{n\geq n_{0}}$ given by

$\displaystyle\begin{split}\Theta_{n}:=\sum_{k=n_{0}+1}^{n}\gamma_{k}\,g(\mathbf{X}(k)).\end{split}$
(62)

For technical reasons we will consider dynamical systems with simpler
dynamics. For this denote by $(n_{\ell})_{\ell\in{\mathbb{N}}_{0}}$ an
increasing ${\mathbb{N}}_{0}$-valued sequence tending to infinity. Here
deliberately the initial value $n_{0}$ of the series coincides with the
initial time of the Adam scheme. We will use the times in the sequence
$(n_{\ell})$ as update-times for the $\theta$-parameter similar to an Euler
approximation. More explicitly, we define for every $\ell\in{\mathbb{N}}$ and
$n\in\\{n_{\ell-1}+1,\dots,n_{\ell}\\}$, the process
$\tilde{\mathbf{X}}(n)=(\tilde{\mathbf{X}}(n)_{k})_{k\in-{\mathbb{N}}_{0}}$ by

$\displaystyle\begin{split}\tilde{\mathbf{X}}(n)_{k}=\begin{cases}X(U_{n+k},\theta_{n_{\ell-1}}),&\text{
\ if }n+k>n_{\ell-1},\\\ X_{n+k},&\text{ \ else.}\end{cases}\end{split}$ (63)

Comparing $\mathbf{X}(n)$ and $\tilde{\mathbf{X}}(n)$ we see that the terms
outside the $(n_{\ell-1},n_{\ell}]$-window agree and inside the window the
$\theta$-parameter is fixed as $\theta_{n_{\ell-1}}$. In analogy to before we
consider the process $(\tilde{\Theta}_{n})_{n\geq n_{0}}$ given by

$\displaystyle\begin{split}\tilde{\Theta}_{n}:=\sum_{k=n_{0}+1}^{n}\gamma_{k}\,g(\tilde{\mathbf{X}}(k)).\end{split}$
(64)

Next, let $(U_{\ell,n})_{\ell\in{\mathbb{N}},n\in{\mathbb{Z}}}$ be a family of
independent copies of $U$ that is also independent of
$(U_{n})_{n\in{\mathbb{N}}}$. For every $\ell\in{\mathbb{N}}$ and
$n\in\\{n_{\ell-1}+1,\dots,n_{\ell}\\}$, we consider
$\tilde{\tilde{\mathbf{X}}}(n)=(\tilde{\tilde{\mathbf{X}}}(n)_{k})_{k\in-{\mathbb{N}}_{0}}$
given by

$\displaystyle\begin{split}\tilde{\tilde{\mathbf{X}}}(n)_{k}=\begin{cases}X(U_{n+k},\theta_{n_{\ell-1}})=\tilde{\mathbf{X}}(n)_{k},&\text{
\ if }n+k>n_{\ell-1},\\\ X(U_{\ell,n+k},\theta_{n_{\ell-1}}),&\text{ \
else.}\end{cases}\end{split}$ (65)

In analogy to before we define a process $(\tilde{\tilde{\Theta}}_{n})_{n\geq
n_{0}}$ via

$\displaystyle\begin{split}\tilde{\tilde{\Theta}}_{n}=\sum_{k=n_{0}+1}^{n}\gamma_{k}\,g(\tilde{\tilde{\mathbf{X}}}(k)).\end{split}$
(66)

We see that in $\tilde{\tilde{\mathbf{X}}}(n)$ and $\tilde{\mathbf{X}}(n)$ the
terms inside the $(n_{\ell-1},n_{\ell}]$-window agree. Moreover, the terms are
chosen in such a way that conditionally on $\theta_{n_{\ell-1}}$,
$\tilde{\tilde{\mathbf{X}}}(n)$ is a sequence of i.i.d. random variables.
Roughly speaking, this entail that the related approximation is in “stationary
equilibrium”.

As last approximation we denote by $(\bar{\Theta}_{n})_{n\geq n_{0}}$ the
unique process satisfying for every $\ell\in{\mathbb{N}}$ and
$n=n_{\ell-1}+1,\dots,n_{\ell}$

$\displaystyle\begin{split}\Delta\bar{\Theta}_{n}:=\bar{\Theta}_{n}-\bar{\Theta}_{n-1}=\gamma_{n}f(\theta_{n_{\ell-1}})\end{split}$
(67)

and $\bar{\Theta}_{n_{0}}=0$.

In the analysis, we will impose the following regularity assumption on the
innovation.

######  Definition 5.1.

Let $C,\tilde{C},\tilde{L}\in[0,\infty)$, $p\in[2,\infty)$ and
$V\subset{\mathbb{R}}^{d}$ a measurable set. An innovation $(X,U)$ is called
_$p$ -regular with parameter $(C,\tilde{C},\tilde{L})$ on $V$_, if for every
$\theta,\theta^{\prime}\in V$, one has

$\displaystyle\begin{split}{\mathbb{E}}[|X(U,\theta)|^{2}]^{1/2}\leq C,\
&{\mathbb{E}}[|X(U,\theta)-{\mathbb{E}}[X(U,\theta)]|^{p}]^{1/p}\leq\tilde{C}\text{
\ and}\\\
&\qquad{\mathbb{E}}[|X(U,\theta)-X(U,\theta^{\prime})|^{p}]^{1/p}\leq\tilde{L}\,|\theta-\theta^{\prime}|.\end{split}$
(68)

We give a quantitative statement that allows us to control the error between
the Adam algorithm and its approximations.

######  Proposition 5.2.

Let

  1. (i)

$\alpha,\beta\in[0,1)$ with $\alpha<\sqrt{\beta}$ and $\epsilon\in(0,\infty)$
(the _damping parameters_),

  2. (ii)

$n_{0}\in{\mathbb{N}}_{0}$, $\theta_{n_{0}},m_{n_{0}}\in{\mathbb{R}}^{d}$,
$v_{n_{0}}\in[0,\infty)^{d}$ (the initialisation),

  3. (iii)

a decreasing $(0,\infty)$-valued sequence
$(\gamma_{n})_{n\in{\mathbb{N}}}$(_sequence of step-sizes_),

  4. (iv)

$(X,U)$ an innovation,

  5. (v)

$C,\tilde{C},\tilde{L}\in[0,\infty)$, $p\in[2,\infty)$ and
$V\subset{\mathbb{R}}^{d}$ be a measurable set,

  6. (vi)

$(n_{\ell})_{\ell\in{\mathbb{N}}_{0}}$ be a strictly increasing
${\mathbb{N}}_{0}$-valued sequence.

Let $(X,U)$ be a $p$-regular innovation with parameter
$(C,\tilde{C},\tilde{L})$ on $V$ and
$(\theta_{n})_{n\in{\mathbb{N}}_{0}\cap[n_{0},\infty)}$ the Adam algorithm
with damping parameter $(\alpha,\beta,\epsilon)$ and step-sizes $(\gamma_{n})$
started at time $n_{0}$ in $(\theta_{n_{0}},m_{n_{0}},v_{n_{0}})$. Moreover,
let

$\displaystyle\begin{split}\mathfrak{N}=\inf\\{n\geq n_{0}:\theta(n)\not\in
V\\}\end{split}$ (69)

and let $(t_{n})_{n\in{\mathbb{N}}}$ as in (5). One has the following for the
approximations $(\Theta_{n})_{n\geq n_{0}}$, $(\tilde{\Theta}_{n})_{n\geq
n_{0}}$ and $(\tilde{\tilde{\Theta}}_{n})_{n\geq n_{0}}$:

  1. (I)

for every $\mathfrak{n}\in\\{n_{0},n_{0}+1,\dots\\}$,

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\Bigl{(}\sum_{k=\mathfrak{n}+1}^{\infty}1\mathrm{l}_{\\{\mathfrak{N}\geq
k\\}}|\Delta\theta_{k}-\Delta\Theta_{k}|\Bigr{)}^{p}\Bigr{]}^{1/p}&\leq\bigl{(}\kappa_{1}\beta^{\frac{1}{2}(\mathfrak{n}+1)-n_{0}}\|\mathbf{x}\|_{\ell^{d}_{\varrho}}+\kappa_{2}C\bigr{)}\gamma_{\mathfrak{n}+1}\beta^{\mathfrak{n}+1}\end{split}$
(70)

  2. (II)

for every $\ell\in{\mathbb{N}}$ and $\mathfrak{n},n\in{\mathbb{N}}_{0}$ with
$n_{\ell-1}\leq\mathfrak{n}\leq n\leq n_{\ell}$,

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\Bigl{(}\sum_{k=\mathfrak{n}+1}^{n}1\mathrm{l}_{\\{\mathfrak{N}\geq
k\\}}|\Delta\Theta_{k}-\Delta\tilde{\Theta}_{k}|\Bigr{)}^{p}\Bigr{]}^{1/p}&\leq\kappa_{3}\tilde{L}(t_{n_{\ell}}-t_{n_{\ell-1}})(t_{n}-t_{\mathfrak{n}})\end{split}$
(71)

  3. (III)

for every $\ell\in{\mathbb{N}}$,

$\displaystyle{\mathbb{E}}\Bigl{[}$ $\displaystyle
1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}\Bigl{(}\sum_{k=n_{\ell-1}+1}^{n_{\ell}}\bigl{|}\Delta{\tilde{\Theta}}_{k}-\Delta\tilde{\tilde{\Theta}}_{k}\bigr{|}\Bigr{)}^{p}\Bigr{]}^{1/p}\leq\gamma_{n_{\ell-1}+1}\bigl{(}\kappa_{4}C+\kappa_{5}\beta^{(n_{\ell-1}-n_{0})/2}\|\mathbf{x}\|_{\ell_{\varrho}^{d}}),$
(72)

  4. (IV.a)

for every $\ell\in{\mathbb{N}}$,

$\displaystyle\begin{split}{\mathbb{E}}[1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}|\tilde{\tilde{\Theta}}_{n_{\ell}}-\tilde{\tilde{\Theta}}_{n_{\ell-1}}-(t_{n_{\ell}}-t_{n_{\ell-1}})f(\theta_{n_{\ell-1}})|^{p}|\mathcal{F}_{n_{\ell-1}}]^{1/p}\leq\kappa_{6}\tilde{C}\Bigl{(}\sum_{k=n_{\ell-1}+1}^{n_{\ell}}\gamma_{k}^{2}\Bigr{)}^{1/2},\end{split}$
(73)

  5. (IV.b)

if $p>2$, then for every $\ell\in{\mathbb{N}}$,

$\displaystyle\begin{split}{\mathbb{E}}[1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}\max_{n=n_{\ell-1},\dots,n_{\ell}}|\tilde{\tilde{\Theta}}_{n}&-\tilde{\tilde{\Theta}}_{n_{\ell-1}}-(t_{n}-t_{n_{\ell-1}})f(\theta_{n_{\ell-1}})|^{p}|\mathcal{F}_{n_{\ell-1}}]^{1/p}\\\
&\leq(1-2^{-(\frac{1}{2}-\frac{1}{p})})^{-1}\kappa_{6}\tilde{C}\gamma_{n_{\ell-1}+1}\sqrt{n_{\ell}-n_{\ell-1}},\end{split}$
(74)

where

$\displaystyle\begin{split}&\kappa_{1}=\frac{2}{1-\beta^{3/2}},\
\kappa_{2}=\frac{2}{1-\beta^{3/2}}\bigl{(}\frac{\varrho_{0}}{1-\beta}+\|\varrho\|_{\ell_{1}}\bigr{)},\kappa_{3}=\frac{1-\alpha}{\sqrt{1-\beta}\sqrt{1-\alpha^{2}/\beta}}d\|\varrho\|_{\ell_{1}},\\\
&\kappa_{4}=2(1-\sqrt{\beta})^{-1}\|\varrho\|_{\ell_{1}},\
\kappa_{5}=(1-\sqrt{\beta})^{-1},\
\kappa_{6}=2C_{p}\bigl{(}(1-\sqrt{\beta})^{-1}\sqrt{\varrho_{0}\|\varrho\|_{\ell_{1}}}+\|\varrho\|_{\ell_{1}}\bigr{)},\end{split}$
(75)

$(\varrho_{k})$ is as in (6) and $C_{p}$ is the constant in the Burholder-
Davis-Gundy inequality when applied for the $p$th moment.

###### Proof.

1) We prove the first inequality. Note that

$\displaystyle\begin{split}\bigl{|}\sigma^{(i)}_{k}m_{k}^{(i)}-g(\mathbf{X}^{(i)}(k))\bigr{|}&\leq\Bigl{(}1-\frac{1}{\sqrt{1/(1-\beta^{k})}}\Bigr{)}|g(\mathbf{X}^{(i)}(k))|\leq
2\beta^{k}\|\mathbf{X}^{(i)}(k)\|_{\ell_{\varrho}}\\\ &\leq
2\beta^{k}\Bigl{(}{\sqrt{\beta}}^{k-n_{0}}\|\mathbf{x}^{(i)}\|_{\ell_{\varrho}}+\sum_{r=n_{0}+1}^{k}\varrho_{r-k}|X^{(i)}_{r}|\Bigr{)}.\end{split}$
(76)

This entails that

$\displaystyle\begin{split}{\mathbb{E}}[1\mathrm{l}_{\\{\mathfrak{N}\geq
k\\}}|\Delta\theta_{k}-\Delta\Theta_{k}|^{p}]^{1/p}\leq
2\beta^{k}\Bigl{(}{\sqrt{\beta}}^{k-n_{0}}\|\mathbf{x}\|_{\ell^{d}_{\varrho}}+C\sum_{r=n_{0}+1}^{k}\varrho_{r-k}\Bigr{)}.\end{split}$
(77)

Consequently,

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\Bigl{(}\sum_{k=\mathfrak{n}+1}^{\infty}1\mathrm{l}_{\\{\mathfrak{N}\geq
k\\}}\gamma_{k}&|\Delta\theta_{k}-\Delta\Theta_{k}|\Bigr{)}^{p}\Bigr{]}^{1/p}\leq
2\sum_{k=\mathfrak{n}+1}^{\infty}\gamma_{k}\beta^{k}\Bigl{(}{\sqrt{\beta}}^{k-n_{0}}\|\mathbf{x}\|_{\ell^{d}_{\varrho}}+C\sum_{r=n_{0}+1}^{k}\varrho_{r-k}\Bigr{)}\\\
&\leq
2(1-\beta^{3/2})^{-1}\gamma_{\mathfrak{n}+1}\beta^{\frac{3}{2}(\mathfrak{n}+1)-n_{0}}\|\mathbf{x}\|_{\ell^{d}_{\varrho}}+2C\gamma_{\mathfrak{n}+1}\sum_{r=n_{0}+1}^{\infty}\sum_{k=r\vee(\mathfrak{n}+1)}^{n}\beta^{k}\varrho_{r-k}\end{split}$
(78)

In the case where $r\leq\mathfrak{n}$, one has that

$\displaystyle\begin{split}\sum_{k=r\vee(\mathfrak{n}+1)}^{n}\beta^{k}\varrho_{r-k}\leq(1-\beta^{3/2})^{-1}\varrho_{r-(\mathfrak{n}+1)}\beta^{\mathfrak{n}+1}\end{split}$
(79)

and in the case where $r>\mathfrak{n}$,

$\displaystyle\begin{split}\sum_{k=r\vee(\mathfrak{n}+1)}^{n}\beta^{k}\varrho_{r-k}\leq(1-\beta^{3/2})^{-1}\varrho_{0}\beta^{r}.\end{split}$
(80)

Hence,

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}&\Bigl{(}\sum_{k=\mathfrak{n}+1}^{\infty}1\mathrm{l}_{\\{\mathfrak{N}\geq
k\\}}\gamma_{k}|\Delta\theta_{k}-\Delta\Theta_{k}|\Bigr{)}^{p}\Bigr{]}^{1/p}\\\
&\leq
2(1-\beta^{3/2})^{-1}\gamma_{\mathfrak{n}+1}\Bigl{(}\beta^{\frac{3}{2}(\mathfrak{n}+1)-n_{0}}\|\mathbf{x}\|_{\ell^{d}_{\varrho}}+\beta^{\mathfrak{n}+1}C\sum_{r=n_{0}+1}^{\mathfrak{n}}\varrho_{r-(\mathfrak{n}+1)}+C\sum_{r=\mathfrak{n}+1}^{n}\varrho_{0}\beta^{r}\Bigr{)}\\\
&\leq
2(1-\beta^{3/2})^{-1}\bigl{(}\beta^{\frac{1}{2}(\mathfrak{n}+1)-n_{0}}\|\mathbf{x}\|_{\ell^{d}_{\varrho}}+(\|\varrho\|_{\ell_{1}}+(1-\beta)^{-1}\varrho_{0})C\bigr{)}\gamma_{\mathfrak{n}+1}\beta^{\mathfrak{n}+1}.\end{split}$
(81)

2.) Fix $\ell\in{\mathbb{N}}$. Since for every $k\geq n_{0}$

$\displaystyle\begin{split}\sigma^{(i)}_{k}m^{(i)}_{k}\leq\frac{1-\alpha}{\sqrt{1-\beta}}\frac{1}{\sqrt{1-\alpha^{2}/\beta}},\end{split}$
(82)

one has for every $n=n_{\ell-1}+1,\dots,n_{\ell}$

$\displaystyle\begin{split}|\theta_{n}^{(i)}-\theta_{n_{\ell-1}}^{(i)}|=\Bigl{|}\sum_{k=n_{\ell-1}+1}^{n}\gamma_{k}\,\sigma^{(i)}_{k}m^{(i)}_{k}\Bigr{|}\leq\frac{1-\alpha}{\sqrt{1-\beta}}\frac{1}{\sqrt{1-\alpha^{2}/\beta}}(t_{n}-t_{n_{\ell-1}}).\end{split}$
(83)

This implies that

$\displaystyle\begin{split}{\mathbb{E}}[1\mathrm{l}_{\\{\mathfrak{N}\geq
n\\}}|X(U_{n},\theta_{n-1})-X(U_{n},\theta_{n_{\ell-1}})|^{p}|\mathcal{F}_{n-1}]^{1/p}\leq\underbrace{\frac{1-\alpha}{\sqrt{1-\beta}}\frac{1}{\sqrt{1-\alpha^{2}/\beta}}d}_{=\kappa_{3}/\|\varrho\|_{\ell_{1}}}\tilde{L}(t_{n_{\ell}}-t_{n_{\ell-1}}).\end{split}$
(84)

Now note that for $k=n_{\ell-1}+1,\ldots,n_{\ell}$

$\displaystyle\begin{split}\bigl{|}g(\mathbf{X}(k))-g(\tilde{\mathbf{X}}(k))\bigr{|}\leq\sum_{r=n_{\ell-1}+1}^{k}\rho_{r-k}\,|X(U_{r},\theta_{r-1})-X(U_{r},\theta_{n_{\ell-1}})|.\end{split}$
(85)

This implies that for $\mathfrak{n},n\in{\mathbb{N}}_{0}$ with
$n_{\ell-1}\leq\mathfrak{n}\leq n\leq n_{\ell}$

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\Bigl{(}&\sum_{k=\mathfrak{n}+1}^{n}1\mathrm{l}_{\\{\mathfrak{N}>k\\}}\gamma_{k}\bigl{|}g(\mathbf{X}(k))-g(\tilde{\mathbf{X}}(k))\bigr{|}\Bigr{)}^{p}\Bigr{]}^{1/p}\\\
&\leq\sum_{k=\mathfrak{n}+1}^{n}\gamma_{k}\,{\mathbb{E}}\Bigl{[}\Bigl{(}1\mathrm{l}_{\\{\mathfrak{N}>k\\}}\bigl{|}g(\mathbf{X}(k))-g(\tilde{\mathbf{X}}(k))\bigr{|}\Bigr{)}^{p}\Bigr{]}^{1/p}\\\
&\leq\sum_{k=\mathfrak{n}+1}^{n}\gamma_{k}\,{\mathbb{E}}\Bigl{[}\Bigl{(}1\mathrm{l}_{\\{\mathfrak{N}>k\\}}\sum_{r=n_{\ell-1}+1}^{k}\rho_{r-k}\,|X(U_{r},\theta_{r-1})-X(U_{r},\theta_{n_{\ell-1}})|\Bigr{)}^{p}\Bigr{]}^{1/p}\\\
&\leq\sum_{k=\mathfrak{n}+1}^{n}\gamma_{k}\sum_{r=n_{\ell-1}+1}^{k}\varrho_{r-k}\,{\mathbb{E}}\Bigl{[}\Bigl{(}1\mathrm{l}_{\\{\mathfrak{N}>r\\}}|X(U_{r},\theta_{r-1})-X(U_{r},\theta_{n_{\ell-1}})|\Bigr{)}^{p}\Bigr{]}^{1/p}\\\
&\leq\kappa_{3}\tilde{L}(t_{n_{\ell}}-t_{n_{\ell-1}})\sum_{k=\mathfrak{n}+1}^{n}\gamma_{k}.\end{split}$
(86)

3.) Note that

$\displaystyle\begin{split}|\Delta\tilde{\tilde{\Theta}}_{\mathfrak{n},n}-\Delta\tilde{\Theta}_{\mathfrak{n},n}|=|\gamma_{n}\,(g(\mathbf{\tilde{\tilde{X}}}(n))-g(\mathbf{\tilde{X}}(n)))|\leq\gamma_{n}\,\|\mathbf{\tilde{\tilde{X}}}(n)-\mathbf{\tilde{X}}(n)\|_{\ell_{\varrho}^{d}}\end{split}$
(87)

and for $n=n_{\ell-1}+1,\dots,n_{\ell}$,

$\displaystyle\begin{split}\|\mathbf{\tilde{\tilde{X}}}(n)-\mathbf{\tilde{X}}(n)\|_{\ell_{\varrho}^{d}}&=\sum_{k=-\infty}^{n_{\ell-1}}\varrho_{k-n}|X_{k}-X(U_{\ell,k},\theta_{n_{\ell-1}})|\\\
&\leq\sum_{k=-\infty}^{n_{\ell-1}}\varrho_{k-n}|X_{k}|+\sum_{k=-\infty}^{n_{\ell-1}}\varrho_{k-n}|X(U_{\ell,k},\theta_{n_{\ell-1}})|.\end{split}$
(88)

Hence,

$\displaystyle\begin{split}{\mathbb{E}}\bigl{[}1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}\|\mathbf{\tilde{\tilde{X}}}(n)-\mathbf{\tilde{X}}(n)\|^{p}_{\ell_{\varrho}^{d}}\bigr{]}^{1/p}]&\leq\|\mathbf{x}\|_{\ell_{\varrho}^{d}}{\sqrt{\beta}}^{n-n_{0}}+2C\sum_{k=-\infty}^{n_{\ell-1}}\varrho_{k-n}\\\
&\leq\|\mathbf{x}\|_{\ell_{\varrho}^{d}}{\sqrt{\beta}}^{n-n_{0}}+2(1-\sqrt{\beta})^{-1}C\varrho_{n_{\ell-1}-n}\end{split}$
(89)

and

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}&\sum_{n=n_{\ell-1}+1}^{n_{\ell}}|\Delta\tilde{\tilde{\Theta}}_{n}-\Delta\tilde{\Theta}_{n}|^{p}\Bigr{]}^{1/p}\leq\gamma_{n_{\ell-1}+1}\sum_{n=n_{\ell-1}+1}^{n_{\ell}}\bigl{(}\|\mathbf{x}\|_{\ell_{\varrho}^{d}}{\sqrt{\beta}}^{n-n_{0}}+2(1-\sqrt{\beta})^{-1}C\varrho_{n_{\ell-1}-n}\bigr{)}\\\
&\leq\frac{1}{1-\sqrt{\beta}}\gamma_{n_{\ell-1}+1}\bigl{(}{\sqrt{\beta}}^{n_{\ell-1}-n_{0}}\|\mathbf{x}\|_{\ell_{\varrho}^{d}}+2\|\varrho\|_{\ell_{1}}C\bigr{)}.\end{split}$
(90)

4.) The inequalities (IV.a) and (IV.b) are direct consequences of Lemmas 4.1
and 4.2 when conditioning on $\mathcal{F}_{n_{\ell-1}}$. ∎

When choosing in estimate (II), $\mathfrak{n}=n_{\ell-1}$ and $n=n_{\ell}$ we
obtain an estimate covering the same range of indices as the estimate (III).
In order to obtain good results we will choose the sequence
$(n_{\ell})_{\ell\in{\mathbb{N}}_{0}}$ in such a way that both error terms are
of the same order. This motivates the following definition.

######  Definition 5.3.

Let $n_{0}\in{\mathbb{N}}_{0}$ and $\rho\in[\sqrt{\gamma_{n_{0}+1}},\infty)$.
We call the ${\mathbb{N}}_{0}$-valued sequence
$(n_{\ell})_{\ell\in{\mathbb{N}}_{0}}$ a _$\rho$ -partition w.r.t.
$(\gamma_{n})$_ if for every $\ell\in{\mathbb{N}}$, $n_{\ell}$ is the largest
integer with

$\displaystyle\begin{split}t_{n_{\ell}}-t_{n_{\ell-1}}\leq\rho\sqrt{\gamma_{n_{\ell-1}+1}},\end{split}$
(91)

where $(t_{n})$ is as in (5). We call $n_{0}$ the _starting value_.

######  Remark 5.4.

In the definition we assume that $\rho\geq\sqrt{\gamma_{n_{0}+1}}$. This
guarantees that for every $\ell\in{\mathbb{N}}$, one has
$\rho\sqrt{\gamma_{n_{\ell-1}+1}}\geq\gamma_{n_{\ell-1}+1}$ by monotonicity of
$(\gamma_{n})$ so that $n_{\ell}>n_{\ell-1}$. This implies that $(n_{\ell})$
is strictly increasing and that $\lim_{n\to\infty}n_{\ell}=\infty$.

######  Lemma 5.5.

Let $(\gamma_{n})_{n\in{\mathbb{N}}}$ be a $(0,\infty)$-valued decreasing non-
summable sequence and let $(n_{\ell})_{\ell\in{\mathbb{N}}_{0}}$ be a
$\rho$-partition for $(\gamma_{n})$.

  1. (i)

For $\ell\in{\mathbb{N}}$ with $\gamma_{n_{\ell-1}+1}<\rho^{2}$, one has that

$\displaystyle\begin{split}\sqrt{\gamma_{n_{\ell-1}+1}}\leq\frac{1}{\rho-\sqrt{\gamma_{n_{\ell-1}+1}}}(t_{n_{\ell}}-t_{n_{\ell-1}}).\end{split}$
(92)

  2. (ii)

Assume that for all $n=n_{0}+1,n_{0}+2,\dots$

$\displaystyle\begin{split}\frac{\gamma_{n}-\gamma_{n+1}}{\gamma_{n}^{2}}\leq\zeta\end{split}$
(93)

and that $\rho\zeta\sqrt{\gamma_{n_{0}+1}}<1$. Set
$K=(1-\zeta\rho\sqrt{\gamma_{n_{0}+1}})^{-1}$. One has for every
$\ell\in{\mathbb{N}}$ that

$\displaystyle\begin{split}\frac{\gamma_{n_{\ell-1}+1}}{\gamma_{n_{\ell}+1}}\leq
K\text{ \ and \ }\frac{\gamma_{n_{\ell-1}+1}}{\gamma_{n_{\ell}+1}}\leq 1+\zeta
K(t_{n_{\ell}}-t_{n_{\ell-1}}).\end{split}$ (94)

###### Proof.

(i): This is an immediate consequence of

$\displaystyle\begin{split}t_{n_{\ell}}-t_{n_{\ell-1}}\geq\rho\sqrt{\gamma_{n_{\ell-1}+1}}-\gamma_{n_{\ell-1}+1}=(\rho-\sqrt{\gamma_{n_{\ell-1}+1}})\sqrt{\gamma_{n_{\ell-1}+1}}.\end{split}$
(95)

(ii): Denote by $f:[0,\infty)\to(0,\infty)$ the function satisfying

$\displaystyle\begin{split}f(t_{n})=\gamma_{n+1}\end{split}$ (96)

for every $n\in{\mathbb{N}}_{0}$ and that is piecewise linear in between the
points of $\\{t_{0},t_{1},\ldots\\}$. First note that on each interval
$(t_{n-1},t_{n})$

$\displaystyle\begin{split}-f^{\prime}(s)=\frac{\gamma_{n}-\gamma_{n+1}}{\gamma_{n}}\leq\zeta\gamma_{n}\end{split}$
(97)

so that, for $\ell\in{\mathbb{N}}$,

$\displaystyle\begin{split}\gamma_{n_{\ell}+1}\geq\gamma_{n_{\ell-1}+1}-\zeta\gamma_{n_{\ell-1}+1}\rho\sqrt{\gamma_{n_{\ell-1}+1}}\geq(1-\zeta\rho\sqrt{\gamma_{n_{0}+1}})\gamma_{n_{\ell-1}+1}\end{split}$
(98)

and

$\displaystyle\begin{split}\frac{\gamma_{n_{\ell-1}+1}}{\gamma_{n_{\ell}+1}}\leq
K.\end{split}$ (99)

One has

$\displaystyle\begin{split}\gamma_{n_{\ell-1}+1}-\gamma_{n_{\ell}+1}=f(t_{n_{\ell-1}})-f(t_{n_{\ell}})\leq\zeta\gamma_{n_{\ell-1}+1}(t_{n_{\ell}}-t_{n_{\ell-1}})\end{split}$
(100)

and

$\displaystyle\begin{split}\frac{\gamma_{n_{\ell-1}+1}-\gamma_{n_{\ell}+1}}{\gamma_{n_{\ell}+1}}\leq\zeta
K(t_{n_{\ell}}-t_{n_{\ell-1}}).\end{split}$ (101)

∎

We provide another technical estimate.

######  Lemma 5.6.

Let $\|\cdot\|$ be a norm induced by a scalar product
$\llangle\cdot,\cdot\rrangle$ on ${\mathbb{R}}^{d}$ and let $p\geq 2$. One has
for every $x,y\in{\mathbb{R}}^{d}$ that

$\displaystyle\begin{split}\|x+y\|^{p}\leq\|x\|^{p}+p\|x\|^{p-2}\llangle
x,y\rrangle+\mbox{$\frac{1}{2}$}p(p-1)(\|x\|\vee\|x+y\|)^{p-2}\|y\|^{2}.\end{split}$
(102)

###### Proof.

Let $x,y\in{\mathbb{R}}^{d}$. Note that the function $h(z)=\|z\|^{p}$
$(z\in{\mathbb{R}}^{d})$ is twice continuously differentiable with
differentials

$\displaystyle\begin{split}Dh(z)(a)=p\,\|z\|^{p-2}\llangle z,a\rrangle\text{ \
and \ }D^{2}h(z)(a,b)=p(p-2)\|z\|^{p-4}\llangle z,a\rrangle\llangle
z,b\rrangle+p|z|^{p-2}\llangle a,b\rrangle.\end{split}$ (103)

By Taylor’s theorem, we thus have

$\displaystyle\begin{split}|x+y|^{p}=|x|^{p}+p\,|x|^{p-2}\langle
x,y\rangle+\int_{0}^{1}D^{2}h(x+ry)(y,y)(1-r)\,\mathrm{d}r.\end{split}$ (104)

Note that for every $r\in[0,1]$, one has $|x+ry|\leq|x|\vee|x+y|$ and

$\displaystyle\begin{split}\|D^{2}h(x+ry)(y,y)\|&\leq
p(p-2)\|x+ry\|^{p-4}\|\llangle x+ry,y\rrangle\llangle
x+ry,y\rrangle|+p\|x+ry\|^{p-2}\llangle y,y\rrangle\\\ &\leq
p(p-1)(\|x\|\vee\|x+y\|)^{p-2}\|y\|^{2}.\end{split}$ (105)

The statement follows since $\int_{0}^{1}(1-r)\,\mathrm{d}r=\frac{1}{2}$. ∎

##  6 Ordinary differential equation (ODE) based error analyses for the Adam
optimizer

In this section we prove the central estimates for the analysis of the Adam
algorithm. The analysis is done in such a way that the impact of certain
perturbation effects is made completely transparent in the propositions.
Although this precise information is not used when deriving the main theorems,
the results allow to immediately investigate the impact of the tuning
parameters of Adam algorithms such as the damping parameters and the size of
the mini-batch in the case where the innovation is obtained by the simulation
of mini-batches. So it is straight-forward to deduce variants of our main
theorems, where the precise role of certain tuning parameters is revealed.

######  Proposition 6.1 (ODE based non-uniform error analysis for the Adam
optimizer).

Let $d\in{\mathbb{N}}$ and let $\|\cdot\|$ be a norm on ${\mathbb{R}}^{d}$
induced by a scalar product $\llangle\cdot,\cdot\rrangle$ satifying
$\|x\|\leq|x|$ for all $x\in{\mathbb{R}}^{d}$.

  1. (i)

_Innovation._ Let $C,\tilde{C},C^{\prime},L,\tilde{L}\in[0,\infty)$,
$p\in[2,\infty)$ and suppose that $(X,U)$ is a $p$-regular innovation with
parameter $(C,\tilde{C},\tilde{L})$ on the set $V\subset{\mathbb{R}}^{d}$ and
that the Adam vector field $f$ is bounded by $C^{\prime}$ and $L$-Lipschitz on
$V$ with respect to the norm $\|\cdot\|$.

  2. (ii)

_Adam algorithm._ Let $(\theta_{n})_{n\geq n_{0}}$ be an Adam algorithm
started at time $n_{0}\in{\mathbb{N}}_{0}$ in a state
$(\theta_{n_{0}},m_{n_{0}},v_{n_{0}})$ and let
$\mathbf{x}\in\ell_{\varrho}^{d}$ with

$\displaystyle\begin{split}m_{n_{0}}=(1-\alpha)\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}x_{k}\text{
\ and \
}v^{(i)}_{n_{0}}=(1-\beta)\sum_{k\in-{\mathbb{N}}_{0}}\beta^{-k}\bigl{(}x^{(i)}_{k}\bigr{)}^{2}\end{split}$
(106)

for all $i=1,\dots,d$.

  3. (iii)

_ODE._ Let $\Psi:[t_{n_{0}},\infty)\to{\mathbb{R}}^{d}$ be a solution to the
ODE

$\displaystyle\begin{split}\dot{\Psi}_{t}=f(\Psi_{t})\end{split}$ (107)

staying in $V\subset{\mathbb{R}}^{d}$.

  4. (iv)

_Local monotonicity of ODE._ Let $(\mathfrak{R}_{t})_{t\geq t_{n_{0}}}$ a
decreasing $(0,\infty]$-valued mapping and suppose that for a fixed
$c_{1}\in(0,\infty)$ for every $t\in[t_{n_{0}},\infty)$ and $x\in
V\cap\overline{B_{\|\cdot\|}(\Psi_{t},\mathfrak{R}_{t})}$ one has

$\displaystyle\begin{split}\llangle f(x)-f(\Psi_{t}),x-\Psi_{t}\rrangle\leq-
c_{1}\|x-\Psi_{t}\|^{2}.\end{split}$ (108)

  5. (v)

_$\rho$ -partition._ Let $\rho\in[\sqrt{\gamma_{n_{0}+1}},\infty)$ and let
$(n_{\ell})_{\ell\in{\mathbb{N}}_{0}}$ be a $\rho$-partition.

  6. (vi)

_Technical assumptions._ Let $\kappa_{1},\dots,\kappa_{6}$ as in
(LABEL:eq237643) and $c^{\prime},\zeta,\delta_{1},\delta_{2}\in(0,\infty)$. We
suppose validity of the following inequalities:

    1. (a)

$\zeta\rho\sqrt{\gamma_{n_{0}+1}}<1$ and
$\gamma_{n_{0}+1}\leq\delta_{1}<\rho^{2}$

    2. (b)

for every $n=n_{0}+1,n_{0}+2,\dots$, one has
$\frac{\gamma_{n}-\gamma_{n+1}}{\gamma_{n}^{2}}\leq\zeta$

    3. (c)

$2c_{1}-L^{2}\rho\sqrt{\gamma_{n_{0}+1}}-\zeta K\geq 2c^{\prime}$, for
$K:=(1-\zeta\rho\sqrt{\gamma_{n_{0}+1}})^{-1}$

    4. (d)

$\displaystyle{\frac{\rho}{\rho-\sqrt{\delta_{1}}}(\kappa_{3}\rho^{2}\tilde{L}+\mbox{$\frac{1}{2}$}LC^{\prime}\rho^{2}+(\kappa_{2}+\kappa_{4})C+(\kappa_{1}+\kappa_{5})\|\mathbf{x}\|_{\ell_{\varrho}^{d}})\sqrt{\gamma_{n_{0}+1}}\leq\delta_{2}}$.

We consider the stopping time

$\displaystyle\begin{split}\mathfrak{N}=\inf\\{n\geq n_{0}:\theta_{n}\not\in
V\\}\wedge\inf\\{n_{\ell}:\ell\in{\mathbb{N}}_{0},\|\theta_{n_{\ell}}-\Psi_{t_{n_{\ell}}}\|>\mathfrak{R}_{t_{n_{\ell}}}\\}\end{split}$
(109)

Then the sequence $(e_{\ell})_{\ell\in{\mathbb{N}}_{0}}$ given by

$\displaystyle\begin{split}e_{\ell}=\gamma_{n_{\ell}+1}^{-1}\,{\mathbb{E}}[1\mathrm{l}_{\\{\mathfrak{N}\geq
n_{\ell}\\}}\|\theta_{n_{\ell}}-\Psi_{t_{n_{\ell}}}\|^{p}]^{2/p}\end{split}$
(110)

satisfies

$\displaystyle\begin{split}e_{\ell}\leq(1-2c^{\prime}(t_{n_{\ell}}-t_{n_{\ell-1}}))\,e_{\ell-1}+\bigl{(}K(2\sqrt{e_{\ell-1}}+\delta_{2})a_{\ell}+b_{\ell}\bigr{)}(t_{n_{\ell}}-t_{n_{\ell-1}}),\end{split}$
(111)

where

$\displaystyle\begin{split}a_{\ell}=\frac{1}{\rho-\sqrt{\delta_{1}}}\aleph_{\ell}+\mbox{$\frac{1}{2}$}LC^{\prime}\rho,\
\
b_{\ell}=\bigl{(}(p-1)+(\mbox{$\frac{1}{2}$}p(p-1))^{2/p}\bigr{)}\Bigl{(}2K\kappa_{6}^{2}\tilde{C}^{2}+\frac{4K}{\rho-\sqrt{\delta_{1}}}\aleph_{\ell}^{2}\sqrt{\gamma_{n_{\ell-1}+1}}\Bigr{)}\end{split}$
(112)

and

$\displaystyle\begin{split}\aleph_{\ell}=\kappa_{3}\rho^{2}\tilde{L}+(\kappa_{2}+\kappa_{4})C+(\kappa_{1}+\kappa_{5})\beta^{(n_{\ell-1}-n_{0})/2}\|\mathbf{x}\|_{\ell^{d}_{\varrho}}.\end{split}$
(113)

###### Proof.

We use the approximations $(\Theta_{n}),(\tilde{\Theta}_{n})$ and
$(\tilde{\tilde{\Theta}}_{n})$ as introduced in Section 5 and briefly write
for $\mathfrak{n},n\in{\mathbb{N}}_{0}$ with $n_{0}\leq\mathfrak{n}\leq n$,

$\displaystyle\begin{split}\Theta_{\mathfrak{n}:n}=\Theta_{n}-\Theta_{\mathfrak{n}},\
\tilde{\Theta}_{\mathfrak{n}:n}=\tilde{\Theta}_{n}-\tilde{\Theta}_{\mathfrak{n}}\text{
\ and \
}\tilde{\tilde{\Theta}}_{\mathfrak{n}:n}=\tilde{\tilde{\Theta}}_{n}-\tilde{\tilde{\Theta}}_{\mathfrak{n}}.\end{split}$
(114)

We derive a recursive estimate for $e_{\ell}$. For this we let

$\displaystyle\begin{split}A_{\ell}=1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}{\mathbb{E}}\bigl{[}\theta_{n_{\ell}\wedge\mathfrak{N}}-\theta_{n_{\ell-1}}-\tilde{\tilde{\Theta}}_{n_{\ell-1}:(n_{\ell}\wedge\mathfrak{N})}\big{|}\mathcal{F}_{n_{\ell-1}}\bigr{]}\end{split}$
(115)

and

$\displaystyle\begin{split}M_{\ell}=1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}\bigl{(}\tilde{\tilde{\Theta}}_{n_{\ell-1}:n_{\ell}}-f(\theta_{n_{\ell-1}})(t_{n_{\ell}}-t_{n_{\ell-1}})+\theta_{n_{\ell}\wedge\mathfrak{N}}-\theta_{n_{\ell-1}}-\tilde{\tilde{\Theta}}_{n_{\ell-1}:(n_{\ell}\wedge\mathfrak{N})}\bigr{)}-A_{\ell}.\end{split}$
(116)

Note that on the event $\\{\mathfrak{N}\geq n_{\ell}\\}$ one has that

$\displaystyle\begin{split}\theta_{n_{\ell}}=\theta_{n_{\ell-1}}+A_{\ell}+M_{\ell}+f(\theta_{n_{\ell-1}})(t_{n_{\ell}}-t_{n_{\ell-1}}).\end{split}$
(117)

Moreover, write

$\displaystyle\begin{split}\Psi_{t_{n_{\ell}}}=\Psi_{t_{n_{\ell-1}}}+f(\Psi_{t_{n_{\ell-1}}})(t_{n_{\ell}}-t_{n_{\ell-1}})+\tilde{A}_{\ell},\end{split}$
(118)

where
$\tilde{A}_{\ell}=\Psi_{t_{n_{\ell}}}-(\Psi_{t_{n_{\ell-1}}}+f(\Psi_{t_{n_{\ell-1}}})(t_{n_{\ell}}-t_{n_{\ell-1}}))$.
Before we derive appropriate estimates for
$A_{\ell},\tilde{A}_{\ell},M_{\ell}$ we analyse how these estimates enter into
the recursive estimates. Abridge

$\displaystyle\begin{split}\Upsilon_{\ell}=1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}(\theta_{n_{\ell-1}}-\Psi_{t_{n_{\ell-1}}}+(f(\theta_{n_{\ell-1}})-f(\Psi_{t_{n_{\ell-1}}}))(t_{n_{\ell}}-t_{n_{\ell-1}})+A_{\ell}-\tilde{A}_{\ell})\end{split}$
(119)

and note that $\Upsilon_{\ell}$ is $\mathcal{F}_{n_{\ell-1}}$-measurable,
${\mathbb{E}}[M_{\ell}|\mathcal{F}_{n_{\ell-1}}]=0$ and, on
$\\{\mathfrak{N}\geq n_{\ell}\\}$,

$\displaystyle\begin{split}\theta_{n_{\ell}}-\Psi_{t_{n_{\ell}}}=\Upsilon_{\ell}+M_{\ell}.\end{split}$
(120)

Using these properties together with Lemma 5.6 and the Hölder inequality we
get that

$\displaystyle\begin{split}e_{\ell}&=\gamma_{n_{\ell}+1}^{-1}\,{\mathbb{E}}[1\mathrm{l}_{\\{\mathfrak{N}\geq
n_{\ell}\\}}\|\Upsilon_{\ell}+M_{\ell}\|^{p}]^{2/p}\leq\gamma_{n_{\ell}+1}^{-1}\,{\mathbb{E}}[\|\Upsilon_{\ell}+M_{\ell}\|^{p}]^{2/p}\\\
&=\gamma_{n_{\ell}+1}^{-1}\,{\mathbb{E}}\bigl{[}{\mathbb{E}}[\|\Upsilon_{\ell}+M_{\ell}\|^{p}|\mathcal{F}_{n_{\ell-1}}]\bigr{]}^{2/p}\\\
&\leq\gamma_{n_{\ell}+1}^{-1}\,{\mathbb{E}}\bigl{[}\|\Upsilon_{\ell}\|^{p}+\mbox{$\frac{1}{2}$}p(p-1)(\|\Upsilon_{\ell}\|^{p-2}+\|M_{\ell}\|^{p-2})\|M_{\ell}\|^{2}\bigr{]}^{2/p}\\\
&=\gamma_{n_{\ell}+1}^{-1}\,\bigl{(}{\mathbb{E}}[\|\Upsilon_{\ell}\|^{p}]+\mbox{$\frac{1}{2}$}p(p-1)({\mathbb{E}}[\|\Upsilon_{\ell}\|^{p-2}|M_{\ell}|^{2}]+{\mathbb{E}}[\|M_{\ell}\|^{p}])\bigr{)}^{2/p}\\\
&\leq\gamma_{n_{\ell}+1}^{-1}\,\bigl{(}{\mathbb{E}}[\|\Upsilon_{\ell}\|^{p}]+\mbox{$\frac{1}{2}$}p(p-1)({\mathbb{E}}[\|\Upsilon_{\ell}\|^{p}]^{\frac{p-2}{p}}\,{\mathbb{E}}[\|M_{\ell}\|^{p}]^{2/p}+{\mathbb{E}}[\|M_{\ell}\|^{p}])\bigr{)}^{2/p}.\end{split}$
(121)

Using that for all $a,b\geq 0$ and $h(z)=z^{p/2}$ ($z\in[0,\infty)$) one has
$h(a+b)\geq h(a)+h^{\prime}(a)b$ we get that

$\displaystyle\begin{split}\bigl{(}{\mathbb{E}}[\|\Upsilon_{\ell}\|^{p}&]^{2/p}+(p-1){\mathbb{E}}[\|M_{\ell}\|^{p}]^{2/p}\bigr{)}^{p/2}\\\
&\geq{\mathbb{E}}[\|\Upsilon_{\ell}\|^{p}]+\mbox{$\frac{p}{2}$}\bigl{(}{\mathbb{E}}[\|\Upsilon_{\ell}\|^{p}]^{2/p}\bigr{)}^{\frac{p}{2}-1}(p-1){\mathbb{E}}[\|M_{\ell}\|^{p}]^{2/p}.\end{split}$
(122)

Thus we obtain with (121) that

$\displaystyle\begin{split}e_{\ell}&\leq\gamma_{n_{\ell}+1}^{-1}\Bigl{(}\bigl{(}{\mathbb{E}}[\|\Upsilon_{\ell}\|^{p}]^{2/p}+(p-1)\,{\mathbb{E}}[\|M_{\ell}\|^{p}]^{2/p}\bigr{)}^{p/2}+\mbox{$\frac{1}{2}$}p(p-1){\mathbb{E}}[\|M_{\ell}\|^{p}]\Bigr{)}^{2/p}\\\
&\leq\gamma_{n_{\ell}+1}^{-1}\bigl{(}{\mathbb{E}}[\|\Upsilon_{\ell}\|^{p}]^{2/p}+(p-1)\,{\mathbb{E}}[\|M_{\ell}\|^{p}]^{2/p}+(\mbox{$\frac{1}{2}$}p(p-1))^{2/p}\,{\mathbb{E}}[\|M_{\ell}\|^{p}]^{2/p}\bigr{)}\\\
&\leq\gamma_{n_{\ell}+1}^{-1}\bigl{(}{\mathbb{E}}[\|\Upsilon_{\ell}\|^{p}]^{2/p}+\mathfrak{p}\,{\mathbb{E}}[\|M_{\ell}\|^{p}]^{2/p}\bigr{)},\end{split}$
(123)

where $\mathfrak{p}:=p-1+(\mbox{$\frac{1}{2}$}p(p-1))^{2/p}$.

Next, we will provide an estimate for ${\mathbb{E}}[\|M_{\ell}\|^{p}]$. First
note that by Proposition 5.2 (IV.a)

$\displaystyle\begin{split}{\mathbb{E}}\bigl{[}1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}\bigl{\|}\tilde{\tilde{\Theta}}_{n_{\ell-1},n_{\ell}}-f(\theta_{n_{\ell-1}})(t_{n_{\ell}}-t_{n_{\ell-1}})\bigr{\|}^{p}\bigr{]}^{1/p}\leq\kappa_{6}\tilde{C}\sqrt{\gamma_{n_{\ell-1}}(t_{n_{\ell}}-t_{n_{\ell-1}})}\end{split}$
(124)

Moreover, using estimates (I) to (III) and the fact that $(n_{\ell})$ is a
$\rho$-partition we get that

$\displaystyle\begin{split}{\mathbb{E}}[1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}&\|\theta_{n_{\ell}\wedge\mathfrak{N}}-\theta_{n_{\ell-1}}-\tilde{\tilde{\Theta}}_{n_{\ell}-1:(n_{\ell}\wedge\mathfrak{N})}\|^{p}]^{1/p}\\\
&\leq\bigl{(}\kappa_{1}\beta^{\frac{1}{2}(n_{\ell-1}+1)-n_{0}}\|\mathbf{x}\|_{\ell^{d}_{\rho}}+\kappa_{2}C\bigr{)}\gamma_{n_{\ell-1}+1}\beta^{n_{\ell-1}+1}+\kappa_{3}\tilde{L}(t_{n_{\ell}}-t_{n_{\ell-1}})^{2}\\\
&\qquad+\gamma_{n_{\ell-1}+1}\bigl{(}\kappa_{4}C+\kappa_{5}\beta^{(n_{\ell-1}-n_{0})/2}\|\mathbf{x}\|_{\ell_{\varrho}})\\\
&\leq\bigl{(}\underbrace{\kappa_{3}\rho^{2}\tilde{L}+(\kappa_{2}+\kappa_{4})C+(\kappa_{1}+\kappa_{5})\beta^{(n_{\ell-1}-n_{0})/2}\|\mathbf{x}\|_{\ell^{d}_{\varrho}}}_{=\aleph_{\ell}}\bigr{)}\gamma_{n_{\ell-1}+1}.\end{split}$
(125)

By Jensen’s inequality, one has that

$\displaystyle\begin{split}{\mathbb{E}}[\|A_{\ell}\|^{p}]^{1/p}\leq\aleph_{\ell}\gamma_{n_{\ell-1}+1}\end{split}$
(126)

so that we arrive with Lemma 5.5 at

$\displaystyle\begin{split}\gamma_{n_{\ell}+1}^{-1}\,{\mathbb{E}}[\|M_{\ell}\|^{p}]^{2/p}&\leq\bigl{(}{\mathbb{E}}\bigl{[}1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}\bigl{\|}\tilde{\tilde{\Theta}}_{n_{\ell-1},n_{\ell}}-f(\theta_{n_{\ell-1}})(t_{n_{\ell}}-t_{n_{\ell-1}})\bigr{\|}^{p}\bigr{]}^{1/p}+2\,{\mathbb{E}}[\|A_{\ell}\|^{p}]^{1/p}\bigr{)}^{2}\\\
&\leq\gamma_{n_{\ell}+1}^{-1}\bigl{(}\kappa_{6}\tilde{C}\sqrt{\gamma_{n_{\ell-1}+1}(t_{n_{\ell}}-t_{n_{\ell-1}})}+2\aleph_{\ell}\gamma_{n_{\ell-1}+1}\bigr{)}^{2}\\\
&\leq
2K\kappa_{6}^{2}\tilde{C}^{2}(t_{n_{\ell}}-t_{n_{\ell-1}})+4K\aleph_{\ell}^{2}\gamma_{n_{\ell-1}+1}\\\
&\leq\Bigl{(}2K\kappa_{6}^{2}\tilde{C}^{2}+\frac{4K}{\rho-\sqrt{\delta_{1}}}\aleph_{\ell}^{2}\sqrt{\gamma_{n_{\ell-1}+1}}\Bigr{)}(t_{n_{\ell}}-t_{n_{\ell-1}}).\end{split}$
(127)

Together with (123) we obtain that

$\displaystyle\begin{split}e_{\ell}&\leq\gamma_{n_{\ell}+1}^{-1}\bigl{(}{\mathbb{E}}[\|\Upsilon_{\ell}\|^{p}]^{2/p}+\mathfrak{p}\,{\mathbb{E}}[\|M_{\ell}\|^{p}]^{2/p}\bigr{)}\\\
&\leq\gamma_{n_{\ell}+1}^{-1}{\mathbb{E}}[\|\Upsilon_{\ell}\|^{p}]^{2/p}+\mathfrak{p}\Bigl{(}2K\kappa_{6}^{2}\tilde{C}^{2}+\frac{4K}{\rho-\sqrt{\delta_{1}}}\aleph_{\ell}^{2}\sqrt{\gamma_{n_{\ell-1}+1}}\Bigr{)}(t_{n_{\ell}}-t_{n_{\ell-1}}).\end{split}$
(128)

Next, we provide an estimate for ${\mathbb{E}}[\|\Upsilon_{\ell}\|^{p}]$.
Using that $\Psi$ is $L$-Lipschitz and $C^{\prime}$-bounded on $V$ w.r.t.
$\|\cdot\|$ we conclude that

$\displaystyle\begin{split}\|\tilde{A}_{\ell}\|&\leq\int_{t_{n_{\ell-1}}}^{t_{n_{\ell}}}\|f(\Psi_{s})-f(\Psi_{t_{n_{\ell-1}}})\|\,\mathrm{d}s\leq
L\int_{t_{n_{\ell-1}}}^{t_{n_{\ell}}}\int_{t_{n_{\ell-1}}}^{s}\|f(\Psi_{u})\|\,\mathrm{d}u\,\mathrm{d}s\\\
&\leq\mbox{$\frac{1}{2}$}LC^{\prime}(t_{n_{\ell}}-t_{n_{\ell-1}})^{2}.\end{split}$
(129)

Hence, we get with (126) and Lemma 5.5 that

$\displaystyle\begin{split}E[\|A_{\ell}-\tilde{A}_{\ell}\|^{p}]^{1/p}&\leq\aleph_{\ell}\gamma_{n_{\ell-1}+1}+\mbox{$\frac{1}{2}$}LC^{\prime}(t_{n_{\ell}}-t_{n_{\ell-1}})^{2}\\\
&\leq\Bigl{(}\underbrace{\frac{1}{\rho-\sqrt{\delta}}\aleph_{\ell}+\mbox{$\frac{1}{2}$}LC^{\prime}\rho}_{=a_{\ell}}\Bigr{)}\sqrt{\gamma_{n_{\ell-1}+1}}(t_{n_{\ell}}-t_{n_{\ell-1}}).\end{split}$
(130)

As consequence of the monotonicity assumption (4) and the Lipschitz continuity
of $f$, one has on $\\{\mathfrak{N}>n_{\ell-1}\\}$ that

$\displaystyle\begin{split}\|\theta_{n_{\ell-1}}&-\Psi_{t_{n_{\ell-1}}}+(f(\theta_{n_{\ell-1}})-f(\Psi_{t_{n_{\ell-1}}}))(t_{n_{\ell}}-t_{n_{\ell-1}})\|^{2}\\\
&=\|\theta_{n_{\ell-1}}-\Psi_{t_{n_{\ell-1}}}\|^{2}+2(t_{n_{\ell}}-t_{n_{\ell-1}})\llangle\theta_{n_{\ell-1}}-\Psi_{t_{n_{\ell-1}}},f(\theta_{n_{\ell-1}})-f(\Psi_{t_{n_{\ell-1}}})\rrangle\\\
&\qquad\qquad\qquad\qquad\qquad+(t_{n_{\ell}}-t_{n_{\ell-1}})^{2}\|f(\theta_{n_{\ell-1}})-f(\Psi_{t_{n_{\ell-1}}})\|^{2}\\\
&\leq(1-2c_{1}(t_{n_{\ell}}-t_{n_{\ell-1}})+L^{2}(t_{n_{\ell}}-t_{n_{\ell-1}})^{2})\,\|\theta_{n_{\ell-1}}-\Psi_{t_{n_{\ell-1}}}\|^{2}.\end{split}$
(131)

As consequence of assumption (c) we have that
$2c_{1}-L^{2}(t_{n_{\ell}}-t_{n_{\ell-1}})\geq 0$ and we get that

$\displaystyle\begin{split}\|\Upsilon_{\ell}\|^{2}\leq
1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}\bigl{(}&(1-2c_{1}(t_{n_{\ell}}-t_{n_{\ell-1}})+L^{2}(t_{n_{\ell}}-t_{n_{\ell-1}})^{2})\,\|\theta_{n_{\ell-1}}-\Psi_{t_{n_{\ell-1}}}\|^{2}\\\
&+2\|\theta_{n_{\ell-1}}-\Psi_{t_{n_{\ell-1}}}\|\,\|A_{\ell}-\tilde{A}_{\ell}\|+\|A_{\ell}-\tilde{A}_{\ell}\|^{2}\bigr{)}.\end{split}$
(132)

Now note that by assumption (d), we have that
$a_{\ell}(t_{n_{\ell}}-t_{n_{\ell-1}})\leq\delta_{2}$ for all
$\ell\in{\mathbb{N}}$ so that we arrive with (130) and the Cauchy-Schwarz
inequality at

$\displaystyle\begin{split}{\mathbb{E}}[\|\Upsilon_{\ell}\|^{p}]^{2/p}&\leq(1-2c_{1}(t_{n_{\ell}}-t_{n_{\ell-1}})+L^{2}(t_{n_{\ell}}-t_{n_{\ell-1}})^{2})\,{\mathbb{E}}[1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}\|\theta_{n_{\ell-1}}-\Psi_{t_{n_{\ell-1}}}\|^{p}]^{2/p}\\\
&\qquad+2\,{\mathbb{E}}[1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}\|\theta_{n_{\ell-1}}-\Psi_{t_{n_{\ell-1}}}\|^{p}]^{1/p}\,{\mathbb{E}}[\|A_{\ell}-\tilde{A}_{\ell}\|^{p}]^{1/p}+{\mathbb{E}}[\|A_{\ell}-\tilde{A}_{\ell}\|^{p}]^{2/p}\\\
&\leq(1-2c_{1}(t_{n_{\ell}}-t_{n_{\ell-1}})+L^{2}(t_{n_{\ell}}-t_{n_{\ell-1}})^{2})\gamma_{n_{\ell-1}+1}e_{\ell-1}+2\gamma_{n_{\ell-1}+1}\sqrt{e_{\ell-1}}a_{\ell}(t_{n_{\ell}}-t_{n_{\ell-1}})\\\
&\qquad+a_{\ell}^{2}\gamma_{n_{\ell-1}+1}(t_{n_{\ell}}-t_{n_{\ell-1}})^{2}\\\
&\leq(1-2c_{1}(t_{n_{\ell}}-t_{n_{\ell-1}})+L^{2}(t_{n_{\ell}}-t_{n_{\ell-1}})^{2})\gamma_{n_{\ell-1}+1}e_{\ell-1}\\\
&\qquad+\gamma_{n_{\ell-1}+1}(2\sqrt{e_{\ell-1}}+\delta_{2})a_{\ell}(t_{n_{\ell}}-t_{n_{\ell-1}}).\end{split}$
(133)

We apply Lemma 5.5 and use assumption (c) to deduce that

$\displaystyle\begin{split}\gamma_{n_{\ell}+1}^{-1}\,{\mathbb{E}}[\|\Upsilon_{\ell}\|^{p}]^{2/p}&\leq\underbrace{(1+\zeta
K(t_{n_{\ell}}-t_{n_{\ell-1}}))(1-2c_{1}(t_{n_{\ell}}-t_{n_{\ell-1}})+L^{2}(t_{n_{\ell}}-t_{n_{\ell-1}})^{2})}_{\leq
1-2c^{\prime}(t_{n_{\ell}}-t_{n_{\ell-1}})}e_{\ell-1}\\\
&\qquad+K(2\sqrt{e_{\ell-1}}+\delta_{2})a_{\ell}(t_{n_{\ell}}-t_{n_{\ell-1}}).\end{split}$
(134)

We combine this estimate with (128) and get that

$\displaystyle\begin{split}e_{\ell}\leq(1-2c^{\prime}(t_{n_{\ell}}-t_{n_{\ell-1}}))\,e_{\ell-1}&+K(2\sqrt{e_{\ell-1}}+\delta_{2})a_{\ell}(t_{n_{\ell}}-t_{n_{\ell-1}})\\\
&+\mathfrak{p}\Bigl{(}2K\kappa_{6}^{2}\tilde{C}^{2}+\frac{4K}{\rho-\sqrt{\delta_{1}}}\aleph_{\ell}^{2}\sqrt{\gamma_{n_{\ell-1}+1}}\Bigr{)}(t_{n_{\ell}}-t_{n_{\ell-1}}).\end{split}$
(135)

∎

######  Proposition 6.2 (ODE based uniform error analysis for the Adam
optimizer).

Assume item (i), item (ii), item (iii), item (iv), item (v), item (vi)a, item
(vi)b of 6.1, assume that $p>2$ and let again

$\displaystyle\begin{split}\mathfrak{N}=\inf\\{n\geq n_{0}:\theta_{n}\not\in
V\\}\wedge\inf\\{n_{\ell}:\ell\in{\mathbb{N}}_{0},\|\theta_{n_{\ell}}-\Psi_{t_{n_{\ell}}}\|>\mathfrak{R}_{t_{n_{\ell}}}\\}.\end{split}$
(136)

One has

$\displaystyle\begin{split}{\mathbb{E}}\bigl{[}\sup_{n:n_{\ell-1}\leq n\leq
n_{\ell}\wedge\mathfrak{N}}&\|\theta_{n}-\theta_{n_{\ell-1}}-(\Psi_{t_{n}}-\Psi_{t_{n_{\ell-1}}})\|^{p}\bigr{]}^{1/p}\\\
&\leq
L(t_{n_{\ell}}-t_{n_{\ell-1}}){\mathbb{E}}\bigl{[}1\mathrm{l}_{\\{\mathfrak{N}\geq
n_{\ell-1}\\}}\|\theta_{n_{\ell-1}}-\Psi_{t_{n_{\ell-1}}}\|^{p}\bigr{]}^{1/p}\\\
&\qquad+(1-2^{-(\frac{1}{2}-\frac{1}{p})})^{-1}K^{5/4}\kappa_{6}\tilde{C}\gamma_{n_{\ell}+1}^{3/4}+K(\aleph_{\ell}+\mbox{$\frac{1}{2}$}LC^{\prime}\rho^{2})\gamma_{n_{\ell}+1},\end{split}$
(137)

where $K=(1-\zeta\rho\sqrt{\gamma_{n_{0}+1}})^{-1}$ and

$\displaystyle\begin{split}\aleph_{\ell}=\kappa_{3}\rho^{2}\tilde{L}+(\kappa_{2}+\kappa_{4})C+(\kappa_{1}+\kappa_{5})\beta^{(n_{\ell-1}-n_{0})/2}\|\mathbf{x}\|_{\ell^{d}_{\varrho}}.\end{split}$
(138)

###### Proof.

We use the approximations $(\Theta_{n}),(\tilde{\Theta}_{n})$ and
$(\tilde{\tilde{\Theta}}_{n})$ as introduced in Section 5 and write for
$\ell\in{\mathbb{N}}$ and $n\in\\{n_{\ell-1},\dots,n_{\ell}\\}$

$\displaystyle\Psi_{t_{n}}=\Psi_{t_{n_{\ell-1}}}+(t_{n}-t_{n_{\ell-1}})f(\Psi_{t_{n_{\ell-1}}})+\tilde{A}_{\ell,n}$
(139)

and

$\displaystyle\theta_{n}=\theta_{n_{\ell-1}}+\underbrace{\theta_{n}-\theta_{n_{\ell-1}}-\tilde{\tilde{\Theta}}_{n_{\ell-1}:n}}_{=:A_{\ell,n}}+\underbrace{\tilde{\tilde{\Theta}}_{n_{\ell-1}:n_{\ell}}-(t_{n}-t_{n_{\ell-1}})f(\theta_{n_{\ell-1}})}_{=:M_{\ell,n}}+(t_{n}-t_{n_{\ell-1}})f(\theta_{n_{\ell-1}}).$
(140)

In complete analogy to the proof of (125), we get that

$\displaystyle\begin{split}{\mathbb{E}}\bigl{[}\max_{n=n_{\ell-1},\dots,n_{\ell}}1\mathrm{l}_{\\{\mathfrak{N}\geq
n\\}}\|A_{\ell,n}\|^{p}\bigr{]}^{1/p}&\leq{\mathbb{E}}\Bigl{[}\Bigl{(}\sum_{k=n_{\ell-1}+1}^{n_{\ell}}\|\Delta\theta_{k}-\Delta\tilde{\tilde{\Theta}}_{k}\|\Bigr{)}^{p}\Bigr{]}^{1/p}\\\
&\leq\aleph_{\ell}\gamma_{n_{\ell-1}+1}\end{split}$ (141)

with the identical $\aleph_{\ell}$. Moreover, Propositon 5.2 (IV.b) yields
that

$\displaystyle\begin{split}{\mathbb{E}}\bigl{[}1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}\max_{n=n_{\ell-1},\dots,n_{\ell}}\|M_{\ell,n}\|^{p}\bigr{]}^{1/p}\leq(1-2^{-(\frac{1}{2}-\frac{1}{p})})^{-1}\kappa_{6}\tilde{C}\gamma_{n_{\ell-1}+1}\sqrt{n_{\ell}-n_{\ell-1}}.\end{split}$
(142)

With Lemma 5.5 we get that $\gamma_{n_{\ell-1}+1}\leq K\gamma_{n_{\ell}+1}$
and $n_{\ell}-n_{\ell-1}\leq(t_{n_{\ell}}-t_{n_{\ell-1}})/\gamma_{n_{\ell}+1}$
which entails that

$\displaystyle\begin{split}{\mathbb{E}}\bigl{[}1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}\max_{n=n_{\ell-1},\dots,n_{\ell}}\|M_{\ell,n}\|^{p}\bigr{]}^{1/p}\leq(1-2^{-(\frac{1}{2}-\frac{1}{p})})^{-1}K\kappa_{6}\tilde{C}\sqrt{\gamma_{n_{\ell}+1}(t_{n_{\ell}}-t_{n_{\ell}})}.\end{split}$
(143)

Moreover,

$\displaystyle\begin{split}1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}\max_{n=n_{\ell-1},\dots,n_{\ell}}\bigl{|}(t_{n}-t_{n_{\ell-1}})(f(\theta_{n_{\ell-1}})-f(\Psi_{t_{n_{\ell-1}}}))\bigr{|}\leq(t_{n_{\ell}}-t_{n_{\ell-1}})L\|\theta_{n_{\ell-1}}-\Psi_{t_{n_{\ell-1}}}\|\end{split}$
(144)

and
$1\mathrm{l}_{\\{\mathfrak{N}>n_{\ell-1}\\}}\max_{n=n_{\ell-1},\dots,n_{\ell}}\|\tilde{A}_{\ell,n}\|\leq\frac{1}{2}LC^{\prime}(t_{n_{\ell}}-t_{n_{\ell-1}})^{2}$
as in (129). Combining these estimates with the representations (139) and
(140) we get that

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\sup_{n:n_{\ell-1}\leq n\leq
n_{\ell}\wedge\mathfrak{N}}&\|\theta_{n}-\theta_{n_{\ell-1}}-(\Psi_{t_{n}}-\Psi_{t_{n_{\ell-1}}})\|^{p}\Bigr{]}^{1/p}\leq
L(t_{n_{\ell}}-t_{n_{\ell-1}}){\mathbb{E}}\bigl{[}1\mathrm{l}_{\\{\mathfrak{N}\geq
n_{\ell-1}\\}}\|\theta_{n_{\ell-1}}-\Psi_{t_{n_{\ell-1}}}\|^{p}\bigr{]}^{1/p}\\\
&\qquad+\aleph_{\ell}\gamma_{n_{\ell-1}+1}+(1-2^{-(\frac{1}{2}-\frac{1}{p})})^{-1}K\kappa_{6}\tilde{C}\sqrt{\gamma_{n_{\ell}+1}(t_{n_{\ell}}-t_{n_{\ell-1}})}\\\
&\qquad+\mbox{$\frac{1}{2}$}LC^{\prime}(t_{n_{\ell}}-t_{n_{\ell-1}})^{2}\\\
&\leq
L(t_{n_{\ell}}-t_{n_{\ell-1}}){\mathbb{E}}\bigl{[}1\mathrm{l}_{\\{\mathfrak{N}\geq
n_{\ell-1}\\}}\|\theta_{n_{\ell-1}}-\Psi_{t_{n_{\ell-1}}}\|^{p}\bigr{]}^{1/p}\\\
&\qquad+(1-2^{-(\frac{1}{2}-\frac{1}{p})})^{-1}K^{5/4}\kappa_{6}\tilde{C}\gamma_{n_{\ell}+1}^{3/4}+K(\aleph_{\ell}+\mbox{$\frac{1}{2}$}LC^{\prime}\rho^{2})\gamma_{n_{\ell}+1}.\end{split}$
(145)

∎

##  7 Proof of the main result of this article (Theorem 2.5 in Section 2)

In the proof of Theorem 2.5 we proceed as follows. First we verify that Prop.
6.1 is applicable for sufficiently large $\mathfrak{n}$ and appropriate
constants (steps 1.-3.). In the next step, the recursive estimate is used to
deduce an error estimate at the times of a $\rho$-partition, see (166) below.
In step 5. this estimate is extended to all time instances in order to prove
statement one of the theorem. Finally, the estimate of step 4 is used to
deduce the second statement of the theorem.

###### Proof of Theorem 2.5.

We provide a proof under the additional assumption that for every
$x\in{\mathbb{R}}^{d}$ one has $\|x\|\leq|x|$. The general statement then can
be easily obtained by applying the result with norm
$\|\cdot\|^{*}=\iota\,\|\cdot\|$ with $\iota\in(0,\infty)$ sufficiently small
in place of $\|\cdot\|$.

1.) _Choice of parameters for the application of Prop. 6.1._ We denote by
$\kappa_{0}\in(0,\infty)$ the condition number of the canonical embedding of
$({\mathbb{R}}^{d},|\cdot|)$ into $({\mathbb{R}}^{d},\|\cdot\|)$.

We pick $\zeta\in(2c_{2},\infty)$,
$\rho,c^{\prime},\delta,\delta_{1},\delta_{2}\in(0,\infty)$ and
$\mathfrak{n}\in{\mathbb{N}}_{0}$ so that the following inequalities hold:

  1. (i)

$\rho\sqrt{\gamma_{\mathfrak{n}+1}}<\zeta^{-1}\wedge 1$,
$\gamma_{\mathfrak{n}+1}\leq\delta_{1}<\rho^{2}$,

  2. (ii)

$\frac{\gamma_{n}-\gamma_{n+1}}{\gamma_{n}^{2}}\leq\zeta$ for all
$n\geq\mathfrak{n}+1$,

  3. (iii)

$2c_{1}-({\kappa_{0}}{\mathcal{K}}\|\varrho\|_{\ell_{1}})^{2}\rho\sqrt{\gamma_{\mathfrak{n}+1}}-\zeta
K\geq 2c^{\prime}>2c$, for
$K:=(1-\zeta\rho\sqrt{\gamma_{\mathfrak{n}+1}})^{-1}$,

  4. (iv)

$\displaystyle{\mbox{$\frac{\rho}{\rho-\sqrt{\delta_{1}}}$}\bigl{(}(\kappa_{3}\rho^{2}\tilde{L}+\mbox{$\frac{1}{2}$}LC^{\prime}\rho^{2}+(\kappa_{2}+\kappa_{4})C)\sqrt{\gamma_{\mathfrak{n}+1}}+(\kappa_{1}+\kappa_{5})2{\mathcal{K}}\bigr{)}\leq\delta_{2}}$,

  5. (v)

$\mbox{$\frac{1}{2}$}\gamma_{\mathfrak{n}+1}^{-1}\log\beta^{-1}-2c\geq\delta\gamma_{\mathfrak{n}+1}^{-1}$,

  6. (vi)

$e^{c\rho\sqrt{\gamma_{\mathfrak{n}+1}}}\leq 1+\sqrt{\gamma_{\mathfrak{n}+1}}$
and $\sqrt{K}\leq 1+\varepsilon$.

Indeed, this is easily established: pick $\delta_{1},\rho\in(0,\infty)$ with
$\delta_{1}<\rho^{2}$ and $c\rho<1$. Since $2c_{1}-2c_{2}>2c$ we can pick
$\zeta>2c_{2}$ and $c^{\prime}>c$ with

$\displaystyle\begin{split}2c_{1}-\zeta>2c^{\prime}>2c.\end{split}$ (146)

Noting that
$({\kappa_{0}}{\mathcal{K}}\|\varrho\|_{\ell_{1}})^{2}\rho\sqrt{\gamma_{\mathfrak{n}+1}}+\zeta(K-1)$
tends to zero as $\mathfrak{n}$ tends to infinity, we conclude that (c) holds
for all but finitely many $\mathfrak{n}\in{\mathbb{N}}_{0}$. The same is true
for the inequalities in (a) and (b) as consequence of (10) and the fact that
$\zeta>2c_{2}$. We pick
$\delta_{2}=\mbox{$\frac{\rho}{\rho-\sqrt{\delta_{1}}}$}(\kappa_{1}+\kappa_{5})2{\mathcal{K}}+1$
and note that since $\gamma_{\mathfrak{n}+1}$ tends to zero (d) holds for all
but finitely many $\mathfrak{n}$. Pick
$\delta\in(0,\frac{1}{2}\log\beta^{-1})$ and observe that (e) is satisfied for
all but finitely many $\mathfrak{n}$. Analogously, the estimates in (f) hold
for all but finitely many $\mathfrak{n}$ since $(\gamma_{n})$ is a zero
sequence and $K$ converges to one when letting $\mathfrak{n}$ go to infinity.
Thus we have shown that (a), (b), (c), (d), (e) and (f) hold for an
appropriately fixed $\mathfrak{n}\in{\mathbb{N}}_{0}$.

_2\. Regularity of the innovation._ We verify that an innovation $(X,U)$ as in
1. of the theorem is $p$-regular with parameter
$(C,\tilde{C},\tilde{L}):=({\mathcal{K}},2{\mathcal{K}},{\mathcal{K}})$ and,
on $V$, its Adam vector field $f$ is Lipschitz continuous with parameter
$L:={\kappa_{0}}{\mathcal{K}}\|\varrho\|_{\ell_{1}}$ and uniformly bounded by
$C^{\prime}:=d\frac{1-\alpha}{\sqrt{1-\beta}}\frac{1}{\sqrt{1-\alpha^{2}/\beta}}$.
Indeed, by assumption, one has for $\theta,\theta^{\prime}\in V$

$\displaystyle\begin{split}{\mathbb{E}}[|X(U,\theta)|^{2}]^{1/2}&\leq{\mathbb{E}}[|X(U,\theta)|^{p}]^{1/p}\leq{\mathcal{K}}\\\
{\mathbb{E}}[|X(U,\theta)-{\mathbb{E}}[X(U,\theta)]|^{p}]^{1/p}&\leq
2{\mathbb{E}}[|X(U,\theta)|^{p}]^{1/p}\leq 2{\mathcal{K}}\\\
{\mathbb{E}}[|X(U,\theta)-X(U,\theta^{\prime})]|^{p}]^{1/p}&\leq{\mathcal{K}}|\theta-\theta^{\prime}|.\end{split}$
(147)

Moreover, using the Lipschitz continuity of $g$ (Lemma 3.1) we get that

$\displaystyle\begin{split}|f(\theta)-f(\theta^{\prime})|&=|{\mathbb{E}}[g(X(U_{0},\theta),X(U_{-1},\theta),\dots)-g(X(U_{0},\theta^{\prime}),X(U_{-1},\theta^{\prime}),\dots)]|\\\
&\leq{\mathbb{E}}[\|(X(U_{0},\theta)-X(U_{0},\theta^{\prime}),\dots)\|_{\ell^{d}_{\varrho}}]\\\
&=\|\varrho\|_{\ell_{1}}{\mathbb{E}}[|(X(U_{0},\theta)-X(U_{0},\theta^{\prime})|]\leq\|\varrho\|_{\ell_{1}}{\mathcal{K}}\,|\theta-\theta^{\prime}|\end{split}$
(148)

so that by recalling that $\kappa_{0}$ is the condition number of the
canonical embedding of the two Banach spaces we obtain that

$\displaystyle\begin{split}\|f(\theta)-f(\theta^{\prime})\|\leq\kappa_{0}\|\varrho\|_{\ell_{1}}{\mathcal{K}}\,\|\theta-\theta^{\prime}\|\end{split}$
(149)

The uniform bound of $g$ is proved in Lemma 3.1. Hence, property (1) of
Proposition 6.1 is satisfied for $C,\tilde{C},C^{\prime},L,\tilde{L}$ as
above.

_3\. The Adam algorithm in view of Prop. 6.1._ Let
$n_{0}\in{\mathbb{N}}_{0}\cap[\mathfrak{n},\infty)$ and $(\theta_{n})_{n\geq
n_{0}}$ an Adam algorithm as in 2. of the theorem. We pick
$\mathbf{x}\in\ell_{\varrho}^{d}$ satisfying (106) with
$\|\mathbf{x}\|_{\ell_{\varrho}^{d}}\leq
2\|m_{n_{0}},v_{n_{0}}\|_{\ell_{\varrho}^{d}}$ so that, in particular,
$\sqrt{\gamma_{n_{0}+1}}\|\mathbf{x}\|_{\ell_{\varrho}^{d}}\leq
2{\mathcal{K}}$. Note that 2. and 3. of the theorem are identical with (3) and
(4) of Prop. 6.1. We set
$K_{n_{0}}=(1-\zeta\rho\sqrt{\gamma_{n_{0}+1}})^{-1}$. Recalling that
$n_{0}\geq\mathfrak{n}$, $(\gamma_{n})$ is decreasing, $f$ is $L$-Lipschitz
and $K_{n_{0}}\leq K$ we get validity of (6.a)-(6.d) of the proposition (with
$K_{n_{0}}$ in place of $K$).

We are in the position to apply Prop. 6.1. Let
$(n_{\ell})_{\ell\in{\mathbb{N}}_{0}}$ be a $\rho$-partition starting in
$n_{0}$,

$\displaystyle\begin{split}\mathfrak{N}=\inf\\{n\geq n_{0}:\theta_{n}\not\in
V\\}\wedge\inf\\{n_{\ell}:\ell\in{\mathbb{N}}_{0},\|\theta_{n_{\ell}}-\Psi_{t_{n_{\ell}}}\|>\mathfrak{R}_{t_{n_{\ell}}}\\}\end{split}$
(150)

and, for $\ell\in{\mathbb{N}}_{0}$,

$\displaystyle\begin{split}e_{\ell}=\gamma_{n_{\ell}+1}^{-1}\,{\mathbb{E}}[1\mathrm{l}_{\\{\mathfrak{N}\geq
n_{\ell}\\}}\|\theta_{n}-\Psi_{t_{n}}\|^{p}]^{2/p}.\end{split}$ (151)

Then the proposition implies that one has, for all $\ell\in{\mathbb{N}}$,

$\displaystyle\begin{split}e_{\ell}\leq(1-2c^{\prime}(t_{n_{\ell}}-t_{n_{\ell-1}}))\,e_{\ell-1}+\bigl{(}K(2\sqrt{e_{\ell-1}}+\delta_{2})a_{\ell}+b_{\ell}\bigr{)}(t_{n_{\ell}}-t_{n_{\ell-1}}),\end{split}$
(152)

where $(a_{\ell})$, $(b_{\ell})$ and $(\aleph_{\ell})$ are as in (112) and
(113).

_4\. Analysis of the recursive estimate ( 152)._ In the following, we denote
by $\eta_{1},\dots$ constants that may depend on $d$, $\alpha$, $\beta$, $p$,
$(\gamma_{n})$, ${\mathcal{K}}$, $c$, $c_{1}$, $c_{2}$ and the choices that we
made for $\mathfrak{n}$, $c^{\prime}$, $\rho$, $\delta$,$\delta_{1}$ and
$\delta_{2}$ in part one, but not on further specific details of the
underlying algorithm or the ODE. By definition of $(a_{\ell})$ and
$(b_{\ell})$ and the bound $\|\mathbf{x}\|_{\ell_{\varrho}^{d}}\leq
2{\mathcal{K}}\gamma_{n_{0}+1}^{-1/2}$ there exists a finite constant
$\eta_{1}$ such that, for every $\ell\in{\mathbb{N}}$,

$\displaystyle\begin{split}|a_{\ell}|\vee|b_{\ell}|\leq\eta_{1}(1+\beta^{(n_{\ell-1}-n_{0})/2}\|\mathbf{x}\|_{\ell_{\varrho}^{d}}).\end{split}$
(153)

Together with (152) we thus get that for an appropriate constant $\eta_{2}$
one has

$\displaystyle\begin{split}e_{\ell}\leq(1-2c^{\prime}(t_{n_{\ell}}-t_{n_{\ell-1}}))\,e_{\ell-1}&+\eta_{2}(\sqrt{e_{\ell-1}}+1)(1+\beta^{(n_{\ell-1}-n_{0})/2}\|\mathbf{x}\|_{\ell^{d}_{\varrho}})(t_{n_{\ell}}-t_{n_{\ell-1}}).\end{split}$
(154)

Clearly,
$\eta_{3}:=\sup_{z\in[0,\infty)}(\eta_{2}(\sqrt{z}+1)-(2c^{\prime}-2c)z)$ is
finite and using that
$\eta_{2}(\sqrt{e_{\ell-1}}+1)\leq(2c^{\prime}-2c)e_{\ell-1}+\eta_{3}$ we get
that

$\displaystyle\begin{split}e_{\ell}\leq(1-2c(t_{n_{\ell}}-t_{n_{\ell-1}}))\,e_{\ell-1}+\eta_{3}(t_{n_{\ell}}-t_{n_{\ell-1}})+\eta_{2}(\sqrt{e_{\ell-1}}+1)\beta^{(n_{\ell-1}-n_{0})/2}\|\mathbf{x}\|_{\ell^{d}_{\varrho}}(t_{n_{\ell}}-t_{n_{\ell-1}})\end{split}$
(155)

and

$\displaystyle\begin{split}e_{\ell}-\mbox{$\frac{\eta_{3}}{2c}$}\leq(1-2c(t_{n_{\ell}}-t_{n_{\ell-1}}))\,(e_{\ell-1}-\mbox{$\frac{\eta_{3}}{2c}$})+\eta_{2}(\sqrt{e_{\ell-1}}+1)\beta^{(n_{\ell-1}-n_{0})/2}\|\mathbf{x}\|_{\ell^{d}_{\varrho}}(t_{n_{\ell}}-t_{n_{\ell-1}}).\end{split}$
(156)

This gives

$\displaystyle\begin{split}e_{\ell}-\mbox{$\frac{\eta_{3}}{2c}$}&\leq(e_{0}-\mbox{$\frac{\eta_{3}}{2c}$})_{+}e^{-2c(t_{n_{\ell}}-t_{n_{0}})}\\\
&\qquad+\sum_{r=1}^{\ell}e^{-2c(t_{n_{\ell}}-t_{n_{r}})}(\sqrt{e_{r-1}}+1)\beta^{(n_{r-1}-n_{0})/2}\|\mathbf{x}\|_{\ell^{d}_{\varrho}}(t_{n_{r}}-t_{n_{r-1}})\end{split}$
(157)

It remains to provide an estimate for the latter sum. First note that

$\displaystyle\begin{split}n_{r-1}-n_{0}\geq\frac{t_{n_{r-1}}-t_{n_{0}}}{\gamma_{n_{0}+1}}\end{split}$
(158)

and as consequence of (e) above we get that

$\displaystyle\begin{split}\frac{1}{2\gamma_{n_{0}+1}}\log\beta^{-1}-2c\geq\delta\gamma_{n_{0}+1}^{-1}>0.\end{split}$
(159)

Consequently, we have

$\displaystyle\begin{split}\sum_{r=1}^{\ell}&e^{-2c(t_{n_{\ell}}-t_{n_{r}})}\beta^{(n_{r-1}-n_{0})/2}(t_{n_{r}}-t_{n_{r-1}})\\\
&\leq
e^{2c\rho\sqrt{\gamma_{n_{0}+1}}}\sum_{r=1}^{\ell}\underbrace{e^{-2c(t_{n_{\ell}}-t_{n_{r-1}})-\frac{1}{2}\log\beta^{-1}(n_{r-1}-n_{0})}}_{\leq
e^{-2c(t_{n_{\ell}}-t_{n_{0}})}e^{-\delta\gamma_{n_{0}-1}^{-1}(t_{n_{r-1}}-t_{n_{0}})}}(t_{n_{r}}-t_{n_{r-1}})\\\
&\leq
e^{-2c(t_{n_{\ell}}-t_{n_{0}}-\rho\sqrt{\gamma_{n_{0}+1}})}\sum_{r=1}^{\ell}e^{-\delta\gamma_{n_{0}+1}^{-1}(t_{n_{r-1}}-t_{n_{0}})}(t_{n_{r}}-t_{n_{r-1}})\\\
&\leq
e^{-2c(t_{n_{\ell}}-t_{n_{0}}-\rho\sqrt{\gamma_{n_{0}+1}})}\Bigl{(}\rho\sqrt{\gamma_{n_{0}+1}}+\int_{0}^{\infty}e^{-\delta\gamma_{n_{0}+1}^{-1}s}\,\mathrm{d}s\Bigr{)}\\\
&\leq\eta_{4}\sqrt{\gamma_{n_{0}+1}}e^{-2c(t_{n_{\ell}}-t_{n_{0}})}\end{split}$
(160)

for the constant
$\eta_{4}=e^{2c\rho\sqrt{\gamma_{\mathfrak{n}+1}}}\bigl{(}\rho+\delta^{-1}\sqrt{\gamma_{\mathfrak{n}+1}}\bigr{)}.$
Together with (157) we get an a priori bound for
$\mathcal{M}_{L}:=\sup_{\ell=0,\dots,L}e_{\ell}$ ($L\in{\mathbb{N}}_{0}$): one
has for every $\ell=0,\dots,L$ that

$\displaystyle\begin{split}e_{\ell}-\mbox{$\frac{\eta_{3}}{2c}$}\leq(e_{0}-\mbox{$\frac{\eta_{3}}{2c}$})_{+}+(\sqrt{\mathcal{M}_{L}}+1)\|\mathbf{x}\|_{\rho_{\ell}^{d}}\underbrace{\sum_{r=1}^{\ell}e^{-2c(t_{n_{\ell}}-t_{n_{r}})}\beta^{(n_{r-1}-n_{0})/2}(t_{n_{r}}-t_{n_{r-1}})}_{\leq\eta_{4}\sqrt{\gamma_{n_{0}+1}}}\end{split}$
(161)

so that

$\displaystyle\begin{split}\mathcal{M}_{L}-\underbrace{\eta_{4}\sqrt{\gamma_{n_{0}+1}}\|\mathbf{x}\|_{\ell_{\varrho}^{d}}}_{=:a}(\sqrt{\mathcal{M}_{L}}+1)-\bigl{(}\underbrace{e_{0}\vee\mbox{$\frac{\eta_{3}}{2c}$}}_{=:b}\bigr{)}\leq
0.\end{split}$ (162)

Hence, $\sqrt{\mathcal{M}_{L}}$ is smaller or equal to the right zero of the
parabola $z\mapsto z^{2}-a(z+1)-b$. This gives that

$\displaystyle\begin{split}\mathcal{M}_{L}\leq\Bigl{(}\frac{a}{2}+\sqrt{\frac{a^{2}}{4}+a+b}\Bigr{)}^{2}\leq\Bigl{(}\frac{a}{2}+\sqrt{(\mbox{$\frac{1}{2}$}a+1)^{2}+b}\Bigr{)}^{2}\leq(a+1+\sqrt{b})^{2}.\end{split}$
(163)

By assuming that $\mathfrak{n}$ is sufficiently large (otherwise we may
enlarge it appropriately) we can guarantee that
$\eta_{3}/(2c)\leq{\mathcal{K}}^{2}\gamma_{\mathfrak{n}+1}^{-1}$.
Additionally, by assumption (13),
$e_{0}\leq{\mathcal{K}}^{2}\gamma_{n_{0}+1}^{-1}$ so that
$\sqrt{b}\leq{\mathcal{K}}\gamma_{n_{0}+1}^{-1/2}$. Together with
$a\leq\eta_{4}{\mathcal{K}}$ we get that
$\sqrt{\mathcal{M}_{L}}+1\leq\mathcal{K}\gamma_{n_{0}+1}^{-1/2}+\eta_{4}{\mathcal{K}}+2.$
Assuming that $\mathfrak{n}$ is sufficiently large that
$\eta_{4}{\mathcal{K}}+2\leq{\mathcal{K}}\gamma_{\mathfrak{n}+1}^{-1/2}$ we
obtain that

$\displaystyle\begin{split}\sqrt{\mathcal{M}_{L}}+1\leq
2\mathcal{K}\gamma_{n_{0}+1}^{-1/2}.\end{split}$ (164)

Note that the latter estimate does not depend on the choice of $L$ so that it
remains valid when replacing $\mathcal{M}_{L}$ by
$\mathcal{M}=\sup_{\ell\in{\mathbb{N}}_{0}}e_{\ell}$.

Insertion of this a priori bound into (157) and using again (160) gives that

$\displaystyle\begin{split}e_{\ell}-\mbox{$\frac{\eta_{3}}{2c}$}&\leq(e_{0}-\mbox{$\frac{\eta_{3}}{2c}$})_{+}e^{-2c(t_{n_{\ell}}-t_{n_{0}})}\\\
&\qquad+2{\mathcal{K}}\gamma_{n_{0}+1}^{-1/2}\|\mathbf{x}\|_{\ell^{d}_{\varrho}}\sum_{r=1}^{\ell}e^{-2c(t_{n_{\ell}}-t_{n_{r}})}\beta^{(n_{r-1}-n_{0})/2}(t_{n_{r}}-t_{n_{r-1}})\\\
&\leq(e_{0}-\mbox{$\frac{\eta_{3}}{2c}$})_{+}e^{-2c(t_{n_{\ell}}-t_{n_{0}})}+2{\mathcal{K}}\eta_{4}\|\mathbf{x}\|_{\ell^{d}_{\varrho}}e^{-2c(t_{n_{\ell}}-t_{n_{0}})}.\end{split}$
(165)

Consequently,

$\displaystyle\begin{split}{\mathbb{E}}[&1\mathrm{l}_{\\{\mathfrak{N}\geq
n_{\ell}\\}}\|\theta_{n_{\ell}}-\Psi_{t_{n_{\ell}}}\|^{p}]^{1/p}=\sqrt{\gamma_{n_{\ell}+1}e_{\ell}}\\\
&\leq\Bigl{(}\sqrt{\mbox{$\frac{\eta_{3}}{2c}$}}+e^{-c(t_{n_{\ell}}-t_{n_{0}})}\Bigl{(}\frac{1}{\sqrt{\gamma_{n_{0}+1}}}{\mathbb{E}}[1\mathrm{l}_{\\{\mathfrak{N}>n_{0}\\}}\|\theta_{n_{0}}-\Psi_{t_{n_{0}}}\|^{p}]^{1/p}+\sqrt{2{\mathcal{K}}\eta_{4}}\sqrt{\|\mathbf{x}\|_{\ell_{\varrho}^{d}}}\Bigr{)}\Bigr{)}\sqrt{\gamma_{n_{\ell}+1}}\\\
&=:\bar{e}_{\ell}\end{split}$ (166)

_5\. Proof of the first statement._ To extend this estimate on the set of all
time instances first observe that as consequence of property (f) one has

$\displaystyle\begin{split}e^{-c(t_{n_{\ell-1}}-t_{n_{0}})}\leq
e^{-c(t_{n_{\ell}}-t_{n_{0}})}e^{c\rho\sqrt{\gamma_{n_{\ell-1}+1}}}\leq
e^{-c(t_{n_{\ell}}-t_{n_{0}})}(1+\sqrt{\gamma_{n_{0}+1}})\end{split}$ (167)

and

$\displaystyle\begin{split}\sqrt{\gamma_{n_{\ell-1}+1}}\leq\sqrt{K}\sqrt{\gamma_{n_{\ell}+1}}\leq(1+\varepsilon)\sqrt{\gamma_{n_{\ell}+1}}.\end{split}$
(168)

This entails that

$\displaystyle\begin{split}\bar{e}_{\ell-1}&\leq(1+\varepsilon)\Bigl{(}\sqrt{\mbox{$\frac{\eta_{3}}{2c}$}}+e^{-c(t_{n_{\ell}}-t_{n_{0}})}(1+\sqrt{\gamma_{n_{0}+1}})\Bigl{(}\frac{1}{\sqrt{\gamma_{n_{0}+1}}}{\mathbb{E}}[1\mathrm{l}_{\\{\mathfrak{N}>n_{0}\\}}\|\theta_{n_{0}}-\Psi_{t_{n_{0}}}\|^{p}]^{1/p}\\\
&\quad+\sqrt{2{\mathcal{K}}\eta_{4}}\sqrt{\|\mathbf{x}\|_{\ell_{\varrho}^{d}}}\Bigr{)}\Bigr{)}\sqrt{\gamma_{n_{\ell}+1}}\\\
&\leq(1+\varepsilon)\bar{e}_{\ell}+\eta_{5}\sqrt{\gamma_{n_{\ell}+1}},\end{split}$
(169)

where $\eta_{5}$ is an appropriate constant. By Proposition 6.2, there is a
constant $\eta_{6}$ such that

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\sup_{n:n_{\ell-1}\leq n\leq
n_{\ell}\wedge\mathfrak{N}}\|\theta_{n}-\theta_{n_{\ell-1}}-(\Psi_{t_{n}}-\Psi_{t_{n_{\ell-1}}})\|^{p}\Bigr{]}^{1/p}&\leq\eta_{6}\sqrt{\gamma_{n_{\ell}+1}}(\bar{e}_{\ell-1}+1)\\\
&\leq\eta_{6}\sqrt{\gamma_{n_{\ell}+1}}((1+\varepsilon)\bar{e}_{\ell}+\eta_{5}\sqrt{\gamma_{n_{\ell}+1}}+1)\end{split}$
(170)

Assuming that $\mathfrak{n}$ is sufficiently large to guarantee that
$\eta_{6}\sqrt{\gamma_{\mathfrak{n}+1}}\leq\varepsilon$ and
$\eta_{5}\sqrt{\gamma_{\mathfrak{n}+1}}\leq 1$ we get that

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\sup_{n:n_{\ell-1}\leq n\leq
n_{\ell}\wedge\mathfrak{N}}\|\theta_{n}-\theta_{n_{\ell-1}}-(\Psi_{t_{n}}-\Psi_{t_{n_{\ell-1}}})\|^{p}\Bigr{]}^{1/p}&\leq\varepsilon(1+\varepsilon)\bar{e}_{\ell}+2\eta_{6}\sqrt{\gamma_{n_{\ell}+1}}.\end{split}$
(171)

Combining this estimate with the triangle inequality and (169) we conclude
that

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\sup_{n_{\ell-1}\leq n\leq
n_{\ell}\wedge\mathfrak{N}}&\|\theta_{n}-\Psi_{t_{n}}\|^{p}\Bigr{]}^{1/p}\leq{\mathbb{E}}[1\mathrm{l}_{\\{\mathfrak{N}\geq
n_{\ell}\\}}\|\theta_{n_{\ell-1}}-\Psi_{t_{n_{\ell-1}}}\|^{p}]^{1/p}\\\
&\qquad\qquad\qquad\qquad+{\mathbb{E}}\bigl{[}\sup_{n:n_{\ell-1}\leq n\leq
n_{\ell}\wedge\mathfrak{N}}\|\theta_{n}-\theta_{n_{\ell-1}}-(\Psi_{t_{n}}-\Psi_{t_{n_{\ell-1}}})\|^{p}\bigr{]}^{1/p}\\\
&\leq(1+\varepsilon)^{2}\bar{e}_{\ell}+(\eta_{5}+2\eta_{6})\sqrt{\gamma_{n_{\ell}+1}}\\\
&\leq\Bigl{(}\eta_{7}+e^{-c(t_{n_{\ell}}-t_{n_{0}})}\Bigl{(}(1+\varepsilon)^{2}\frac{|\theta_{n_{0}}-\Psi_{t_{n_{0}}}|}{\sqrt{\gamma_{n_{0}+1}}}+\eta_{7}\sqrt{(m_{0},v_{0})_{\ell_{\varrho}^{d}}}\Bigr{)}\Bigr{)}\sqrt{\gamma_{n_{\ell}+1}},\end{split}$
(172)

where $\eta_{7}$ is an appropriate constant. This proves the first statement
by noticing that, in particular, for $n\geq n_{0}$ one can choose
$\ell\in{\mathbb{N}}$ with $n\in\\{n_{\ell-1},\dots,n_{\ell}\\}$ and get that

$\displaystyle\begin{split}{\mathbb{E}}\bigl{[}1\mathrm{l}_{\\{\mathfrak{N}\geq
n\\}}&\|\theta_{n}-\Psi_{t_{n}}\|^{p}\bigr{]}^{1/p}\leq(1+\varepsilon)^{2}\bar{e}_{\ell}+(\eta_{5}+2\eta_{6})\sqrt{\gamma_{n_{\ell}+1}}\\\
&\leq\Bigl{(}\eta_{7}+e^{-c(t_{n_{\ell}}-t_{n_{0}})}\Bigl{(}(1+\varepsilon)^{2}\frac{\|\theta_{n_{0}}-\Psi_{t_{n_{0}}}\|}{\sqrt{\gamma_{n_{0}+1}}}+\eta_{7}\sqrt{(m_{0},v_{0})_{\ell_{\varrho}^{d}}}\Bigr{)}\Bigr{)}\sqrt{\gamma_{n+1}}.\end{split}$
(173)

_6\. Proof of the second statement._ For ease of notation, we write in this
part

$\displaystyle\begin{split}a:=\eta_{7}\text{ \ and \
}b:=(1+\varepsilon)^{2}\frac{\|\theta_{n_{0}}-\Psi_{t_{n_{0}}}\|}{\sqrt{\gamma_{n_{0}+1}}}+\eta_{7}(m_{n_{0}},v_{n_{0}})_{\ell_{\varrho}^{d}}.\end{split}$
(174)

By assumption, $(R_{t})_{t\geq t_{n_{0}}}$ is decreasing which implies that

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}&\sum_{\ell=1}^{\infty}R_{t_{n_{\ell-1}}}^{-p}\sup_{n_{\ell-1}\leq
n\leq n_{\ell}\wedge\mathfrak{N}}\|\theta_{n}-\Psi_{t_{n}}\|^{p}\Bigr{]}\\\
&\leq\sum_{\ell=1}^{\infty}R_{t_{n_{\ell-1}}}^{-p}\bigl{(}a+be^{-c(t_{n_{\ell}}-t_{n_{0}})})^{p}\,\gamma_{n_{\ell}+1}^{p/2}\\\
&\leq(\rho-\sqrt{\gamma_{\mathfrak{n}+1}})^{-1}\sum_{\ell=1}^{\infty}R_{t_{n_{\ell-1}}}^{-p}\bigl{(}a+be^{-c(t_{n_{\ell}}-t_{n_{0}})})^{p}\gamma_{n_{\ell}+1}^{(p-1)/2}(t_{n_{\ell}}-t_{n_{\ell-1}})\\\
&\leq(\rho-\sqrt{\gamma_{\mathfrak{n}+1}})^{-1}\int_{t_{n_{0}}}^{\infty}R_{s}^{-p}\bigl{(}a+be^{-c(s-t_{n_{0}})})^{p}\,\Gamma_{s}^{(p-1)/2}\,\mathrm{d}s.\end{split}$
(175)

By (a), we have that $t_{n_{\ell}}-t_{n_{\ell-1}}\leq 1$ so that

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\sup_{n=n_{0},\dots,\mathfrak{N}}R_{t_{n}}^{-p}\|\theta_{n}-\Psi_{t_{n}}\|^{p}\Bigr{]}&\leq{\mathcal{K}}^{p}\,{\mathbb{E}}\Bigl{[}\sum_{\ell=1}^{\infty}R_{t_{n_{\ell-1}}}^{-p}\sup_{n_{\ell-1}\leq
n\leq n_{\ell}\wedge\mathfrak{N}}\|\theta_{n}-\Psi_{t_{n}}\|^{p}\Bigr{]}\\\
&\leq{\mathcal{K}}^{p}\,(\rho-\sqrt{\gamma_{\mathfrak{n}+1}})^{-1}\int_{t_{n_{0}}}^{\infty}R_{s}^{-p}\bigl{(}a+be^{-c(s-t_{n_{0}})})^{p}\,\Gamma_{s}^{(p-1)/2}\,\mathrm{d}s\end{split}$
(176)

which implies the second statement of the theorem. ∎

##  8 Regularity properties and perturbation analysis for the Adam vector
field

The Adam vector field as introduced in 2.4 depends in an intricate way on the
innovation $(X,U)$ and the damping parameters $(\alpha,\beta,\epsilon)$. In
this section, we want to investigate the dominant terms for particular choices
of parameters.

In the following, let $(X,U)$ be an innovation and let
$(\alpha,\beta,\epsilon)$ be damping parameters with
$0\leq\alpha<\sqrt{\beta}<1$. The related Adam vector field
$f\colon{\mathbb{R}}^{d}\to{\mathbb{R}}^{d}$ is given by

$\displaystyle\begin{split}f^{(i)}(\theta)&=(1-\alpha)\,{\mathbb{E}}\Bigl{[}1/\Bigl{(}\sqrt{(1-\beta)\sum_{k\in-{\mathbb{N}}_{0}}\beta^{-k}X^{(i)}(U_{k},\theta)^{2}}+\epsilon\Bigr{)}\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}X^{(i)}(U_{k},\theta)\Bigr{]}.\end{split}$
(177)

Motivated by a Taylor approximation we will introduce a vector field
$\tilde{f}=(\tilde{f}^{(1)},\dots,\tilde{f}^{(d)})\colon\allowbreak{\mathbb{R}}^{d}\to{\mathbb{R}}^{d}$
which we call the _first order approximation_ for the Adam field $f$. For this
we need some more notation.

We denote by $(U_{k})_{k\in-{\mathbb{N}}_{0}}$ an i.i.d. sequence of copies of
$U$ and briefly write, for all $k\in-{\mathbb{N}}_{0}$ and
$\theta\in{\mathbb{R}}^{d}$, $X_{k}^{\theta}=X(U_{k},\theta)$ and
$\mathbf{X}^{\theta}=(X_{k}^{\theta})_{k\in-{\mathbb{N}}_{0}}$. Again we write
for $\mathbf{x}=(x_{k})_{k\in-{\mathbb{N}}_{0}}\in\ell_{\varrho}$

$\displaystyle\begin{split}V(\mathbf{x})=(1-\beta)\sum_{k\in-{\mathbb{N}}_{0}}\beta^{-k}x_{k}^{2}\end{split}$
(178)

and let

$\displaystyle\begin{split}h:[0,\infty)\to(0,\epsilon^{-1}],\
x\mapsto\frac{1}{\sqrt{x}+\epsilon}.\end{split}$ (179)

In this notation, we have

$\displaystyle\begin{split}f^{(i)}(\theta)&=(1-\alpha)\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}\,{\mathbb{E}}\bigl{[}h(V(\mathbf{X}^{\theta,(i)}))\,X^{\theta,(i)}_{k}\bigr{]}.\end{split}$
(180)

For $k\in-{\mathbb{N}}_{0}$ and
$\mathbf{x}=(x_{r})_{r\in-{\mathbb{N}}_{0}}\in\ell_{\varrho}$, we let

$\displaystyle\begin{split}V^{\not=k}(\mathbf{x})=(1-\beta)\sum_{r\in-{\mathbb{N}}_{0}\backslash\\{k\\}}\beta^{-r}x_{r}^{2},\text{
\ for all $i=1,\dots,d$,}\end{split}$ (181)

and we set, for all $\theta\in{\mathbb{R}}^{d}$ and $i=1,\dots,d$,

$\displaystyle\begin{split}&\tilde{f}^{(i)}(\theta)=(1-\alpha)\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}\,{\mathbb{E}}\Bigl{[}\frac{1}{\sqrt{V^{\not=k}(\mathbf{X}^{\theta,(i)})}+\epsilon}\Bigr{]}\,{\mathbb{E}}[X^{\theta,(i)}_{0}]\\\
&-(1-\alpha)(1-\beta)\sum_{k\in-{\mathbb{N}}_{0}}(\alpha\beta)^{-k}\,{\mathbb{E}}\Bigl{[}\frac{1}{(\sqrt{V^{\not=k}(\mathbf{X}^{\theta,(i)})}+\epsilon)^{2}}\frac{1}{2\sqrt{V^{\not=k}(\mathbf{X}^{\theta,(i)})}}\Bigr{]}{\mathbb{E}}\bigl{[}(X^{\theta,(i)}_{0})^{3}\bigr{]}\end{split}$
(182)

provided that the latter two expectations are well-defined and finite. Note
that for every $k\in-{\mathbb{N}}_{0}$, the random variable
$V^{\not=k}(\mathbf{X}^{\theta,(i)})$ stochastically dominates
$V^{\not=0}(\mathbf{X}^{\theta,(i)})$. Moreover, the distribution of
$V^{\not=0}(\mathbf{X}^{\theta,(i)})$ agrees with the one of $\beta
V(\mathbf{X}^{\theta,(i)})$. Consequently, $\tilde{f}^{(i)}(\theta)$ is well-
defined and finite, if and only if

$\displaystyle\begin{split}X_{0}^{\theta,(i)}\in L^{3}\text{ \ and \
}V(\mathbf{X}^{\theta,(i)})^{-1/2}\in L^{1}.\end{split}$ (183)

We call $\tilde{f}^{(i)}(\theta)$ as in (LABEL:def:linApp) _first order
approximation_ for the Adam vector field with innovation $(X,U)$ and damping
parameters $(\alpha,\beta,\epsilon)$ provided that it exists.

######  Theorem 8.1.

Let $(X,U)$ be an innovation and $(\alpha,\beta,\epsilon)$ damping parameters
with $0\leq\alpha<\sqrt{\beta}<1$. Let $\theta\in{\mathbb{R}}^{d}$ and
$i=1,\dots,d$ and suppose that

$\displaystyle\begin{split}X_{0}^{\theta,(i)}\in L^{5}\text{ \ and \
}V(\mathbf{X}^{\theta,(i)})^{-1/2}\in L^{3}.\end{split}$ (184)

Then the first order approximation $\tilde{f}^{(i)}(\theta)$ for the Adam
field with innovation $(X,U)$ and damping factors $(\alpha,\beta,\epsilon)$ is
well-defined in $\theta$ and $i$ and one has that

$\displaystyle\begin{split}|f^{(i)}(\theta)-\tilde{f}^{(i)}(\theta)|&\leq\frac{3}{8}\frac{(1-\alpha)(1-\beta)^{2}}{\beta^{5/2}(1-\alpha\beta^{2})}\,{\mathbb{E}}\Bigl{[}\frac{1}{(\sqrt{V(\mathbf{X}^{\theta,(i)})}+\epsilon)^{2}\,V(\mathbf{X}^{\theta,(i)})^{3/2}}\Bigr{]}\,{\mathbb{E}}^{\theta}[|X^{\theta,(i)}_{0}|^{5}\bigr{]}.\end{split}$
(185)

######  Remark 8.2.

Supposing that 184 is satisfied for given $\theta\in{\mathbb{R}}^{d}$ and
$i\in\\{1,\dots,d\\}$ we can indeed use the previous theorem to show that
$\tilde{f}^{(i)}(\theta)$ approximates $f^{(i)}(\theta)$ well, when fixing
$\alpha$ and $\epsilon$ and letting $\beta\to 1$. In this setting,
$|f^{(i)}(\theta)-\tilde{f}^{(i)}(\theta)|$ is of order $(1-\beta)^{2}$ and
the first term on the right-hand side of (LABEL:def:linApp) converges and the
second term is of order $1-\beta$. Thus $\tilde{f}^{(i)}(\theta)$ consists of
the two leading order terms. In particular, the second order term gives
insights about the deviation of critical points of the Adam field from
critical points of the vector field $\theta\mapsto{\mathbb{E}}[X(U,\theta)]$
which is the field related to classical gradient descent.

###### Proof.

Note that one has that, for all $x\in[0,\infty)$,

$\displaystyle\begin{split}h^{\prime}(x)=-\frac{1}{(\sqrt{x}+\epsilon)^{2}}\frac{1}{2\sqrt{x}}\text{
\ and \
}h^{\prime\prime}(x)=\frac{1}{(\sqrt{x}+\epsilon)^{3}}\frac{1}{2x}+\frac{1}{(\sqrt{x}+\epsilon)^{2}}\frac{1}{4x^{3/2}}.\end{split}$
(186)

Observe that one has

$\displaystyle\begin{split}(1-\alpha)&\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}\,{\mathbb{E}}\bigl{[}\bigl{(}h(V^{\not=k}(\mathbf{X}^{\theta,(i)}))+h^{\prime}(V^{\not=k}(\mathbf{X}^{\theta,(i)}))(1-\beta)\beta^{-k}(X_{k}^{\theta,(i)})^{2}\bigr{)}\,X_{k}^{\theta,(i)}\bigr{]}\\\
&=(1-\alpha)\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}\,{\mathbb{E}}\Bigl{[}\frac{1}{\sqrt{V^{\not=k}(\mathbf{X}^{\theta,(i)})}+\epsilon}\Bigr{]}\,{\mathbb{E}}[X^{\theta,(i)}_{0}]\\\
&\quad-(1-\alpha)(1-\beta)\sum_{k\in-{\mathbb{N}}_{0}}(\alpha\beta)^{-k}\,{\mathbb{E}}\Bigl{[}\frac{1}{(\sqrt{V^{\not=k}(\mathbf{X}^{\theta,(i)})}+\epsilon)^{2}}\frac{1}{2\sqrt{V^{\not=k}(\mathbf{X}^{\theta,(i)})}}\Bigr{]}{\mathbb{E}}\bigl{[}(X^{\theta,(i)}_{0})^{3}\bigr{]}\\\
&=\tilde{f}^{(i)}(\theta),\end{split}$ (187)

where we used independence of $V^{\not=k}(\mathbf{X}^{\theta,(i)})$ and
$X_{k}^{\theta,(i)}$ in the previous step. Using that for all
$k\in\\-{\mathbb{N}}_{0}$,
$V(\mathbf{X}^{\theta,(i)})=V^{\not=k}(\mathbf{X}^{\theta,(i)})+(1-\beta)\beta^{-k}(X_{k}^{(i)})^{2}$,
we get that

$\displaystyle\begin{split}h&(V^{\not=k}(\mathbf{X}^{\theta,(i)}))+h^{\prime}(V^{\not=k}(\mathbf{X}^{\theta,(i)}))(1-\beta)\beta^{-k}(X^{\theta,(i)}_{k})^{2}\leq
h(V(\mathbf{X}^{\theta,(i)}))\\\ &\leq
h(V^{\not=k}(\mathbf{X}^{\theta,(i)}))+h^{\prime}(V^{\not=k}(\mathbf{X}^{\theta,(i)}))(1-\beta)\beta^{-k}(X^{\theta,(i)}_{k})^{2}\\\
&\qquad\qquad+\frac{1}{2}h^{\prime\prime}(V^{\not=k}(\mathbf{X}^{\theta,(i)}))(1-\beta)^{2}\beta^{-2k}(X^{\theta,(i)}_{k})^{4}.\end{split}$
(188)

Consequently,

$\displaystyle\begin{split}|f^{(i)}(\theta)-\tilde{f}^{(i)}(\theta)|&\leq(1-\alpha)\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}\,\frac{1}{2}(1-\beta)^{2}\beta^{-2k}\,{\mathbb{E}}\bigl{[}h^{\prime\prime}(V^{\not=k}(\mathbf{X}^{\theta,(i)}))|X^{\theta,(i)}_{k}|^{5}\bigr{]}\\\
&=(1-\alpha)\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}\,\frac{1}{2}(1-\beta)^{2}\beta^{-2k}\,{\mathbb{E}}\bigl{[}h^{\prime\prime}(V^{\not=k}(\mathbf{X}^{\theta,(i)}))\bigr{]}\,{\mathbb{E}}\bigl{[}|X^{\theta,(i)}_{0}|^{5}\bigr{]}\end{split}$
(189)

Using that $V^{\not=k}(\mathbf{X}^{\theta,(i)})$ stochastically dominates
$\beta\,V(\mathbf{X}^{\theta,(i)})$, the monotonicity of $h^{\prime\prime}$
and the fact that
$h^{\prime\prime}(x)\leq\frac{3}{4}\frac{1}{(\sqrt{x}+\epsilon)^{2}x^{3/2}}$
we conclude that

$\displaystyle\begin{split}|f^{(i)}(\theta)-\tilde{f}^{(i)}(\theta)|&\leq(1-\alpha)\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}\,\frac{1}{2}(1-\beta)^{2}\beta^{-2k}\,{\mathbb{E}}\bigl{[}h^{\prime\prime}(\beta
V(\mathbf{X}^{\theta,(i)}))\bigr{]}\,{\mathbb{E}}\bigl{[}|X^{\theta,(i)}_{0}|^{5}\bigr{]}\\\
&\leq\frac{3}{8}\frac{(1-\alpha)(1-\beta)^{2}}{\beta^{5/2}(1-\alpha\beta^{2})}\,{\mathbb{E}}\Bigl{[}\frac{1}{(\sqrt{V(\mathbf{X}^{\theta,(i)})}+\epsilon)^{2}\,V(\mathbf{X}^{\theta,(i)})^{3/2}}\Bigr{]}\,{\mathbb{E}}^{\theta}[|X^{\theta,(i)}_{0}|^{5}\bigr{]}.\end{split}$
(190)

∎

In the second part of this section we investigate the Adam field when working
with mini-batches. The crucial result will be a first order approximation when
letting the size of the mini-badges tend to infinity. For a fixed innovation
$(X,U)$ be an innovation, we let ${\mathbb{U}}=(U_{r})_{r\in{\mathbb{N}}}$ be
a sequence of independent copies of $U$ and for every $M\in{\mathbb{N}}$, we
call the innovation $(\mathbb{X}_{M},{\mathbb{U}})$ with

$\displaystyle\begin{split}\mathbb{X}_{M}(u)=\frac{1}{M}\sum_{r=1}^{M}X(u_{r},\theta)\end{split}$
(191)

the _mini-batch innovation of $(X,U)$ of size $M$_.

######  Theorem 8.3.

Let $(X,U)$ be an innovation and $(\alpha,\beta,\epsilon)$ be damping
parameters with $\alpha<\sqrt{\beta}<1$. Let $M\in{\mathbb{N}}$ and
$(\mathbb{X}_{M},{\mathbb{U}})$ be the mini-batch innovation of $(X,U)$ of
size $M$. Moreover, let $\theta\in{\mathbb{R}}^{d}$ and $i\in\\{1,\dots,d\\}$
with

$\displaystyle\begin{split}{\mathbb{E}}[X^{(i)}(U,\theta)]=0\qquad\text{and}\qquad{\mathbb{E}}[|h^{\prime}(\mathbb{V}_{M})|]<\infty.\end{split}$
(192)

Set for $q\in(0,\infty)$,
$\varphi^{(i)}_{q}={\mathbb{E}}[|X^{(i)}(U,\theta)|^{q}]$. Then for the
corresponding Adam vector field $f_{M}$, one has that

$\displaystyle\begin{split}&|f_{M}^{(i)}(\theta)|\leq\beta^{-3/2}\frac{(1-\alpha)(1-\beta)}{1-\alpha\beta}\varphi_{3}\,{\mathbb{E}}[|h^{\prime}(\mathbb{V}_{M}^{(i)})|]\,M^{-2}\\\
&+\beta^{-5/2}\frac{(1-\alpha)(1-\beta)^{2}}{1-\alpha\beta^{2}}{\mathbb{E}}[h^{\prime\prime}(\mathbb{V}_{M}^{(i)})](2C_{3}\varphi_{2}^{(i)}\varphi^{(i)}_{3}M^{-5/2}+5\varphi_{2}^{(i)}\varphi_{3}^{(i)}M^{-3}+\varphi_{5}^{(i)}M^{-4}),\end{split}$
(193)

where $C_{3}$ is the constant in the Burkholder-Davis-Gundy inequality for the
third moment.

In our proof of Theorem 8.3 we will use the following lemma.

######  Lemma 8.4.

Let $A,B$ and $C$ be independent real random variables with $A>0$, almost
surely, and let $h:[0,\infty)\to[0,\epsilon^{-1})$ be as in (179). Provided
that ${\mathbb{E}}[|h^{\prime}(A)|]<\infty$ one has that

$\displaystyle\begin{split}&\bigl{|}{\mathbb{E}}\bigl{[}h(A+(B+C)^{2})C\bigr{]}-\bigl{(}{\mathbb{E}}[h(A+B^{2})]\,{\mathbb{E}}[C]+{\mathbb{E}}[h^{\prime}(A)]\bigl{(}2{\mathbb{E}}[B]\,{\mathbb{E}}[C^{2}]+{\mathbb{E}}[C^{3}]\bigr{)}\bigr{)}\bigr{|}\\\
&\leq{\mathbb{E}}[h^{\prime\prime}(A)]\bigl{(}2{\mathbb{E}}[|B|^{3}]\,{\mathbb{E}}[C^{2}]+5{\mathbb{E}}[B^{2}]\,{\mathbb{E}}[|C|^{3}]+{\mathbb{E}}[|C|^{5}]\bigr{)}.\end{split}$
(194)

In particular, in the case where ${\mathbb{E}}[B]={\mathbb{E}}[C]=0$, one has
that

$\displaystyle\begin{split}\bigl{|}{\mathbb{E}}\bigl{[}h&(A+(B+C)^{2})C\bigr{]}-{\mathbb{E}}[h^{\prime}(A)]\,{\mathbb{E}}[C^{3}]\bigr{|}\\\
&\leq{\mathbb{E}}[h^{\prime\prime}(A)]\bigl{(}2{\mathbb{E}}[|B|^{3}]\,{\mathbb{E}}[C^{2}]+5{\mathbb{E}}[B^{2}]\,{\mathbb{E}}[|C|^{3}]+{\mathbb{E}}[|C|^{5}]\bigr{)}.\end{split}$
(195)

###### Proof.

First note that

$\displaystyle\begin{split}h(A+(B+C)^{2})C&=h(A+B^{2}+2BC+C^{2})C\\\
&=\bigl{(}h(A+B^{2})+h^{\prime}(A+B^{2})(2BC+C^{2})+\psi_{1}\bigr{)}C,\end{split}$
(196)

where as consequence of the Taylor formula and the monotonicity of
$h^{\prime\prime}$,
$|\psi_{1}|\leq\frac{1}{2}h^{\prime\prime}(A)(2BC+C^{2})^{2}$. Moreover,

$\displaystyle\begin{split}h^{\prime}(A+B^{2})=h^{\prime}(A)+\psi_{2},\end{split}$
(197)

where $|\psi_{2}|\leq h^{\prime\prime}(A)B^{2}$. Consequently,

$\displaystyle\begin{split}\bigl{|}h&(A+(B+C)^{2})C-\bigl{(}h(A+B^{2})+h^{\prime}(A)(2BC+C^{2})\bigr{)}C\bigr{|}\\\
&=|\psi_{1}C+\psi_{2}(2BC+C^{2})C|\leq
h^{\prime\prime}(A)\bigl{(}2|B|^{3}C^{2}+5B^{2}|C|^{3}+|C|^{5}\bigr{)}\end{split}$
(198)

and by independence of $A$, $B$ and $C$

$\displaystyle\begin{split}\bigl{|}{\mathbb{E}}\bigl{[}h&(A+(B+C)^{2})C\bigr{]}-{\mathbb{E}}\bigl{[}\bigl{(}h(A+B^{2})+h^{\prime}(A)(2BC+C^{2})\bigr{)}C\bigr{]}\bigr{|}\\\
&\leq{\mathbb{E}}[h^{\prime\prime}(A)]\bigl{(}2{\mathbb{E}}[|B|^{3}]\,{\mathbb{E}}[C^{2}]+5{\mathbb{E}}[B^{2}]\,{\mathbb{E}}[|C|^{3}]+{\mathbb{E}}[|C|^{5}]\bigr{)}.\end{split}$
(199)

The statement follows immediately by using the independence of $A$, $B$ and
$C$. ∎

Using Lemma 8.4 we now present the proof of Theorem 8.3.

###### Proof.

For the proof we can assume without loss of generality that $d=1$. We denote
by $({\mathbb{U}}(k))_{k\in-{\mathbb{N}}_{0}}$ a sequence of independent
random variables each one being identically distributed as ${\mathbb{U}}$ and
we set for $k\in-{\mathbb{N}}_{0}$ and $r\in{\mathbb{N}}$

$\displaystyle\begin{split}X_{k,r}=X({\mathbb{U}}_{r}(k),\theta)\text{ \ and \
}\mathbb{V}_{M}=(1-\beta)\sum_{k\in-{\mathbb{N}}_{0}}\beta^{-k}\Bigl{(}\frac{1}{M}\sum_{r=1}^{M}X_{k,r}\Bigr{)}^{2}.\end{split}$
(200)

Then

$\displaystyle\begin{split}f_{M}(\theta)&=(1-\alpha)\,{\mathbb{E}}\Bigl{[}h(\mathbb{V}_{M})\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}\frac{1}{M}\sum_{r=1}^{M}X_{k,r}\Bigr{]}\\\
&=(1-\alpha)\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}\sum_{r=1}^{M}{\mathbb{E}}\bigl{[}h(\mathbb{V}_{M})\mbox{$\frac{1}{M}$}X_{k,r}\bigr{]}.\end{split}$
(201)

We let

$\displaystyle\begin{split}A_{k,r}=(1-\beta)\sum_{\ell\in-{\mathbb{N}}_{0}\backslash\\{k\\}}\beta^{-\ell}\Bigl{(}\frac{1}{M}\sum_{s=1}^{M}X_{\ell,s}\Bigr{)}^{2},\
B_{k,r}=\sqrt{(1-\beta)\beta^{-k}}\frac{1}{M}\sum_{s\in\\{1,\dots,M\\}\backslash\\{r\\}}^{M}X_{k,s}\end{split}$
(202)

and

$\displaystyle\begin{split}C_{k,r}=\sqrt{(1-\beta)\beta^{-k}}\frac{1}{M}X_{k,r}\end{split}$
(203)

and observe that

$\displaystyle\begin{split}\sqrt{(1-\beta)\beta^{-k}}\,{\mathbb{E}}\bigl{[}h(\mathbb{V}_{M})\mbox{$\frac{1}{M}$}X_{k,r}\bigr{]}={\mathbb{E}}\bigl{[}h(A_{k,r}+(B_{k,r}+C_{k,r})^{2})C_{k,r}\bigr{]}.\end{split}$
(204)

For every choice of $k$ and $r$, the random variables $A_{k,r}$, $B_{k,r}$ and
$C_{k,r}$ are independent and $B_{k,r}$ and $C_{k,r}$ have mean zero.
Therefore, we can apply Lemma 8.4 and get that

$\displaystyle\begin{split}\bigl{|}{\mathbb{E}}\bigl{[}&h(A_{k,r}+(B_{k,r}+C_{k,r})^{2})C_{k,r}\bigr{]}-{\mathbb{E}}\bigl{[}h^{\prime}(A_{k,r})\,C_{k,r}^{3}\bigr{]}\bigr{|}\\\
&\leq{\mathbb{E}}[h^{\prime\prime}(A_{k,r})]\bigl{(}2{\mathbb{E}}[|B_{k,r}|^{3}]\,{\mathbb{E}}[C_{k,r}^{2}]+5{\mathbb{E}}[B_{k,r}^{2}]\,{\mathbb{E}}[|C_{k,r}|^{3}]+{\mathbb{E}}[|C_{k,r}|^{5}]\bigr{)}\end{split}$
(205)

Note that $A_{k,r}$ stochastically dominates $\beta\mathbb{V}_{M}$ so that

$\displaystyle\begin{split}{\mathbb{E}}[|h^{\prime}(A_{k,r})|]\leq{\mathbb{E}}[|h^{\prime}(\beta\mathbb{V}_{M})|]\text{
\ and \
}{\mathbb{E}}[h^{\prime\prime}(A_{k,r})]\leq{\mathbb{E}}[h^{\prime\prime}(\mathbb{V}_{M})].\end{split}$
(206)

Moreover, for every $q\in\\{2,3\\}$ one has

$\displaystyle\begin{split}{\mathbb{E}}[|B_{k,r}|^{q}]&=((1-\beta)\beta^{-k})^{q/2}\,{\mathbb{E}}\Bigl{[}\Bigl{|}\frac{1}{M}\sum_{s\in\\{1,\dots,M\\}\backslash\\{r\\}}X_{0,s}\Bigr{|}^{q}\Bigr{]}\\\
&\leq((1-\beta)\beta^{-k})^{q/2}\,{\mathbb{E}}\Bigl{[}\Bigl{|}\frac{1}{M}\sum_{s=1}^{M}X_{0,s}\Bigr{|}^{q}\Bigr{]}\\\
&\leq((1-\beta)\beta^{-k})^{q/2}\,C_{q}\,{\mathbb{E}}\Bigl{[}\Bigl{|}\frac{1}{M^{2}}\sum_{s=1}^{M}X_{0,s}^{2}\Bigr{|}^{q/2}\Bigr{]}\\\
&\leq((1-\beta)\beta^{-k})^{q/2}\,C_{q}\,\frac{1}{M^{q/2}}{\mathbb{E}}\bigl{[}|X_{0,1}|^{q}\bigr{]},\end{split}$
(207)

where $C_{2}=1$ and $C_{3}$ is the constant appearing in the Burkholder-Davis-
Gundy inequality when applied for the moment $3$. Next, observe that

$\displaystyle\begin{split}{\mathbb{E}}[|C_{k,r}|^{q}]&=((1-\beta)\beta^{-k})^{q/2}\,\frac{1}{M^{q}}{\mathbb{E}}\bigl{[}|X_{0,1}|^{q}\bigr{]}.\end{split}$
(208)

Combining the previous three estimates with (205) we get that

$\displaystyle\begin{split}\bigl{|}{\mathbb{E}}\bigl{[}&h(A_{k,r}+(B_{k,r}+C_{k,r})^{2})C_{k,r}\bigr{]}\big{|}\\\
&\leq{\mathbb{E}}[|h^{\prime}(\beta\mathbb{V}_{M})|]\,((1-\beta)\beta^{-k})^{3/2}\,\varphi_{3}M^{-3}\\\
&\qquad+{\mathbb{E}}[h^{\prime\prime}(\beta\mathbb{V}_{M})]((1-\beta)\beta^{-k})^{5/2}(2\kappa_{3}\varphi_{2}\varphi_{3}M^{-7/2}+5\varphi_{2}\varphi_{3}M^{-4}+\varphi_{5}M^{-5}).\end{split}$
(209)

With (201) and (204) we get that

$\displaystyle\begin{split}|f_{M}(\theta)|&\leq(1-\alpha)\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}\sqrt{(1-\beta)\beta^{-k}}^{-1}M\,{\mathbb{E}}\bigl{[}h(\mathbb{V}_{M})\mbox{$\frac{1}{M}$}X_{k,1}\bigr{]}\\\
&\leq(1-\alpha)\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}(1-\beta)\beta^{-k}\varphi_{3}\,{\mathbb{E}}[|h^{\prime}(\beta\mathbb{V}_{M})|]\,M^{-2}\\\
&\qquad+(1-\alpha)\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}((1-\beta)\beta^{-k})^{2}\,{\mathbb{E}}[h^{\prime\prime}(\beta\mathbb{V}_{M})]\\\
&\qquad\qquad\qquad\qquad(2C_{3}\varphi_{2}\varphi_{3}M^{-5/2}+5\varphi_{2}\varphi_{3}M^{-3}+\varphi_{5}M^{-4})\\\
&\leq\beta^{-3/2}\frac{(1-\alpha)(1-\beta)}{1-\alpha\beta}\varphi_{3}\,{\mathbb{E}}[|h^{\prime}(\mathbb{V}_{M})|]\,M^{-2}\\\
&\qquad+\beta^{-5/2}\frac{(1-\alpha)(1-\beta)^{2}}{1-\alpha\beta^{2}}{\mathbb{E}}[h^{\prime\prime}(\mathbb{V}_{M})](2C_{3}\varphi_{2}\varphi_{3}M^{-5/2}+5\varphi_{2}\varphi_{3}M^{-3}+\varphi_{5}M^{-4}),\end{split}$
(210)

where we have used in the las step that for $x\in(0,\infty)$,
$|h^{\prime}(\beta x)|\leq\beta^{-3/2}|h^{\prime}(\beta x)|$ and
$|h^{\prime\prime}(\beta x)|\leq\beta^{-5/2}|h^{\prime\prime}(\beta x)|$. ∎

We will provide a further lemma which will later allow us to control the terms
${\mathbb{E}}[|h^{\prime}(\mathbb{V}_{M}^{(i)})|]$ and
${\mathbb{E}}[h^{\prime\prime}(\mathbb{V}_{M}^{(i)})]$ appearing in Theorem
8.3.

######  Lemma 8.5.

Let $\beta,\delta,p,q\in(0,\infty)$ with $q<\beta^{p}$ and $\beta<1$ and let
$\mathcal{Z}=(Z_{k})_{k\in-{\mathbb{N}}_{0}}$ be a sequence of independent
real-valued random variables satisfying for every $k\in-{\mathbb{N}}_{0}$ that

$\displaystyle\begin{split}{\mathbb{P}}(Z_{k}^{2}<\delta)\leq q.\end{split}$
(211)

One has

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\frac{1}{v(\mathcal{Z})^{p}}\Bigr{]}\leq\Bigl{(}\frac{\beta}{1-\beta}\Bigr{)}^{p}\frac{1-q}{\beta^{p}-q}\,\delta^{-p},\end{split}$
(212)

where

$\displaystyle\begin{split}v:{\mathbb{R}}^{-{\mathbb{N}}_{0}}\backslash\\{0\\}\to[0,\infty),\
\mathbf{x}\mapsto(1-\beta)\sum_{k\in-{\mathbb{N}}_{0}}\beta^{-k}x_{k}^{2}.\end{split}$
(213)

###### Proof.

As consequence of the assumptions on $\mathcal{Z}$ one can couple
$\mathcal{Z}$ with a sequence of independent Bernoulli distributed random
variables $(I_{k})_{k\in{\mathbb{N}}_{0}}$ with success probability $1-q$ such
that for all $k\in{\mathbb{N}}_{0}$,

$\displaystyle\begin{split}1\mathrm{l}_{\\{Z_{-k}^{2}\geq\delta\\}}\geq
I_{k}.\end{split}$ (214)

We consider the geometrically distributed stopping time

$\displaystyle\begin{split}T=\inf\\{k\in{\mathbb{N}}_{0}:I_{k}=1\\}.\end{split}$
(215)

One has that $v(\mathcal{Z})\geq(1-\beta)\beta^{T}\delta$ so that

$\displaystyle\begin{split}{\mathbb{E}}[v(\mathcal{Z})^{-p}]\leq((1-\beta)\delta)^{-p}\,{\mathbb{E}}[\beta^{-pT}]=((1-\beta)\delta)^{-p}\,\frac{1-q}{1-\beta^{-p}q}.\end{split}$
(216)

∎

##  9 Proof of the theorem in the introduction (Theorem 1.1 in Section 1)

In this section, we prove Theorem 1.1. We fix $d=1$ and denote by $U$ a
uniformly bounded random variable. For every $M\in{\mathbb{N}}$, let
$(\mathbb{X}_{M},{\mathbb{U}})$ be the innovation with
$\mathbb{X}_{M}\colon{\mathbb{R}}^{\infty}\times{\mathbb{R}}\to{\mathbb{R}}$
given by

$\mathbb{X}_{M}(u,\theta)=\frac{1}{M}\sum_{i=1}^{M}u^{(i)}-\theta$ (217)

and ${\mathbb{U}}=(U^{(i)})_{i\in{\mathbb{N}}}$ being a sequence of
independent $U$-distributed random variables. Let
$(\theta^{[M]}_{n})_{n\in{\mathbb{N}}_{0}}$ be an Adam algorithm with
innovation $(\mathbb{X}_{M},{\mathbb{U}})$ and denote by
$({\mathbb{U}}_{k})_{k\in-{\mathbb{N}}_{0}}$ a sequence of independent copies
of ${\mathbb{U}}$ driving the Adam algorithm. We can represent the related
Adam vector field $f_{M}\colon{\mathbb{R}}\to{\mathbb{R}}$ as

$\displaystyle\begin{split}f_{M}(\theta)=(1-\alpha){\mathbb{E}}\Bigl{[}\frac{1}{\epsilon+\sqrt{(1-\beta)\sum_{k\in-{\mathbb{N}}_{0}}\beta^{-k}\mathbb{X}_{M}({\mathbb{U}}_{k},\theta)^{2}}}\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}\mathbb{X}_{M}({\mathbb{U}}_{k},\theta)\Bigr{]}.\end{split}$
(218)

For $\rho\in[0,1)$ and $\theta\in{\mathbb{R}}$, let

$\displaystyle\begin{split}\mathbb{M}_{M}^{\rho}(\theta)=(1-\rho)\sum_{k\in-{\mathbb{N}}_{0}}\rho^{-k}\mathbb{X}_{M}({\mathbb{U}}_{k},\theta)\text{
\ and \
}\mathbb{V}_{M}(\theta)=(1-\beta)\sum_{k\in-{\mathbb{N}}_{0}}\beta^{-k}\mathbb{X}_{M}({\mathbb{U}}_{k},\theta)^{2}.\end{split}$
(219)

Provided that we can change differentiation and integration we get that

$\displaystyle\begin{split}f^{\prime}_{M}(\theta)=-{\mathbb{E}}\Bigl{[}\frac{1}{\epsilon+\sqrt{\mathbb{V}_{M}({\theta})}}\Bigr{]}+{\mathbb{E}}\Bigl{[}\mathbb{M}^{\alpha}_{M}({\theta})\mathbb{M}^{\beta}_{M}({\theta})\frac{1}{(\epsilon+\sqrt{\mathbb{V}_{M}(\theta)})^{2}}\frac{1}{\sqrt{\mathbb{V}_{M}({\theta})}}\Bigr{]}.\end{split}$
(220)

As we will verify below (see (225)) the term in both expectations is uniformly
bounded and continuous which justifies the latter identity.

We first verify that on an arbitrary compact set the vector field $f_{M}$ is
decreasing as long as $M$ is sufficiently large.

######  Lemma 9.1.

Let $V\subset{\mathbb{R}}$ be a compact set. There exists
$M_{0}\in{\mathbb{N}}$ such that

$\displaystyle\begin{split}\sup\\{f^{\prime}_{M}(\theta):M\geq M_{0},\theta\in
V\\}<0.\end{split}$ (221)

We thus showed that for $M\geq M_{0}$ and the chosen $V$ one has that for
every $x,y\in V$ with $x\geq y$, one has