# Unlocking optimal batch size schedules using continuous-time control and
perturbation theory

Stefan Perko Institute for Mathematics, Friedrich-Schiller-University Jena,
07737 Jena, Germany. Email<EMAIL_ADDRESS>
###### Abstract

Stochastic Gradient Descent (SGD) and its variants are almost universally used
to train neural networks and to fit a variety of other parametric models. An
important hyperparameter in this context is the batch size, which determines
how many samples are processed before an update of the parameters occurs.
Previous studies have demonstrated the benefits of using variable batch sizes.
In this work, we will theoretically derive optimal batch size schedules for
SGD and similar algorithms, up to an error that is quadratic in the learning
rate. To achieve this, we approximate the discrete process of parameter
updates using a family of stochastic differential equations indexed by the
learning rate. To better handle the state-dependent diffusion coefficient, we
further expand the solution of this family into a series with respect to the
learning rate. Using this setup, we derive a continuous-time optimal batch
size schedule for a large family of diffusion coefficients and then apply the
results in the setting of linear regression.

##  1 Introduction

Let $d\in\mathbb{N}$ and consider a family of risk functions

$R:\mathbb{R}^{d}\times\mathcal{Z}\to[0,\infty),(\theta,z)\mapsto
R_{z}(\theta)$

and a probability measure $\nu$ on $\mathcal{Z}$. The risk minimization task
associated with $(R,\nu)$ is

$\min_{\theta\in\mathbb{R}^{d}}\mathcal{R}(\theta),$ (1.1)

where $\mathcal{R}(\theta)=\mathbb{E}_{z\sim\nu}[R_{z}(\theta)]$. To solve
(1.1) one frequently uses a one-step method of the form

$\chi_{n+1}^{h}=\chi_{n}^{h}+hf_{nh}(\chi_{n}^{h}),$ (1.2)

for a learning rate $h\in(0,1)$, where $(f_{t}^{h})_{t\geq 0,h\in(0,1)}$ is a
family of independent random functions $\mathbb{R}^{d}\to\mathbb{R}^{d}$.

For convenience we use a continuous time point to index $f$, thereby viewing
(1.2) at the time points $n=0,\dots,\left\lfloor T/h\right\rfloor$ as a
(stochastic) discretization of the following ODE

$dX_{t}^{0}=\mathbb{E}f_{t}(X_{t}^{0})\,dt,\quad t\in[0,T],$ (1.3)

for a given continuous time horizon $T>0$.

We are interested in studying a version of (1.2) called _mini-batch SGD_. To
this end, fix an i.i.d. sequence $\bm{z}_{0},\bm{z}_{1},\dots$, with
$\bm{z}_{0}\sim\nu$, and a sequence of _batch sizes_
$(B_{n})_{n\in\mathbb{N}}$. Consider the sequence of _batches_

$\mathcal{B}_{1}=\\{\bm{z}_{0},\dots,\bm{z}_{B_{1}}\\},\mathcal{B}_{2}=\\{\bm{z}_{B_{1}+1},\dots,\bm{z}_{B_{1}+B_{2}}\\},\dots.$

Then mini-batch SGD, with batch sizes $(B_{n})_{n\in\mathbb{N}}$, uses the
sequence of estimators

$f_{nh}(\theta)=-\frac{1}{B_{n}}\sum_{z\in\mathcal{B}_{n}}\nabla
R_{z}(\theta),\quad n\in\mathbb{N}$ (1.4)

Assuming $\mathbb{E}$ and $\nabla$ commute, we have
$\mathbb{E}f_{nh}(\theta)=-\nabla\mathcal{R}(\theta)$. Further, the covariance
matrix of $f_{nh}$ is given by

$\displaystyle\operatorname{Cov}[f_{nh}(\theta)]=$
$\displaystyle\frac{1}{B_{n}}\Sigma(\theta),$

where

$\Sigma(\theta):=\operatorname{Cov}_{z\sim\nu}[\nabla R_{z}(\theta)].$

for all $\theta\in\mathbb{R}^{d}$. We can identify the sequence of _inverse_
batch sizes as a _volatility control_ $\alpha$, i.e.
$\alpha_{nh}=\frac{1}{B_{n}}$. Since batch sizes are bounded below by $1$, we
have the natural bounds $0\leq\alpha\leq 1$.

For technical reasons and to simplify the upcoming theory considerably, we
require volatility controls to be continuous, which also means we allow non-
integer batch sizes. Thus, for any continuous $\alpha:[0,T]\to[0,1]$, we now
consider a (fictitious) variant of SGD, given by

$\chi_{n+1}^{h,\alpha}=\chi_{n}^{h,\alpha}+hf_{nh}^{h,\alpha}(\chi_{n}^{h}),$
(1.5)

with

$\mathbb{E}[f_{t}^{h,\alpha}(\theta)]=-\nabla\mathcal{R}(\theta),\quad\operatorname{Cov}[f_{t}^{h,\alpha}(\theta)]=\alpha_{t}\Sigma(\theta),$

for all $h\in(0,1),t\in[0,T]$ and $\theta\in\mathbb{R}$. We refer to (1.5) as
_fractional batch size SGD_.

Now, our goal is finding an _optimal_ sequence of batch sizes, so that the
error $\mathbb{E}[\mathcal{R}(\chi_{M}^{h})]$ for a given final time step $M$
is minimal.

Of course, stating the problem this way suggests setting the batch size to be
maximal, since this makes our estimate of the true gradient as accurate as
possible. However, a higher batch size also means higher computational cost.
Therefore, we will postulate the condition that the number of data points used
is fixed, i.e.

$\sum_{n=1}^{M}B_{n}=\frac{c}{h}$ (1.6)

for some constant $c\geq T$, where we divide by $h$, with $c/h\in\mathbb{N}$,
for convenience. For SGD _without replacement_ 111Note that our theory
technically only applies to SGD without replacement, with a _single_ epoch.
(which is commonly used in practice) one would usually consider
$\frac{c}{h}=\text{sample size}\times\text{epochs}$. Insisting that $c\geq T$
is natural, since, for $T/h\in\mathbb{N}$,

$\frac{c}{h}=\text{number of samples processed}\geq\text{number of SGD
steps}=\frac{T}{h},$

and the lower bound is obtained by choosing batch size $1$ in each step.
Suppose $B=\alpha^{-1}$. Then under Condition (1.6),

$c=h\sum_{n=1}^{\left\lfloor T/h\right\rfloor}B_{nh}=h\sum_{n=1}^{\left\lfloor
T/h\right\rfloor}\frac{1}{\alpha_{nh}}\to\int_{0}^{T}\frac{1}{\alpha_{t}}\,dt,\quad
h\downarrow 0.$

Thus, in the continuous-time setting, condition (1.6) corresponds to the
following condition on the volatility control

$\int_{0}^{T}\frac{1}{\alpha_{t}}\,dt=c.$ (1.7)

Therefore, we may consider the following optimal volatility control problem:
Given $c\geq T>0$, determine

$\operatorname*{\operatorname{argmin}}_{\alpha\in
A(L)}\mathbb{E}[\mathcal{R}(\chi_{\left\lfloor
T/h\right\rfloor}^{h,\alpha})],$ (1.8)

where the set of admissible controls is given by

$A(L)=\\{\alpha:[0,T]\to[0,1]:\|\sqrt{\alpha}\|_{\operatorname{Lip}}\leq
L,\int_{0}^{T}\frac{1}{\alpha_{t}}\,dt=c\\},$

for some sufficiently large $L>0$. The Lipschitz condition on $\sqrt{\alpha}$
is necessary for the continuous-time theory (cf. Section 3) to be applicable
to this problem.

Initially, one could hope to find an explicit solution to (1.8), at least in
dimension $d=1$. However, this is very difficult or perhaps impossible.
Following [16], our idea is instead to approximate the discrete-time SGD
iterations using a family of continuous-time diffusion processes. Then we can
apply optimal control theory to the approximating stochastic differential
equations and solve (1.8), _up to_ an error $Ch^{2}$, where $h$ is the
learning rate and $C$ is an increasing function of the parameter $L$. The
explicit solution of this relaxed problem is the content of our main result
Theorem 2.1. Since the goal is to find an explicit solution, a further
complication arises. In most problems, the variance of the sample gradients
$\Sigma$ is non-constant and even state-dependent. We solve this issue by
expanding the diffusion approximation again into a series with respect to the
learning rate. This allows for a significant simplification of the control
problem.

Aside from focusing on batch size rather than learning rate schedules, our
work extends the approach in [16] in several aspects:

##### Summary of contributions

  * •

We establish, to our knowledge for the first time, a _rigorous_ theory for
transferring deterministic optimal controls from a continuous-time diffusion
approximation of a numerical one-step stochastic method back to discrete-time.
This includes extending the theory of (second-order) stochastic modified
equations in [15] to allow for time-dependent drift and diffusion
coefficients. Thus, we are able to study SGD with learning rate and batch size
schedules in continuous-time.

  * •

Using perturbation theory, we reduce the continuous-time optimal control
problem to a linear control problem, without resorting to unrealistic
assumptions on the diffusion coefficient. In particular, in contrast to
previous works, we do _not_ assume the variance of the sampled gradients
$\Sigma$ to be constant and explicitly allow it to be state-dependent.

  * •

We demonstrate the potential of our theory by deriving an _explicit_ quasi-
optimal batch size schedule using the continuous-time Pontryagin maximum
principle.

We remark that in practice it is reasonable to use the largest mini-batch size
such that all mini-batches fit into memory. In this setting we will use the
term _batch size_ to refer to _gradient accumulation_ instead, i.e. the number
of batches until an update is made. We will no longer explicitly make this
distinction, because it makes no essential difference to our theory.

##### Failure of the first-order batch size theory

To solve a the optimal batch size control problem, at least in a relaxed
sense, we expand the expected risk $\mathbb{E}[\mathcal{R}(\chi_{\left\lfloor
T/h\right\rfloor}^{h})]$ into a series in $h$ with a remainder term of size
$h^{k}$ for some $k\in\mathbb{N}$ . Then we seek a statement of the following
form. Fix $L>0$ sufficiently large. Then there exists a $C$, depending on $L$,
and a $\alpha^{*}\in A(L)$, such that

$\left|\inf_{\alpha^{*}\in A(L)}\mathbb{E}\mathcal{R}(\chi_{\left\lfloor
T/h\right\rfloor}^{h,\alpha})-\mathbb{E}\mathcal{R}(\chi_{\left\lfloor
T/h\right\rfloor}^{h,\alpha^{*}})\right|\leq Ch^{k}.$ (1.9)

For example, if we let $k=1$, then we can approximate SGD using a continuous-
time first-order approximation, e.g. (cf. [16])

$dX_{t}^{h}=-\nabla\mathcal{R}(X_{t}^{h})\,dt+\sqrt{h\alpha_{t}\Sigma(X_{t}^{h})}\,dW_{t}.$

The following negative result demonstrates why considering $k=1$ in (1.9) is
too crude for a useful theory of almost optimality of batch size schedules.

######  Proposition 1.1.

Let $L>0$. There exists a $C>0$, such that for all
$\alpha^{*}\in\mathcal{A}_{L}$, we have

$\left|\inf_{\alpha^{*}\in A(L)}\mathbb{E}\mathcal{R}(\chi_{\left\lfloor
T/h\right\rfloor}^{h,\alpha})-\mathbb{E}\mathcal{R}(\chi_{\left\lfloor
T/h\right\rfloor}^{h,\alpha^{*}})\right|\leq Ch.$

###### Proof sketch.

Consider Theorem .1. A similar result shows that gradient flow

$dX_{t}^{0}=-\nabla\mathcal{R}(X_{t}^{0})\,dt$

is a first-order approximation of SGD, i.e. there exists a $C>0$, such that

$|\mathbb{E}\mathcal{R}(\chi_{\left\lfloor
T/h\right\rfloor}^{h,\alpha^{*}})-\mathbb{E}\mathcal{R}(X_{T}^{0})|\leq Ch,$

for all $h\in(0,1)$. Moreover, this $C$ can be chosen independently of
$\alpha\in A(L)$, and so, similarly to Corollary .3,

$|\inf_{\alpha\in A(L)}\mathbb{E}\mathcal{R}(\chi_{\left\lfloor
T/h\right\rfloor}^{h,\alpha})-\mathbb{E}\mathcal{R}(X_{T}^{0})|\leq\tilde{C}h.$

By the triangle inequality the result follows. ∎

##  2 Main result

Set $d=1$. Given a function $g:\mathbb{R}\to\mathbb{R}$ write
$g\in\operatorname{Lip}^{l}$ if $g\in C^{l}$ and $\partial^{k}g$ is Lipschitz,
for all $k\in\\{0,\dots,l\\}$.

We make the following technical assumptions on $\mathcal{R}$ and $\Sigma$.

Assumption (A1) The function $\mathcal{R}:\mathbb{R}\to\mathbb{R}$ is in
$C^{5}$, $\mathcal{R}^{\prime}\in\operatorname{Lip}^{4}$,
$\sqrt{\Sigma}\in\operatorname{Lip}^{3}$ and $\Sigma>0$ everywhere. Further,
the linear growth condition

$|\mathcal{R}^{\prime}(\theta)|+|\sqrt{\Sigma(\theta)}|\lesssim
1+|\theta|,\theta\in\mathbb{R}$

holds. Finally,

$|\mathcal{R}(\theta)|\lesssim 1+|\theta|^{2},\theta\in\mathbb{R},$

and $\mathcal{R}^{\prime\prime}(X_{T}^{0})>0$, where $X^{0}$ is gradient flow
(cf. Equation (3.3)).

Since $\mathcal{R}^{\prime\prime}$ is bounded, the product
$\mathcal{R}^{\prime\prime}\mathcal{R}^{\prime}$ is Lipschitz and of linear
growth as well.

Assumption (A2) There exists a random variable $Z$ with finite moments, such
that

$|f_{t}^{h,\alpha}(\theta)|\leq Z(1+|\theta|),a.s.,$

for all $h\in[0,1],\text{Lipschitz continuous }\alpha:[0,T]\to[0,1],t\in[0,T]$
and $\theta\in\mathbb{R}$.

Our main result provides an explicit relaxed solution of the optimal
volatility control problem (1.8) in dimension $d=1$.

######  Theorem 2.1.

Assume (A2) and (A2) and consider fractional batch size SGD (equation (1.5))
with a fixed initial value $\chi_{0}\in\mathbb{R}$. Let $T>0$ and consider the
solution $X^{0}$ to the so called gradient flow ODE

$dX_{t}^{0}=-\mathcal{R}^{\prime}(X_{t}^{0})\,dt,\quad X_{0}^{0}=\chi_{0},$
(2.1)

Set

$\beta_{t,T}^{1}=-\int_{t}^{T}\mathcal{R}^{\prime\prime}(X^{0}_{s})\,ds,\quad\beta_{t,T}^{2}=-\int_{t}^{T}\mathcal{R}^{\prime\prime\prime}(X^{0}_{s})\,ds,$
$\eta_{t,T}=\begin{cases}\frac{e^{-\beta_{t,T}^{1}}-e^{-2\beta_{t,T}^{1}}}{\beta_{t,T}^{1}},&\beta_{t,T}^{1}\neq
0,\\\ 1,&\beta_{t,T}^{1}=0,\end{cases}$
$\delta_{t,T}=e^{-2\beta_{t,T}^{1}}\mathcal{R}^{\prime\prime}(X^{0}_{t})-\beta_{t,T}^{2}\eta_{t,T}\mathcal{R}^{\prime}(X^{0}_{t})>0,$

and

$\alpha_{t}^{*}(\lambda)=\sqrt{\frac{2\lambda}{\delta_{t,T}\Sigma(X_{t}^{0})}}\wedge
1,\quad\lambda>0,$ (2.2)

for all $t\in[0,T]$. Then there exists a constant $\lambda>0$, such that for
all $L\geq\|\sqrt{\alpha^{*}(\lambda)}\|_{\operatorname{Lip}}$, there exists
constant $C>0$, depending on $L$, with

$|\min_{\alpha\in A(L)}\mathbb{E}\mathcal{R}(\chi_{\left\lfloor
T/h\right\rfloor}^{h,\alpha})-\mathbb{E}\mathcal{R}(\chi_{\left\lfloor
T/h\right\rfloor}^{h,\alpha^{*}})|\leq Ch^{2},\quad h\in(0,1).$

Here $\wedge=\min$. The proof of Theorem 2.1 is postponed to Appendix .

##  3 Continuous-time theory of mini-batch SGD

The proof of Theorem 2.1 relies crucially on a continuous-time theory of SGD
and results for relating discrete and continuous time. There are three main
steps to proving our main result:

  1. (i)

approximating SGD with a family of stochastic differential equations indexed
by the learning rate,

  2. (ii)

applying perturbation theory to the approximating family of stochastic
differential equations, thereby expanding it again into a series with respect
to the learning rate,

  3. (iii)

stating and solving an optimal control problem for this series expansion.

Finally, we transfer the solution to the latter optimal control problem back
to the discrete SGD process. In this section we briefly sketch these ideas
while details are referred to the Appendices.

###  3.1 Diffusion approximation

Denote by $\nabla^{2}f$ the Hessian matrix of a function $f\in
C^{2}(\mathbb{R}^{d})$. Set $b^{0}:=-\nabla\mathcal{R}$ and
$b^{1}:=-\frac{1}{4}\nabla|\nabla\mathcal{R}|^{2}$. Roughly following Li et.
al [15], the dynamics of (1.5) can be approximated by the $h$-indexed family
of stochastic differential equations

$dX_{t}^{h}=b^{0}(X_{t}^{h})+hb^{1}(X_{t}^{h})\,dt+\sqrt{h\alpha_{t}\Sigma(X_{t}^{h})}\,dW_{t},$
(3.1)

We also denote the solution of (3.1) for a given volatility control $\alpha$
and $h\in(0,1)$ by $X^{h,\alpha}$.

We refer to Equation (3.1) as a _weak second-order diffusion approximation_ of
(1.2), since, under reasonable conditions, for all $T>0$ there exists a $C>0$,
such that for all smooth $g:\mathbb{R}^{d}\to\mathbb{R}$ with derivatives of
at most polynomial growth, we have

$\max_{n\in\\{0,\dots,\left\lfloor
T/h\right\rfloor\\}}|\mathbb{E}[g(\chi_{n}^{h})]-\mathbb{E}[g(X_{nh}^{h})]|\leq
Ch^{2},$ (3.2)

for all $h\in(0,1)$, given that the diffusion approximation and SGD have the
same starting point, that is $X_{0}^{h}=\chi_{0}$.

In contrast to this diffusion approximation, in the literature on SGD one
commonly considers the gradient flow ODE

$dX_{t}^{0}=-\nabla\mathcal{R}(X_{t}^{0})\,dt$ (3.3)

as a continuous-time version of SGD. This is not sufficient for an analysis of
batch sizes, since the dynamics only depend on the mean of the sampled
gradients. On the other hand, batch sizes only appear in the covariance matrix
of the gradient noise, which is why we consider the stochastic dynamics (3.1)
instead. Putting that aside, the approximation quality of (3.3) is worse
compared to (3.1) since it is merely of first-order, i.e. for all $T>0$ there
exists a $C>0$, such that for all smooth $g:\mathbb{R}^{d}\to\mathbb{R}$ with
derivatives of at most polynomial growth, we have

$\max_{n\in\\{0,\dots,\left\lfloor
T/h\right\rfloor\\}}|\mathbb{E}[g(\chi_{n}^{h})]-\mathbb{E}[g(X_{nh}^{0})]|\leq
Ch,$ (3.4)

for all $h\in(0,1)$, given that $X_{0}^{0}=\chi_{0}$.

Under reasonable conditions we can make the constant $C$ in (3.2) independent
on the choice of volatility control. This allows us, in some sense, to replace
the discrete time control problem 1.8 with the continuous-time control problem

$\operatorname*{\operatorname{argmin}}_{\alpha\in
A(L)}\mathbb{E}[\mathcal{R}(X_{T}^{h,\alpha})],$ (3.5)

so that we can use tools from stochastic calculus and continuous-time optimal
control. Details for this transfer from discrete to continuous time are
deferred to Appendix .

Unfortunately, Problem (3.5) is still too difficult to be solved explicitly,
primarily because of the covariance matrix $\Sigma$. For example, even in one-
dimensional linear regression tasks $\Sigma$ is already a quadratic polynomial
and there is generally no hope that $\Sigma$ simplifies, say, to a constant.

To rectify this issue, in the subsection we introduce an expansion of (3.1)
with respect to the learning rate.

###  3.2 Expansions in the learning rate

Consider again the approximation result (3.2). Based on this we can
approximate the risks

$|\mathbb{E}\mathcal{R}(\chi_{n}^{h})-\mathbb{E}\mathcal{R}(X_{nh}^{h})|=\mathcal{O}(h^{2}).$

However, if we expand the risk of the diffusion approximation into a Taylor
series with respect to the learning rate $h$ as follows

$\mathcal{R}(X_{t}^{h})=\mathcal{R}^{(0)}_{t}+h\mathcal{R}^{(1)}_{t}+\mathcal{O}(h^{2}),$

then all terms beyond $h^{2}$ are not known to contribute (positively or
negatively) to the approximation error in (3.2). Therefore, in order to find
optimal batch sizes for (1.2) we do not lose any accuracy if we change (3.5)
such that we minimize

$\mathbb{E}[\mathcal{R}^{(0)}_{t}+h\mathcal{R}^{(1)}_{t}]$

instead.

We can find $R^{(q)}$ by also considering a series expansion for the diffusion
approximation

$X_{t}^{h}=X^{0}_{t}+\sqrt{h}X^{(1/2)}_{t}+hX^{(1)}_{t}+h^{3/2}X^{(3/2)}_{t}+\mathcal{O}(h^{2})$
(3.6)

Then one can derive a system of stochastic differential equations for
$X^{0},X^{(1/2)},\dots$ which is in a triangular form and such that the
equations for $X^{(1/2)},X^{(1)}$ and $X^{(3/2)}$ are linear, given $X^{0}$.

Given the expansion (3.6), one can show that for $\mathcal{R}\in
C^{2}(\mathbb{R})$ we have

$\mathbb{E}[\mathcal{R}(X^{h})]=\mathcal{R}(X^{0})+h\left(\frac{1}{2}\mathcal{R}^{\prime\prime}(X^{0})\operatorname{Var}[X^{(1/2)}]+\mathcal{R}^{\prime}(X^{0})\mathbb{E}[X^{(1)}]\right)\\\
+\mathcal{O}(h^{2}),$ (3.7)

conditional on the initial condition $X_{0}=\chi_{0}$. Here, $X^{0}$ is
gradient flow, as in equation (3.3). Note that the process $X^{(3/2)}$
introduced in (3.6) plays no role in the expansion of the expected risk.
Further, we have

$\displaystyle d\operatorname{Var}[X^{(1/2)}_{t}]=$ $\displaystyle
2\mathcal{R}^{\prime\prime}(X^{0}_{t})\operatorname{Var}[X^{(1/2)}_{t}]+\alpha_{t}\Sigma(X_{t}^{0})\,dt,$
(3.8) $\displaystyle d\mathbb{E}[X_{t}^{(1)}]=$
$\displaystyle\frac{1}{2}\mathcal{R}^{\prime\prime\prime}(X^{0}_{t})\operatorname{Var}[X^{(1/2)}_{t}]+\mathcal{R}^{\prime\prime}(X^{0}_{t})\mathbb{E}[X_{t}^{(1)}]+b^{1}(X_{t}^{0})\,dt,$
(3.9)

In essence, in (3.7), we are correcting the mean risk of gradient flow by
terms depending on the learning rate $h$, the randomness inherent to SGD and
the fact that even deterministic gradient descent with finite learning rate
essentially optimizes the modified objective

$\mathcal{R}+\frac{h}{4}|\nabla\mathcal{R}|^{2},$

which is evident from the drift coefficient in equation (3.1).

Since gradient flow does not depend on the volatility control, our problem
simplifies to

$\operatorname*{\operatorname{argmin}}_{\alpha\in
A(L)}\frac{1}{2}\mathcal{R}^{\prime\prime}(X^{0}_{T})\operatorname{Var}[X^{(1/2),\alpha}_{T}]+\mathcal{R}^{\prime}(X^{0}_{T})\mathbb{E}[X^{(1),\alpha}_{T}],$
(3.10)

where we indicated the dependence of $X^{(1/2)}$ and $X^{(1)}$ on $\alpha$.

###  3.3 Batch size control

In order to solve (3.10) we take a look at the Lagrange dual problem, i.e. for
$\lambda>0$ we consider

$\operatorname*{\operatorname{argmin}}_{\alpha\in
A^{\prime}(L)}\frac{1}{2}\mathcal{R}^{\prime\prime}(X_{T}^{0})\operatorname{Var}[X^{(1/2),\alpha}_{T}]+\mathcal{R}^{\prime}(X_{T}^{0})\mathbb{E}[X_{T}^{(1),\alpha}]+\lambda\int_{0}^{T}\frac{1}{\alpha_{t}}\,dt,$
(3.11)

where $\operatorname{Var}[X^{(1/2),\alpha}]$ and $\mathbb{E}[X^{(1),\alpha}]$
satisfy (3.8) and (3.9), respectively, and

$A^{\prime}(L)=\\{\alpha:[0,T]\to[0,1]:\|\sqrt{\alpha}\|_{\operatorname{Lip}}\leq
L\\}.$

If $\alpha^{*}(\lambda)$ is a solution to (3.11) and there exists a
$\lambda>0$ with

$\int_{0}^{T}\frac{1}{\alpha_{t}^{*}(\lambda)}\,dt=c,$ (3.12)

then $\alpha^{*}(\lambda)$ solves the primal problem (3.10).

To solve (3.11), we apply the Pontryagin maximum principle (cf. [19] Chapter
6.4 for more details on the maximum principle) to the two-dimensional system
of linear equations, (3.8) and (3.9). This is relatively straightforward and
yields the optimal volatility control (2.2). Details can be found Appendix .

##  4 Optimal batch sizes for linear regression

In this section we apply Theorem 2.1 to the problem of linear regression with
mini-batch SGD.

###  4.1 The statistical learning setting

Suppose we are given random variables $\bm{x}$ and $\bm{\varepsilon}$ defined
on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, such that $\bm{x}$
and $\bm{\varepsilon}$ are independent,
$\mathbb{E}\bm{\varepsilon}=0,\sigma_{\varepsilon}^{2}:=\mathbb{E}\bm{\varepsilon}^{2}<\infty$
and $\mathbb{E}\bm{x}^{4}<\infty$. Let $\theta^{*}\in\mathbb{R}^{d}$. We
define the $\mathbb{R}$-valued random variable $\bm{y}$ by

$\bm{y}=\theta^{*}\bm{x}+\bm{\varepsilon}.$

Denote the distribution of $(\bm{x},\bm{y})$ by $\nu$. We call $\nu$ the
_population_. We consider applying SGD to a sequence of i.i.d. data points
$(\bm{x}_{0},\bm{y}_{0}),(\bm{x}_{1},\bm{y}_{2}),\dots$, drawn from $\nu$,
which follows a linear model. The population is considered unknown to us.

Let $\ell$ be the _square loss_ , given by
$\ell(y,y^{\prime})=\frac{1}{2}(y-y^{\prime})^{2}$. The goal is to fit the
data drawn from $\nu$ using a linear predictor $\theta\mapsto\theta x$. Thus,
for any data point $(x,y)\in\mathbb{R}\times\mathbb{R}$ we consider the
squared risk

$R_{x,y}(\theta)=\ell(\theta x,y)=\frac{1}{2}(\theta x-y)^{2}.$

We define the _population risk_ by

$\mathcal{R}(\theta):=\mathbb{E}[R_{\bm{x},\bm{y}}(\theta)].$

We stress that the bold letters $\bm{x},\bm{y}$ denote random variables, while
$x,y$ represent realizations. The minimum of $\mathcal{R}$, i.e. the best
possible fit, is given by the population parameter $\theta^{*}$.

Then, we have

$\displaystyle\mathcal{R}(\theta)=\frac{1}{2}\kappa(\theta-\theta^{*})^{2}+\mathcal{R}^{*},\quad\mathcal{R}^{\prime}(\theta)=\kappa(\theta-\theta^{*}),\quad\mathcal{R}^{\prime\prime}(\theta)=\kappa,$

where $\kappa:=\operatorname{Var}\bm{x}$ and
$\mathcal{R}^{*}:=\inf_{\theta\in\mathbb{R}}\mathcal{R}(\theta)=\frac{\sigma_{\varepsilon}^{2}}{2}$
is the smallest possible population risk. Further,

$\Sigma(\theta)=\operatorname{Var}[\partial_{\theta}\ell(\theta\bm{x},\bm{y})]=\kappa^{2}(\operatorname{Kurt}\bm{x}-1)(\theta-\theta^{*})^{2}+2\kappa\mathcal{R}^{*},$

where $\operatorname{Kurt}(\bm{x}):=\mathbb{E}[\bm{x}^{4}]/\kappa^{2}$ is the
_kurtosis_ of $\bm{x}$. Note that, e.g., $\operatorname{Kurt}\bm{x}=3$ if
$\bm{x}\sim\mathcal{N}(0,\kappa)$.

###  4.2 Optimal volatility

Consider Theorem 2.1, now in the case of linear regression as outlined in the
previous subsection. Gradient flow satisfies

$dX^{0}_{t}=-\kappa(X^{0}_{t}-\theta^{*})\,dt,X_{0}^{0}=\chi_{0}.$

and so

$X^{0}_{t}=\left(\chi_{0}-\theta^{*}\right)e^{-\kappa t}+\theta^{*}.$

Define the _excess population risk_
$\mathcal{R}^{e}=\mathcal{R}-\mathcal{R}^{*}$ and the _initial excess
population risk_ $\mathcal{R}^{e}_{0}=\mathcal{R}(\chi_{0})-\mathcal{R}^{*}$.
Then the excess population risk of gradient flow at time $t$ satisfies
$\mathcal{R}^{e}(X_{t}^{0})=\mathcal{R}_{0}^{e}e^{-2\kappa t}$. Thus,

$\Sigma(X_{t}^{0})=2\kappa((\operatorname{Kurt}\bm{x}-1)\mathcal{R}_{0}^{e}e^{-2\kappa
t}+\mathcal{R}^{*}).$

Coming back to the solution of the control problem given by Theorem 2.1, we
have $\beta_{t,T}^{1}=-\kappa(T-t)$ and $\beta_{t,T}^{2}=0$. Hence,

$\delta_{t,T}=e^{-2\beta_{t,T}^{1}}\mathcal{R}^{\prime\prime}(X_{T}^{0})=\kappa
e^{-2\kappa(T-t)},$

and the optimal volatility control is

$\displaystyle t\mapsto$
$\displaystyle\sqrt{\frac{\lambda}{\kappa^{2}e^{-2\kappa(T-t)}((\operatorname{Kurt}\bm{x}-1)\mathcal{R}_{0}^{e}e^{-2\kappa
t}+\mathcal{R}^{*})}}\wedge 1.$

After a linear re-parameterization and setting
$\gamma:=\frac{R_{0}^{e}}{R^{*}}(\operatorname{Kurt}\bm{x}-1)$, we have

$\alpha_{t}^{*}(\lambda)=\sqrt{\frac{\lambda}{\gamma+e^{2\kappa t}}}\wedge
1,\quad t\in[0,T],\lambda>0.$ (4.1)

For $\lambda>0$ such that (3.12) is satisfied, $\alpha^{*}(\lambda)$ is the
optimal volatility control for the linear regression problem. Figure 1 shows
$\alpha^{*}$ for different values of $\lambda$ and $\gamma$. In the case that
the upper bound of $1$ is never attained, $\lambda$ can be calculated
explicitly (cf. Appendix ).

Figure 1: Optimal volatility control $\alpha^{*}$ for linear regression, with
$\lambda=75$ (left) / $300$ (right), $\gamma=280$ and $\kappa=1$. On the
right, the time point $\hat{t}\approx 1.5$, where volatility switches away
from $1$ is indicated by the dotted, vertical line. On the left, we have
$\alpha^{*}<1$ everywhere.

Note that the optimal volatility control $\alpha^{*}$ in (4.1) is non-
increasing. Hence, for every $\lambda>0$ there exists a unique
$\check{t}(\lambda)\in[0,T]$ with $\alpha_{t}^{*}(\lambda)<1$ for all
$t\in[\check{t},T]$. In fact, we have

$\frac{\lambda}{\gamma+e^{2\kappa t}}=1\Leftrightarrow
t=\frac{1}{2\kappa}\ln(\lambda-\gamma),$

provided $\lambda-\gamma\geq 1$. Hence, the time point where we switch away
from volatility $1$ is given by

$\check{t}(\lambda)=\begin{cases}\frac{1}{2\kappa}\ln(\lambda-\gamma),&\lambda>\gamma+1,\\\
0,&\text{else}.\end{cases}$

###  4.3 A numerical example

In this subsection we use the optimal volatility control (4.1) for numerically
estimating the true parameter $\theta^{*}$ in a linear regression problem,
using mini batch SGD. Experimental details are deferred to Appendix .

Figures 2 depict the results of two runs of the experiment for different
parameter values. As expected, increasing the batch size leads to lower
population risk at the end of training. In the examples, the difference to
using constant batch size can be more than one order of magnitude. Also, in
Figure 2 we see that, additionally, in the early stages of training, we can
use lower batch sizes than the constant schedule for significantly faster
convergence, in terms of samples processed. It should be pointed out that the
effects of optimized batch schedules are more prominent fo longer training
times, since there is a greater range of batch sizes one can use. Conversely,
if we have too few iterations, then the “optimal” and constant schedules
coincide.

Figure 2: Excess population risk of mini batch SGD as a function of the number
of samples processed, averaged over $1000$ instances each, with constant batch
size of $4$ (left) / $8$ (right) and using an “optimal” batch size schedule
(bs-opt). Here, the sample size is $N=2^{10}$ / $2^{13}$, the number of steps,
i.e. batches, is $M=256$ / $2^{10}$, and the learning rate is $h=0.05$ /
$0.01$. The right $y$-axis specifies the number of samples used by bs-opt.

##  5 Limitations

There are several limitations to the main result Theorem 2.1.

Firstly, the dimension is fixed to $1$. However, we suspect that the behavior
of our quasi-optimal volatility control also yield great benefits in higher
dimensions. A large portion of the theory could in principle be developed in
higher dimensions. Unfortunately, in this case the optimal control problem
(3.5) cannot be reduced to a problem of controlling a system of ordinary
differential equations. Instead, one needs to consider systems of non-linear
fully-coupled forward backward stochastic differential equations and resort to
numerical methods for computing the optimal control. Solving high-dimensional
non-linear FBSDEs is again a difficult problem, which requires using deep
learning techniques (cf. [13]). That makes it prohibitively expensive to use
such a method in practice. Alternatively, one could study a continuous-time
mean-field approximation of SGD applied to high-dimensional problems (cf.
[11]).

Secondly, the optimal volatility control depends on the gradient flow
solution, which generally cannot be derived explicitly. Moreover, it would be
more natural for the optimal control to be Markov, i.e. a function of the
current parameter iterate $\chi_{n}$. However, this would require developing
sophisticated approximation results, based on causal optimal transport, that
allow for the transfer of stochastic optimal controls (cf. [1]).

Thirdly, our results only apply to the fictitious fractional batch size SGD.
If we round our optimal schedule in any way, then the optimality result would
only hold up to a term of order $1$ in the learning rate, which is crude.
Extending diffusion approximations to allow for discontinuous volatility
controls is a difficult issue and would likely change the approximating
equations to feature local times, since we have to resort to using the Itô-
Tanaka formula when deriving the stochastic Taylor approximations (cf.
Proposition .14 in Appendix ).

Fourthly, several quantities featured in the optimal volatility schedule are
difficult to compute or estimate in practice. This includes the integrals
$\int_{t}^{T}$ looking forward in time, the Lagrange mutliplier $\lambda$, as
well as population parameters, such as $\mathcal{R}^{*}$ (cf. Equation 4.1).

Finally, the assumptions on the coefficient of the diffusion approximation
(A2) are technical, restrictive and sometimes violated in examples. Lipschitz
and linear growth conditions are standard in the stochastic differential
equation literature to ensure existence and uniqueness of global solutions,
but they can be significantly relaxed, possibly even to the point of
considering weak solutions. The smoothness and boundedness of the derivatives
of the coefficients is used mainly to derive a result on differentiation with
respect to the initial condition.

##  6 Related Work

##### Batch size schedules

In practice it is common to chose a constant batch size. However, it has been
observed before that increasing batch size during training of neural networks
can be beneficial (cf. [20], [10], [8], [4], [7], [9]). The batch size
schedules derived in these works are based on useful heuristics. In contrast,
we use optimal control theory for deriving a theoretically (quasi-) optimal
schedule. While some of these works emphasize an equivalence of increasing
batch size and decreasing learning rate, our theory breaks this symmetry, by
using the (maximal) learning rate $h$ for development of the continuous-time
approximation. Further, we remark that learning rate _schedules_ affect the
dynamics of gradient flow, while the batch size, which only affects
volatility, does not.

Finally, the idea of deriving optimal batch size schedules using diffusion
approximations was also studied by Zhao et. al in [22], which we were unaware
of at the time of writing this paper. One of the great the strengths of their
paper is that they derive their schedule in higher dimensions, which increases
its applicability significantly compared to our work. However, we still feel
our article has several theoretical strengths over [22]:

  1. (a)

They assume throughout that their objective function is quadratic. This is
e.g. the case for linear regression, which we also study in Section 4.
However, our main Theorem 2.1 makes no such assumption and holds for quite
general objective functions.

  2. (b)

Equation (3) in [22] is a first-order approximation of SGD and therefore of
worse quality (i.e in having a non-zero linear error term) than the second-
order approximation(s) we use. Specifically, it is a good approximation only
for much smaller learning rates compared to the approximation we consider
(because if, say, $h=10^{-3}$, then already $h^{2}=10^{-6}$). In fact,
gradient flow is also a first-order approximation of SGD which does not
contain the batch size at all, but is still not known to be worse than (3).
Therefore, up to an error of $h$, any batch size schedule (barring Lipschitz
assumptions, etc.) is “optimal” for SGD. This is the content of Proposition
1.1.

  3. (c)

In Section 4 of [22] $\Sigma$ is assumed to be constant. We went to great
lengths to avoid this commonly made assumption, because it would reduce the
quality of our approximation from second to first-order. Instead we deal with
state-dependent diffusion coefficients using the perturbation theory approach,
retaining the second-order approximation quality.

  4. (d)

Theorem 4.2 in [22] gives the optimal control for the SDE approximation, but
does not say anything directly about SGD. In contrast, our main theorem
pertains directly to (fractional batch size) SGD (see last inequality in
Theorem 2.1).

In the future it would be interesting to see whether the methods of [22] and
our work can be combined to derive even better results.

##### Diffusion approximations

Continuous-time diffusion approximations to SGD, also known as _stochastic
modified equations_ , have been heuristically introduced in [17] and [16], and
theoretically substantiated in [15]. Since then numerous works have used
diffusion approximations to study SGD ([2], [3], [6], [21], [18], [12], and
others). Further, [16] was also the first work, to our knowledge, to use
optimal control theory for hyperparameter tuning of SGD, by deriving an
optimal learning rate control for a first-order diffusion approximation with
constant diffusion coefficient. While we focus on batch size control, our work
extends [16] in several aspects: we establish a rigorous theory for
transferring optimal controls from continuous-time theory back to discrete-
time theory; we use the more accurate second-order diffusion approximation; we
specifically allow for state-dependent diffusion coefficients. Further, we
extend the theory in [15] to allow generally for time-dependent drift and
diffusion coefficients, e.g. learning rate and batch size schedules.

##  7 Conclusion

We have developed a continuous-time theory for calculating quasi-optimal
hyperparameter schedules for stochastic gradient descent and similar
stochastic one-step optimization methods, and demonstrated its usefulness by
deriving a quasi-optimal batch size schedule for SGD and a large class of
regression problems. Generalizing these results to allow for Markov controls,
higher dimensions and more general assumptions on the drift and diffusion
coefficients of the diffusion approximations, as well as the development of
practically relevant algorithms, is left to future work.

##  Preliminaries

In this section we introduce notation for the upcoming appendices, as well as
some basic properties.

We write $\mathbb{N}=\\{1,2,\dots\\}$ and $\mathbb{N}_{0}=\\{0,1,\dots\\}$. A
(unordered) _multi-index_ $\alpha$ is a multi-subset of $\\{1,\dots,d\\}$,
i.e. a function $\alpha:\\{1,\dots,d\\}\to\mathbb{N}_{0}$. The size $|\alpha|$
of $\alpha$ is given by

$|\alpha|:=\sum_{j=1}^{d}\alpha(j).$

Every subset $A\subseteq\\{1,\dots,d\\}$ becomes a multi-set by identifying it
with its indicator function. Given multi-indices $\alpha$ and $\beta$ we write
$\alpha\leq\beta$ if $\alpha(j)\leq\beta(j)$ for all $j\in\\{1,\dots,d\\}$ and
in that case the multi-index $\beta-\alpha$ is well defined, by component-wise
subtraction. Further, write $j\in\alpha$ if $\\{j\\}\leq\alpha$ and set
$\alpha-j:=\alpha-\\{j\\}$ in that case.

If a function $f:\mathbb{R}^{d}\to\mathbb{R}$ is $l$-times continuously
differentiable, then by Schwarz’s theorem the partial derivative with respect
to a multi-index $\alpha$ with $|\alpha|\leq l$ is well-defined recursively,
by

$\partial^{\alpha}f=\partial_{j}\partial_{\alpha-j}f,\partial_{\varnothing}f=f.$

where $j$ is any $j\in\\{1,\dots,d\\}$ with $j\in\alpha$. Given
$x\in\mathbb{R}^{d}$ and a multi-index $\alpha$ we define

$x^{\alpha}:=\prod_{j=1}^{d}x_{j}^{\alpha(j)}.$

We denote by $A^{\dagger}$ the transpose of a matrix $A$.

Fix $T>0$, $d\in\mathbb{N}$ and let $B\in\\{\mathbb{R}^{d},\mathbb{R}^{d\times
d}\\}$. Consider a function $g:D\to B$, where $D$ is a subset of Euclidean
space, typically $D\in\\{[0,T],\mathbb{R}^{d},[0,T]\times\mathbb{R}^{d}\\}$.

We write $g\in C^{l}(D)$ if the function $g$ is $l$-times continuously
differentiable on the interior of $D$ and it and its derivatives up to order
$l$ admit a continuous extension to $D$.

Define

$\displaystyle\|g\|_{G_{\kappa}}:=$ $\displaystyle\sup_{x\in
D}\frac{|g(x)|}{1+|x|^{\kappa}},\quad\kappa\in\mathbb{N}_{0},\quad\|g\|_{\operatorname{Lip}}:=\sup_{\stackrel{{\scriptstyle
x,y\in D}}{{x\neq y}}}\frac{|g(x)-g(y)|}{|x-y|}.$

Further, for $g\in C^{l}(D)$ we set

$\displaystyle\|g\|_{G^{l}_{\kappa}}:=$ $\displaystyle\max_{|\alpha|\leq
l}\|\partial^{\alpha}g\|_{G_{\kappa}},\quad\kappa\in\mathbb{N}_{0},\quad\|g\|_{\operatorname{Lip}^{l}}:=\max_{|\alpha|\leq
l}\|\partial^{\alpha}g\|_{\operatorname{Lip}},$

where the maximum is taken over all multi-indices
$\alpha:\\{1,\dots,d\\}\to\mathbb{N}$ with $|\alpha|=l$. Moreover, given that

$\kappa=\inf\\{\kappa\in\mathbb{N}_{0}:\|\partial^{\alpha}g\|_{G_{\kappa}}<\infty,|\alpha|\leq
l\\}\in\mathbb{N}_{0}\cup\\{\infty\\},$

we set $\|g\|_{G^{l}}:=\|g\|_{G_{\kappa}^{l}}$. Note that $\|\cdot\|_{E^{l}}$
is a norm on the vector space $E^{l}=\\{g\in
C^{l}(D):\|g\|_{E^{l}}<\infty\\}$, for
$E\in\\{G_{\kappa},G,\operatorname{Lip}\\}$. We write $G:=G^{0}$.

Now, consider specifically a function $g:[0,T]\times\mathbb{R}^{d}\to B$,
depending on time and space. In this context, we denote time derivatives by
$\partial_{t}$, and iterated space derivatives by $\partial^{\alpha}$, for any
multi-index $\alpha$. We write $g\in C^{k,l}([0,T]\times\mathbb{R}^{d})$ if
$g$ is $k$-times partially differentiable on $(0,T)$ in time, and $l$-times in
space, and $\partial_{t}^{m}\partial^{\alpha}g$ has a continuous extension to
$[0,T]\times\mathbb{R}^{d}$, for all $m\leq k$ and $|\alpha|\leq l$. Further,
we write $g\in G^{k,l}([0,T]\times\mathbb{R}^{d})$ if $g\in
C^{k,l}([0,T]\times\mathbb{R}^{d})$ and $\partial_{t}^{m}\partial^{\alpha}g\in
G([0,T]\times\mathbb{R}^{d})$, for all $m\leq k$ and $|\alpha|\leq l$. Also,we
define

$\|g\|_{\operatorname{Lip}^{\mathbb{T}}}:\mathbb{R}^{d}\to[0,\infty],x\mapsto\|g(x)\|_{\operatorname{Lip}}.$

This special notation is created so that we may write
$\|g\|_{\operatorname{Lip}^{\mathbb{T}}}\in G(\mathbb{R}^{d})$.

Finally, if $I$ is a set and we are given $g:I\times D\to B$ with $g_{i}\in
C^{l}(D)$ for all $i\in I$, then we write

$g_{i}\in E^{l},\text{uniformly in }i\in I,$

if $\sup_{i\in I}\|g_{i}\|_{E^{l}}<\infty$, for
$E\in\\{G_{\kappa},G,\operatorname{Lip}\\}$.

Now, let $X=(X_{t})_{t\geq 0}$ be a continuous-time stochastic process. Given
$p\in[1,\infty)$ we define

$\|X\|_{\operatorname{Lip},p}=\sup_{0\leq s\leq t\leq
T}\frac{\|X_{t}-X_{s}\|_{p}}{t-s},$

provided it exists. Similar to before, we also define
$\|X\|_{\operatorname{Lip}_{p}^{\mathbb{T}}}$ if $X$ depends on
$x\in\mathbb{R}^{d}$ as well. Consider random fields
$X,Y:\Omega\times[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d}$ with
$\|X\|_{\operatorname{Lip}_{p}^{\mathbb{T}}},\|Y\|_{\operatorname{Lip}_{p}^{\mathbb{T}}}\in
G(\mathbb{R}^{d})$. Then also
$\|X+Y\|_{\operatorname{Lip}_{p}^{\mathbb{T}}}\in G(\mathbb{R}^{d})$. Further,
$\|X_{0}\|_{p},\|Y_{0}\|_{p}\in G(\mathbb{R}^{d})$ implies
$\|X_{t}\|_{p},\|Y_{t}\|_{p}\in G(\mathbb{R}^{d})$, uniformly in $t$, and then
$\|XY\|_{\operatorname{Lip}^{\mathbb{T}}_{p}}\in G(\mathbb{R}^{d})$. Similar
statements apply to functions
$f,g:[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d}$. Given $p\in[1,\infty)$ and
$t\geq 0$, we further define

$\|X\|_{p,t}=\left(\mathbb{E}\int_{0}^{t}|X_{s}|^{p}\,ds\right)^{1/p},\quad\|X\|_{*p,t}=\left(\mathbb{E}\sup_{s\in[0,t]}|X_{s}|^{p}\right)^{1/p}$

If we are given $(X_{t})_{t\in[0,T]}$, then we also write
$\|X\|_{p}:=\|X\|_{p,T}$ and $\|X\|_{*p}:=\|X\|_{*p,T}$. Similarly, given
discrete-time stochastic process $\chi$ we define

$\|\chi\|_{*p,n}=\left(\mathbb{E}\max_{n^{\prime}\in\\{0,\dots,n\\}}|\chi_{n^{\prime}}|^{p}\right)^{1/p}.$

In the following we will frequently omit the domain from
$C^{l},G_{\kappa}^{l},G^{l}$ and $\operatorname{Lip}^{l}$. Further, if we
write, say, $g\in G^{3}(\mathbb{R}^{d})$ without explicitly specifying the
codomain of $g$, then it is assumed to be $\mathbb{R}$.

We call a random field

$X:\Omega\times[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d},(\omega,t,x)\mapsto
X_{t}(\omega)(x)$

a solution to a stochastic differential equation

$dX_{t}=b_{t}(X_{t})\,dt+\sigma_{t}(X_{t})\,dW_{t},$

without explicit initial value, if $X(x)$ is a the solution to the stochastic
differential equation

$dX_{t}(x)=b_{t}(X_{t}(x))\,dt+\sigma_{t}(X_{t}(x))\,dW_{t},\quad X_{0}(x)=x,$

for all $x\in\mathbb{R}^{d}$. Similarly, we treat the solution of a recursion

$\chi_{n+1}=\chi_{n}+g_{n}(\chi_{n})$

as a random field $\chi:(\omega,n,x)\mapsto\chi_{n}(\omega)(x)$, with
$\chi_{0}(x)=x$.

##  Expansions in the learning rate

###  .1 Heuristics

We heuristically describe how to derive a series expansion of the form (3.6),
as well as (3.7). Details can be found in in the more general setting of
Subsection .2. Let $T>0$ and

$b^{0},b^{1},S:[0,T]\times\mathbb{R}\to\mathbb{R}$

be measurable functions. We consider the general equation for a second-order
diffusion approximation

$dX_{t}^{h}=(b^{0}_{t}+hb^{1}_{t})(X_{t}^{h})\,dt+\sqrt{h\alpha_{t}}S_{t}(X_{t})\,dW_{t},$
(.1)

with $h\in[0,1)$. We assume that .1 has a unique solution.

Let $g\in C^{2}(\mathbb{R})$. We want to, for now heuristically, determine an
expression for $\mathbb{E}g(X_{t}^{h})$ using the expansion in (3.6),

$X^{h}=X^{0}+\sqrt{h}X^{(1/2)}+hX^{(1)}+h^{3/2}X^{(3/2)}+\mathcal{O}(h^{2}).$

Using a Taylor approximation around the point $X^{0}$, we get

$\displaystyle g(X^{h})=g(X^{0})$
$\displaystyle+g^{\prime}(X^{0})(\sqrt{h}X^{(1/2)}+hX^{(1)}+h^{(3/2)}X^{(3/2)})$
$\displaystyle+\frac{1}{2}g^{\prime\prime}(X^{0})(\sqrt{h}X^{(1/2)}+hX^{(1)}+h^{(3/2)}X^{(3/2)})^{2}$
$\displaystyle+\mathcal{O}(h^{2})$ $\displaystyle=g(X^{0})$
$\displaystyle+\sqrt{h}g^{\prime}(X^{0})X^{(1/2)}$
$\displaystyle+h\left(g^{\prime}(X^{0})X^{(1)}+\frac{1}{2}g^{\prime\prime}(X^{0})(X^{(1/2)})^{2}\right)$
$\displaystyle+h^{3/2}\left(g^{\prime}(X^{0})X^{(3/2)}+g^{\prime\prime}(X^{0})X^{(1/2)}X^{(1)}\right)$
$\displaystyle+\mathcal{O}(h^{2}).$ (.2)

We can apply the same formula to $b^{0},b^{1}$ and $S$. Plugging the result
into (.1), we get

$\displaystyle d(X^{0}+\sqrt{h}X^{(1/2)}+hX^{(1)}+\mathcal{O}(h^{(3/2)}))$
$\displaystyle=$ $\displaystyle b^{0}(X^{0})+\sqrt{h}\partial
b^{0}(X^{0})X^{(1/2)}$
$\displaystyle+h\left(b^{1}{(X^{0})}+\frac{1}{2}\partial^{2}b^{0}(X^{0})(X^{(1/2)})^{2}+\partial
b^{0}(X^{0})X^{(1)}\right)+\mathcal{O}(h^{3/2})\,dt$
$\displaystyle+\sqrt{h\alpha}S(X^{0})+h\sqrt{\alpha}\partial
S(X^{0})X^{(1/2)}+\mathcal{O}(h^{3/2})\,dW,$

where for simplicity we did not consider the $h^{3/2}$-terms. Thus, by
matching powers of $h^{1/2}$ on both sides of the equation, we have

$\displaystyle dX^{0}=$ $\displaystyle b^{0}(X^{0})\,dt,$ $\displaystyle
X_{0}^{(0)}=X_{0},$ $\displaystyle dX^{(1/2)}=$ $\displaystyle\partial
b^{0}(X^{0})X^{(1/2)}\,dt+\sqrt{\alpha}S(X^{0})\,dW,$ $\displaystyle
X^{(1/2)}_{0}=0,$ $\displaystyle dX^{(1)}=$ $\displaystyle
b^{1}(X^{0})+\frac{1}{2}\partial^{2}b^{0}(X^{0})(X^{(1/2)})^{2}+\partial
b^{0}(X^{0})X^{(1)}\,dt$ $\displaystyle+\sqrt{\alpha}\partial
S(X^{0})X^{(1/2)}\,dW,$ $\displaystyle X_{0}^{(1)}=0.$ (.3)

Simplifying further, we heave $\mathbb{E}X^{(1/2)}=0$ because
$\int_{0}^{\cdot}\sqrt{\alpha_{t}}S(X_{T}^{0})\,dW_{t}$ is a martingale. In
similar fashion one can show that the expectation for the omitted component
$X^{(3/2)}$ is zero everywhere. Further, the quadratic covariation of
$X^{(1/2)}$ and $X^{(1)}$ satisfies

$[X^{(1/2)},X^{(1)}]_{t}=\mathbb{E}\int_{0}^{t}\alpha_{s}S(X_{s}^{(0)})\partial
S(X_{s}^{(0)})X^{(1/2)}_{s}\,ds=0,$

and so $\operatorname{Cov}(X^{(1/2)}_{t},X^{(1)}_{t})=0$, for all $t\geq 0$.

Moreover, Itô’s formula implies

$d(X^{(1/2)})^{2}=2\partial b^{0}(X^{0})(X^{(1/2)})^{2}+\alpha
S(X^{0})^{2}\,dt+2X^{(1/2)}\sqrt{\alpha}S(X^{0})\,dW.$ (.4)

Applying expectation to (.1) with the second equation replaced by (.4) yields
the system of ordinary differential equations

$\displaystyle dX_{t}^{0}=$ $\displaystyle b^{0}_{t}(X_{t}^{0})\,dt,$
$\displaystyle X_{0}^{(0)}=X_{0},$ $\displaystyle
d\operatorname{Var}[X_{t}^{(1/2)}]=$ $\displaystyle 2\partial
b^{0}_{t}(X_{t}^{0})\operatorname{Var}[X_{t}^{(1/2)}]+\alpha_{t}(S(X^{0}_{t}))^{2}\,dt,$
$\displaystyle\operatorname{Var}[X_{0}^{(1/2)}]=0,$ $\displaystyle
d\mathbb{E}[X_{t}^{(1)}]=$ $\displaystyle
b^{1}_{t}(X^{0}_{t})+\frac{1}{2}\partial^{2}b^{0}_{t}(X^{0}_{t})\operatorname{Var}[X_{t}^{(1/2)}]$
$\displaystyle+\partial b^{0}_{t}(X^{0}_{t})\mathbb{E}[X^{(1)}_{t}]\,dt,$
$\displaystyle\mathbb{E}[X_{0}^{(1)}]=0.$ (.5)

By applying expectation to (.1) we get

$\displaystyle\mathbb{E}[g(X^{h})]=g(X^{0})$
$\displaystyle+h\left(\frac{1}{2}g^{\prime\prime}(X^{0})\operatorname{Var}[X^{(1/2)}]+g^{\prime}(X^{0})\mathbb{E}[X^{(1)}]\right)$
$\displaystyle+\mathcal{O}(h^{2}),$ (.6)

since
$\mathbb{E}[X^{(1/2)}]=\mathbb{E}[X^{(3/2)}]=\operatorname{Cov}(X^{(1/2)},X^{(1)})=0$
and $X^{0}$ is deterministic. Proposition (.5) in Section .2 shows that our
derivation is indeed rigorous under reasonable conditions on the coefficients
$b^{0},b^{1}$ and $S$.

###  .2 Perturbation theory for stochastic differential equations

We develop a rigorous perturbation theory for stochastic differential
equations depending on a small parameter, to simplify notation in dimension
$d=1$. The results are inspired by [5], but geared more towards our desired
applications.

Let $(\Omega,\mathcal{F}_{\Omega},\mathbb{P})$ be a complete probability
space, $\mathcal{F}=(\mathcal{F}_{t})_{t\geq 0}$ be a filtration on
$(\Omega,\mathcal{F}_{\Omega},\mathbb{P})$, satisfying the usual conditions
and $W$ be a $\mathbb{R}$-valued $\mathcal{F}$-Brownian motion. Consider a
family of stochastic differential equations indexed by a small parameter
$\varepsilon>0$,

$dY_{t}^{\varepsilon}=b^{\varepsilon}_{t}(Y_{t}^{\varepsilon})\,dt+\sigma^{\varepsilon}_{t}(Y_{t}^{\varepsilon})\,dW_{t},$
(.7)

driven by $W$. Our aim is to find random fields
$Y^{(0)},Y^{(1)},Y^{(2)},\dots$, such that

$Y^{\varepsilon}=Y^{(0)}+\varepsilon Y^{(1)}+\varepsilon^{2}Y^{(2)}+\dots$

Suppose we terminate the series at the level $l$, and we are given random
fields

$Y^{(k)}:\Omega\times[0,T]\times\mathbb{R}\to\mathbb{R},(\omega,t,x)\mapsto
Y^{(k)}_{t}(\omega)(x),$

for $k\in\\{0,\dots,l\\}$. We are interested in the remainder term

$R^{\varepsilon}:=\frac{1}{\varepsilon^{l+1}}\left(Y^{\varepsilon}-\sum_{k=0}^{l}Y^{(k)}\varepsilon^{k}\right).$

We write $Y^{(\alpha)}:=\prod_{k=1}^{l}Y^{(\alpha_{k})}$ for every multi-index
$\alpha:\\{0,\dots,l\\}\to\mathbb{N}_{0}$. Note that the multinomial theorem
implies

$\displaystyle\left(\sum_{k=1}^{l}Y_{t}^{(k)}\varepsilon^{k}\right)^{n}=$
$\displaystyle\sum_{\stackrel{{\scriptstyle\alpha_{1},\dots,\alpha_{l}}}{{|\alpha|=n}}}\binom{n}{\alpha}\prod_{k=1}^{l}\varepsilon^{k\alpha_{k}}(Y_{t}^{k})^{\alpha_{k}}$
$\displaystyle=$
$\displaystyle\sum_{\stackrel{{\scriptstyle\alpha_{1},\dots,\alpha_{l}}}{{|\alpha|=n}}}\binom{n}{\alpha}\varepsilon^{\sum_{k=1}^{l}k\alpha_{k}}Y_{t}^{(\alpha)}$
$\displaystyle=$ $\displaystyle\sum_{k=n}^{nl}Y_{t}^{(k,n)}\varepsilon^{k},$

where

$Y^{(k,n)}:=\sum_{\stackrel{{\scriptstyle\alpha_{1},\dots,\alpha_{l}}}{{|\alpha|=n,\sum_{j}j\alpha_{j}=k}}}\binom{n}{\alpha}Y^{(\alpha)},$

for $n,k\in\mathbb{N}_{0}$.

Now, consider a function

$b:(0,1)\times[0,T]\times\mathbb{R}\to\mathbb{R},(\varepsilon,t,y)\mapsto
b^{\varepsilon}_{t}(y),$

with $b_{t}\in C^{l+1}((0,1)\times\mathbb{R})$ for all $t$.

Write

$b^{(k)}:=\frac{1}{k!}(\partial^{k}_{\varepsilon}b^{\varepsilon})_{|\varepsilon=0}$

and

$(b(Y))^{(k)}=\sum_{m+n\leq
k}\frac{1}{n!}\partial_{y}^{n}b^{(m)}(Y^{(0)})Y^{(k-m,n)}.$ (.8)

Note that $(b(Y))^{(k)}$ is the $k$-th coefficient if we expand
$b^{\varepsilon}(Y^{\varepsilon})$, or in fact also
$b^{\varepsilon}(Y^{(0)}+\varepsilon Y^{(1)}+\dots\varepsilon^{l}Y^{(l)})$,
into a power series with respect to $\varepsilon$, for any $k\leq l$.

######  Lemma .1.

Let $b:(0,1)\times[0,T]\times\mathbb{R}\to\mathbb{R}$ be a function with
$b_{t}\in C^{l+1}((0,1)\times\mathbb{R})$ for all $t$. Write

$Z_{n,m}^{\varepsilon}:=\sum_{k=n}^{m}Y^{(k,n)}\varepsilon^{k},\quad n\leq
m\in\mathbb{N}$

Then,

$\displaystyle
b^{\varepsilon}\left(\sum_{k=0}^{l}Y^{(k)}\varepsilon^{k}\right)=$
$\displaystyle\sum_{k=0}^{l}(b(Y))^{(k)}\varepsilon^{k}+\sum_{m+n\leq
l}\frac{1}{n!}\partial_{y}^{n}b^{(m)}(Y^{(0)})(Z_{n,nl}^{\varepsilon}-Z_{n,l}^{\varepsilon})\varepsilon^{m}$
$\displaystyle+\sum_{k=0}^{l+1}\rho_{k}^{\varepsilon}(Y^{(0)}+Z_{1,l}^{\varepsilon})Z_{(l+1)-k,l(l+1)-lk}^{\varepsilon}\varepsilon^{k},$

where

$\rho_{k}^{\varepsilon}(y)=\frac{l+1}{k!((l+1)-k)!}\int_{0}^{1}(1-\xi)^{l}\partial^{k}_{\varepsilon}\partial^{(l+1)-k}_{y}b^{\xi\varepsilon}((1-\xi)Y^{(0)}+\xi
y)\,d\xi.$

###### Proof.

By applying Taylor’s theorem to $b$ at the point $(\varepsilon,Y^{(0)})$, we
have

$\displaystyle b^{\varepsilon}(y)=\sum_{m+n\leq
l}\frac{1}{n!}\partial_{y}^{n}b^{(m)}(Y^{(0)})(y-Y^{(0)})^{n}\varepsilon^{m}+\sum_{k=0}^{l}\rho_{k}^{\varepsilon}(y)(y-Y^{(0)})^{(l+1)-k}\varepsilon^{k},\quad
y\in\mathbb{R},\varepsilon\in(0,1).$

Note that

$(Z_{1,l})^{n}=Z_{n,nl}=Z_{n,l}+Z_{n,nl}-Z_{n,l},$

and further

$\displaystyle\sum_{m+n\leq
l}\frac{1}{n!}\partial_{y}^{n}b^{(m)}(Y^{(0)})Z_{n,l}\varepsilon^{m}=$
$\displaystyle\sum_{m+n\leq
l}\sum_{q=n}^{l}\frac{1}{n!}\partial_{y}^{n}b^{(m)}(Y^{(0)})Y^{(q,n)}\varepsilon^{m+q}$
$\displaystyle=$ $\displaystyle\sum_{k=0}^{l}\sum_{m+n\leq
l}\frac{1}{n!}\partial_{y}^{n}b^{(m)}(Y^{(0)})Y^{(k-m,n)}\varepsilon^{k}$
$\displaystyle=$ $\displaystyle\sum_{k=0}^{l}(b(Y))^{(k)}\varepsilon^{k}$

Thus, setting $y:=\sum_{k=0}^{l}Y^{(k)}\varepsilon^{k}=Y^{(0)}+Z_{1,l}$ shows
the result. ∎

######  Remark .2.

Let us compute $(b(Y))^{(k)}$ for $k=0,1,2,3$. We have

$Y^{(k,1)}=Y^{(k)},Y^{(k,0)}=0,\quad k\in\mathbb{N}_{1}.$

Further,

$Y^{(2,2)}=(Y^{(1)})^{2},Y^{(3,2)}=2Y^{(1)}Y^{(2)},Y^{(3,3)}=(Y^{(1)})^{3}.$

Thus, we can write

$\displaystyle(b(Y))^{(k)}=$ $\displaystyle\sum_{m+n\leq
k}\frac{1}{n!}\partial_{y}^{n}b^{(m)}(Y^{(0)})Y^{(k-m,n)}$ $\displaystyle=$
$\displaystyle
b^{(k)}(Y^{(0)})+\sum_{m=0}^{k-1}\partial_{y}b^{(m)}(Y^{(0)})Y^{(k-m)}+\frac{1}{2}\partial_{y}^{2}b^{(k-2)}(Y^{(0)})(Y^{(1)})^{2}1_{[2,\infty)}(k)$
$\displaystyle+(\partial_{y}^{2}b^{(k-3)}(Y^{(0)})Y^{(1)}Y^{(2)}+\frac{1}{6}\partial_{y}^{3}b^{(k-3)}(Y^{(0)})(Y^{(1)})^{3})1_{[3,\infty)}(k)$
$\displaystyle+\sum_{\stackrel{{\scriptstyle m+n\leq k}}{{m\leq k-4,n\geq
2}}}\frac{1}{n!}\partial_{y}^{n}b^{(m)}(Y^{(0)})Y^{(k-m,n)}1_{[4,\infty)}(k)$

In particular,

$\displaystyle(b(Y))^{(0)}=$ $\displaystyle b^{0}(Y^{(0)}),$
$\displaystyle(b(Y))^{(1)}=$ $\displaystyle
b^{(1)}(Y^{(0)})+\partial_{y}b^{0}(Y^{(0)})Y^{(1)},$
$\displaystyle(b(Y))^{(2)}=$ $\displaystyle
b^{(2)}(Y^{(0)})+\sum_{m=0}^{1}\partial_{y}b^{(m)}(Y^{(0)})Y^{(2-m)}+\frac{1}{2}\partial_{y}^{2}b^{0}(Y^{(0)})(Y^{(1)})^{2},$
$\displaystyle(b(Y))^{(3)}=$ $\displaystyle
b^{(3)}(Y^{(0)})+\sum_{m=0}^{2}\partial_{y}b^{(m)}(Y^{(0)})Y^{(3-m)}+\frac{1}{2}\partial_{y}^{2}b^{(1)}(Y^{(0)})(Y^{(1)})^{2}$
$\displaystyle+\partial_{y}^{2}b^{0}(Y^{(0)})Y^{(1)}Y^{(2)}+\frac{1}{6}\partial_{y}^{3}b^{0}(Y^{(0)})(Y^{(1)})^{3}.$

######  Proposition .3.

Suppose we are given a function
$b:(0,1)\times[0,T]\times\mathbb{R}\to\mathbb{R}$, with $b_{t}\in
G^{l+1}((0,1)\times\mathbb{R})$, uniformly in $t\in[0,T]$, and
$b_{t}^{\varepsilon}\in\operatorname{Lip}(\mathbb{R})$, uniformly in
$t\in[0,T]$ and $\varepsilon\in(0,1)$. Then there exist a multivariate
polynomial $q\in\mathbb{R}[y_{0},\dots,y_{l+1}]$ and a constant $C>0$, such
that

$\frac{1}{\varepsilon^{l+1}}\left|b^{\varepsilon}(Y^{\varepsilon})-\sum_{k=0}^{l}(b(Y))^{(k)}\varepsilon^{k}\right|\leq
q(|Y^{(0)}|,\dots,|Y^{(l)}|,|Y^{\varepsilon}|)+C|R^{\varepsilon}|.$

Further, the coefficients of $q$ and the constant $C$ depend only on, and are
increasing functions of the $\operatorname{Lip}$\- and $G^{l+1}$-norms of $b$.

In this and similar situations, when we refer to, say, the
$\operatorname{Lip}$-norm of $b:I\times\mathbb{R}^{d}\to\mathbb{R}^{d}$ with
$b_{i}\in\operatorname{Lip}$, uniformly in $i\in I$, what we really mean is
$\sup_{i\in I}\|b_{i}\|_{\operatorname{Lip}}$.

###### Proof.

We write

$\displaystyle
b^{\varepsilon}(Y^{\varepsilon})-\sum_{k=0}^{l}(b(Y))^{(k)}\varepsilon^{k}=$
$\displaystyle
b^{\varepsilon}(Y^{\varepsilon})-b^{\varepsilon}\left(\sum_{k=0}^{l}Y^{(k)}\varepsilon^{k}\right)$
$\displaystyle+b^{\varepsilon}\left(\sum_{k=0}^{l}Y^{(k)}\varepsilon^{k}\right)-\sum_{k=0}^{l}(b(Y))^{(k)}\varepsilon^{k}.$

Then,

$\displaystyle\left|b^{\varepsilon}(Y^{\varepsilon})-b^{\varepsilon}\left(\sum_{k=0}^{l}Y^{(k)}\varepsilon^{k}\right)\right|\leq$
$\displaystyle\varepsilon^{l+1}\sup_{\stackrel{{\scriptstyle\varepsilon\in(0,1)}}{{t\in[0,T]}}}\|b^{\varepsilon}_{t}\|_{\operatorname{Lip}}|R^{\varepsilon}|.$

On the other hand, recall Lemma .1. The Taylor remainder satisfies

$|\rho_{k}^{\varepsilon}(y)|\lesssim|\partial_{\varepsilon}^{k}\partial_{y}^{(l+1)-k}b^{\xi\varepsilon}((1-\xi)Y^{(0)}+\xi
y)|\lesssim 1+|Y^{(0)}|^{\kappa}+|Y^{\varepsilon}|^{\kappa},$

for some $\kappa\in\mathbb{N}$. Thus,
$\left|b^{\varepsilon}\left(\sum_{k=0}^{l}Y^{(k)}\varepsilon^{k}\right)-\sum_{k=0}^{l}(b(Y))^{(k)}\varepsilon^{k}\right|$
is bounded above by

$\displaystyle\varepsilon^{l+1}\sum_{m+n\leq
l}\frac{1}{n!}\partial_{y}^{n}b^{(m)}(Y^{(0)})\varepsilon^{-(l+1)}|Z_{n,nl}^{\varepsilon}-Z_{n,l}^{\varepsilon}|$
$\displaystyle+\varepsilon^{l+1}\sum_{k=0}^{l+1}|\rho_{k}^{\varepsilon}(Y^{(0)}+Z_{1,l}^{\varepsilon})||Z_{(l+1)-k,l(l+1)-lk}^{\varepsilon}|\varepsilon^{k-(l+1)},$

where $\varepsilon^{-(l+1)}|Z_{n,nl}^{\varepsilon}-Z_{n,l}^{\varepsilon}|$ and
$|\rho_{k}^{\varepsilon}(Y^{(0)}+Z_{1,l}^{\varepsilon})||Z_{(l+1)-k,l(l+1)-lk}^{\varepsilon}|\varepsilon^{k-(l+1)}$
are bounded by multivariate polynomials in
$|Y^{(0)}|,\dots,|Y^{(k)}|,|Y^{\varepsilon}|$, not depending on $\varepsilon$
(only on $\|b\|_{G^{l}}$). ∎

Note that if $q\in\mathbb{R}[x_{1},\dots,x_{l}]$ is a multivariate polynomial,
i.e. we can write

$q(x)=\sum_{|\alpha|\leq n}q_{\alpha}x^{\alpha},$

and $X_{1},\dots,X_{l}$ are stochastic processes, then by Hölder’s inequality

$\displaystyle\|q(X_{1},\dots,X_{l})\|_{*p}\leq$
$\displaystyle\sum_{|\alpha|\leq n}|q_{\alpha}|\|X^{\alpha}\|_{*p}$
$\displaystyle\leq$ $\displaystyle\sum_{|\alpha|\leq
n}|q_{\alpha}|\prod_{k=1}^{l}\|X_{k}\|_{*p\alpha_{k}l}^{\alpha_{k}}.$

######  Proposition .4.

Let $T>0$ and $l\in\mathbb{N}_{0}$. Suppose we are given functions

$\displaystyle
b:(0,1)\times[0,T]\times\mathbb{R}\to\mathbb{R},(\varepsilon,t,x)\mapsto
b^{\varepsilon}_{t}(x),$
$\displaystyle\sigma:(0,1)\times[0,T]\times\mathbb{R}\to\mathbb{R},(\varepsilon,t,x)\mapsto\sigma^{\varepsilon}_{t}(x)$

such that
$b_{t}^{\varepsilon},\sigma_{t}^{\varepsilon}\in\operatorname{Lip}^{l+1}\cap
G_{1}$, uniformly in $t\in[0,T]$ and $\varepsilon\in(0,1)$. Let $Y$ be a
solution of the family of stochastic differential equations

$dY_{t}^{\varepsilon}=b^{\varepsilon}_{t}(Y_{t}^{\varepsilon})\,dt+\sigma^{\varepsilon}_{t}(Y_{t}^{\varepsilon})\,dW_{t}.$
(.9)

Then for every $k\leq l$, there exist a unique solution $Y^{(k)}$ of

$dY^{(k)}_{t}=(b(Y))_{t}^{(k)}\,dt+(\sigma(Y))_{t}^{(k)}\,dW_{t},\quad
Y^{(k)}_{0}=\begin{cases}Y_{0},&k=0,\\\ 0,&k\in\mathbb{N},\end{cases}$ (.10)

and the solutions satisfy

$\|Y^{(0)}\|_{*p}\in
G_{1}(\mathbb{R}),\quad\|Y^{(k)}\|_{*p}<\infty,k\in\mathbb{N},$

for all $p\geq 2$. Here, $b(Y)^{(k)}$ and $\sigma(Y)^{(k)}$ are given by (.8).
Further,

$\frac{1}{\varepsilon^{l+1}}\|Y^{\varepsilon}-\sum_{k=0}^{l}Y^{(k)}\varepsilon^{k}\|_{*p}\in
G(\mathbb{R}),$

uniformly in $\varepsilon\in(0,1)$, for all $p\geq 2$. Moreover
$\|\|Y^{(0)}\|_{*p}\|_{G}$, $\|Y^{(k)}\|_{*p}$ and
$\sup_{\varepsilon\in(0,1)}\|\|Y^{\varepsilon}-\sum_{k=0}^{l}Y^{(k)}\varepsilon^{k}\|_{*p}\|_{G}$
depend only on, and are increasing functions of the
$\operatorname{Lip}^{l+1}$\- and $G_{1}$-norms of $b$ and $\sigma$, for all
$p\geq 2$.

Note that even though we initially introduced $Y^{(k)}$ for $k>0$ as random
fields, they in fact do not depend on the initial value assigned to $Y$, in
contrast to $Y^{(0)}$.

###### Proof.

We may write $\|Y^{(k)}\|_{*p}\in G_{1}(\mathbb{R})$ in place of
$\|Y^{(k)}\|_{*p}<\infty$, for $k\in\mathbb{N}$. Suppose (.10) has a unique
solution for all $k^{\prime}<k$, such that $\|Y^{(k^{\prime})}\|_{*p}\in
G_{1}(\mathbb{R})$, for all $p\geq 2$. Then we can plug these solutions into
(.10). The coefficients in (.10) are then uniformly linear and Lipschitz in
$Y^{(k)}$. Hence, (.10) has a unique solution, with
$\|Y^{(k^{\prime})}\|_{*p}\in G_{1}(\mathbb{R})$, for all $p\geq 2$.
Similarly, (.7) has a unique solution $Y^{\varepsilon}$, with
$\|Y^{\varepsilon}\|_{*p}\in G_{1}(\mathbb{R})$, for all $p\geq 2$. Now,
consider the remainder term

$R^{\varepsilon}:=\frac{1}{\varepsilon^{l+1}}\left(Y^{\varepsilon}-\sum_{k=0}^{l}Y^{(k)}\varepsilon^{k}\right).$

Then, by using the stochastic differential equation governing
$Y^{\varepsilon}$ and $Y^{(0)},\dots Y^{(l)}$ we have, for all $p\geq 2$ and
$t\in[0,T]$,

$\displaystyle\|R^{\varepsilon}\|_{*p,t}\leq$
$\displaystyle\frac{1}{\varepsilon^{l+1}}\|\int_{0}^{\cdot}b_{s}^{\varepsilon}(Y_{s}^{\varepsilon})-\sum_{k=0}^{l}(b(Y))^{(k)}_{s}\varepsilon^{k}\,ds\|_{*p,t}$
$\displaystyle+\frac{1}{\varepsilon^{l+1}}\|\int_{0}^{\cdot}\sigma_{s}^{\varepsilon}(Y_{s}^{\varepsilon})-\sum_{k=0}^{l}(\sigma(Y))^{(k)}_{s}\varepsilon^{k}\,dW_{s}\|_{*p,t}$
$\displaystyle\lesssim\frac{1}{\varepsilon^{l+1}}\int_{0}^{t}\|b^{\varepsilon}(Y^{\varepsilon})-\sum_{k=0}^{l}(b(Y))^{(k)}\varepsilon^{k}\|_{*p,s}\,ds$
$\displaystyle+\frac{1}{\varepsilon^{l+1}}\int_{0}^{t}\|\sigma^{\varepsilon}(Y^{\varepsilon})-\sum_{k=0}^{l}(\sigma(Y))^{(k)}\varepsilon^{k}\|_{*p,s}\,ds$
$\displaystyle\lesssim\int_{0}^{t}(\|q(|Y^{(0)}|,\dots,|Y^{(l)}|,|Y^{\varepsilon}|)\|_{*p,s}+C\|R^{\varepsilon}\|_{*p,s})\,ds$

for some multivariate polynomial $q$. Then, by Grownall’s inequality

$\|R^{\varepsilon}\|_{*p,t}\leq
C_{1}\|q(|Y^{(0)}|,\dots,|Y^{(l)}|,|Y^{\varepsilon}|)\|_{*p,t}e^{tC_{2}},$

for some constants $C_{1},C_{2}>0$, with

$\|q(|Y^{(0)}|,\dots,|Y^{(l)}|,|Y^{\varepsilon}|)\|_{*p,t}\in G(\mathbb{R}).$

∎

Let us make a few observations about the series expansion of $Y$ according to
.4 in the special case we encounter for second-order diffusion approximations
to stochastic approximations algorithms with a learning rate
$h=\varepsilon^{2}$.

######  Proposition .5.

Suppose we are in the setting of Proposition .4 with $l=3$. Further, we assume

$\sigma^{(0)}=\sigma^{(2)}=b^{(1)}=b^{(3)}=0.$

Then the following statements hold true.

  1. (i)

$Y^{(0)}$ is deterministic and $Y^{(1)}$ is Gaussian,

  2. (ii)

$\mathbb{E}[(Y^{(1)})^{2k+1}]=0$, for all $k\in\mathbb{N}_{0}$,

  3. (iii)

$\mathbb{E}[Y^{(3)}]=0$,

  4. (iv)

$\operatorname{Cov}(Y^{(1)},Y^{(2)})=0$.

Further, the following dynamics hold true

$\displaystyle dY_{t}^{(0)}=$ $\displaystyle b^{(0)}_{t}(Y_{t}^{(0)})\,dt,$
$\displaystyle Y_{0}^{(0)}=Y_{0}$ $\displaystyle
d\operatorname{Var}[Y_{t}^{(1)}]=$ $\displaystyle
2\partial_{y}b^{(0)}_{t}(Y_{t}^{(0)})\operatorname{Var}[Y_{t}^{(1)}]+\sigma^{(1)}_{t}(Y^{(0)}_{t})^{2}\,dt,$
$\displaystyle\operatorname{Var}[Y_{0}^{(1)}]=0,$ $\displaystyle
d\mathbb{E}[Y_{t}^{(2)}]=$ $\displaystyle
b^{(2)}_{t}(Y^{(0)}_{t})+\frac{1}{2}\partial_{y}^{2}b^{(0)}_{t}(Y^{(0)}_{t})\operatorname{Var}[Y_{t}^{(1)}]$
$\displaystyle+\partial_{y}b^{(0)}_{t}(Y^{(0)}_{t})\mathbb{E}[Y^{(2)}_{t}]\,dt,$
$\displaystyle\mathbb{E}[Y_{0}^{(2)}]=0.$ (.11)

###### Proof.

Regarding $Y^{(0)}$: Since $\sigma^{(0)}=0$, the equation governing $Y^{(0)}$
is the ordinary differential equation

$dY^{(0)}_{t}=b^{(0)}_{t}(Y_{t}^{(0)})\,dt,\quad Y^{(0)}_{0}=Y_{0},$

by Remark .2. In particular, $Y^{(0)}$ is deterministic.
Regarding $Y^{(1)}$: Since $b^{(1)}=0$ and again by Remark .2, $Y^{(1)}$
satisfies the linear equation

$dY^{(1)}_{t}=\partial_{y}b^{(0)}_{t}(Y_{t}^{(0)})Y^{(1)}_{t}\,dt+\sigma^{(1)}_{t}(Y^{(0)}_{t})\,dW_{t},$

and the diffusion term does not depend on $Y^{(1)}$. Thus, $Y^{(1)}$ is
Gaussian. Observe that
$\left(\int_{0}^{t}\sigma_{s}^{(1)}(Y_{s}^{(0)})\,dW_{s}\right)_{s\in[0,T]}$
is a martingale. Hence, by the optional stopping theorem

$d\mathbb{E}[Y_{t}^{(1)}]=\partial_{y}b^{(0)}(Y_{t}^{(0)})\mathbb{E}[Y^{(1)}_{t}]\,dt,\quad\mathbb{E}[Y_{0}^{(1)}]=0.$

The unique solution to this ordinary differential equations is
$\mathbb{E}[Y^{(1)}]=0$, which proves (ii) for $k=0$. Assume that (ii) is true
for $k-1\geq 0$. By Itô’s formula, we have

$\displaystyle d(Y^{(1)}_{t})^{k}=$ $\displaystyle
k\partial_{y}b^{(0)}_{t}(Y_{t}^{(0)})(Y^{(1)}_{t})^{k}\,dt$
$\displaystyle+\frac{1}{2}k(k-1)\sigma^{(1)}_{t}(Y^{(0)}_{t})^{2}(Y^{(1)}_{t})^{(k-2)}\,dt$
$\displaystyle+k\sigma^{(1)}_{t}(Y^{(0)}_{t})(Y^{(1)}_{t})^{(k-1)}\,dW_{t}.$

Substituting $k$ with $2k+1$ and taking the expectation yields

$\displaystyle d\mathbb{E}[(Y^{(1)}_{t})^{2k+1}]=$ $\displaystyle
k\partial_{y}b^{(0)}_{t}(Y_{t}^{(0)})\mathbb{E}[(Y^{(1)}_{t})^{2k+1}]\,dt$
$\displaystyle+\frac{1}{2}k(k-1)(\sigma^{(1)}_{t}(Y^{(0)}_{t}))^{2}\mathbb{E}[(Y^{(1)}_{t})^{2k-1}]\,dt$
$\displaystyle+k\mathbb{E}[\sigma^{(1)}_{t}(Y^{(0)}_{t})(Y^{(1)}_{t})^{2k}\,dW_{t}].$

By Hölder’s inequality, we have

$\displaystyle\|\sigma^{(1)}(Y^{(0)})(Y^{(1)})^{2k}\|_{2}$
$\displaystyle\leq\||\sigma^{(1)}(Y^{(0)})||(Y^{(1)})|^{2k}\|_{2}$
$\displaystyle\lesssim\|\sigma^{(1)}(Y^{(0)})\|_{4}\|(Y^{(1)})^{2k}\|_{4}$
$\displaystyle\lesssim(1+\|Y^{(0)}\|_{4})\|Y^{(1)}\|_{8k}^{2k}$
$\displaystyle<\infty.$

Thus,

$\left(\int_{0}^{t}\sigma^{(1)}(Y^{(0)})(Y^{(1)})^{2k}\,dW\right)_{t\in[0,T]}$

is a square-integrable martingale, and by optional stopping as well as
property (ii) for $k^{\prime}<k$,

$\displaystyle d\mathbb{E}[(Y^{(1)}_{t})^{2k+1}]=$ $\displaystyle
k\partial_{y}b^{(0)}_{t}(Y_{t}^{(0)})\mathbb{E}[(Y^{(1)}_{t})^{2k+1}]\,dt,$
$\displaystyle\mathbb{E}[(Y^{(1)}_{0})^{2k+1}]=0.$

Again, the unique solution to this ordinary differential equation is
$\mathbb{E}[(Y^{(1)})^{2k+1}]=0$, proving (ii) for general $k$. The equation
for $\operatorname{Var}[Y^{(1)}]$ in (.5) follows readily.
Regarding $Y^{(2)}$ and (iv): The process $Y^{(2)}$ satisfies the equation

$\displaystyle dY^{(2)}_{t}=$ $\displaystyle
b^{(2)}_{t}(Y^{(0)}_{t})+\partial_{y}b^{0}_{t}(Y^{(0)}_{t})Y^{(2)}_{t}+\frac{1}{2}\partial_{y}^{2}b^{0}_{t}(Y^{(0)}_{t})(Y^{(1)}_{t})^{2}\,dt$
$\displaystyle+\partial_{y}\sigma_{t}^{(1)}(Y^{(0)}_{t})Y^{(1)}_{t}\,dW_{t}.$

Denote by $[X,Y]$ the quadratic covariation of processes $X$ and $Y$. Then

$\displaystyle\mathbb{E}[[Y^{(1)},Y^{(2)}]_{t}]=$
$\displaystyle\int_{0}^{t}\mathbb{E}[\sigma^{(1)}_{s}(Y^{(0)}_{s})\partial_{y}\sigma_{s}^{(1)}(Y^{(0)}_{s})Y^{(1)}_{s}]\,ds$
$\displaystyle=$ $\displaystyle 0,$

by (i) and (ii). Hence, $\operatorname{Cov}(Y^{(1)},Y^{(2)})$ is $0$
everywhere as well.
Regarding $Y^{(3)}$: The process $Y^{(3)}$ satisfies the equation

$\displaystyle dY_{t}^{(3)}=$
$\displaystyle\partial_{y}b^{0}_{t}(Y^{(0)}_{t})Y^{(3)}_{t}+\partial_{y}b^{(2)}_{t}(Y^{(0)}_{t})Y^{(1)}_{t}+\partial_{y}^{2}b^{0}_{t}(Y^{(0)}_{t})Y^{(1)}_{t}Y^{(2)}_{t}+\frac{1}{6}\partial_{y}^{3}b^{0}_{t}(Y^{(0)}_{t})(Y^{(1)}_{t})^{3}\,dt$
$\displaystyle+\sigma^{(3)}_{t}(Y^{(0)}_{t})+\partial_{y}\sigma^{(1)}_{t}(Y^{(0)}_{t})Y^{(2)}_{t}+\frac{1}{2}\partial_{y}^{2}\sigma^{(1)}_{t}(Y^{(0)}_{t})(Y^{(1)}_{t})^{2}\,dW_{t}.$

Because of (ii) and (iv), as well as another optional stopping argument, we
have

$\displaystyle d\mathbb{E}[Y_{t}^{(3)}]=$
$\displaystyle\partial_{y}b^{(0)}_{t}(Y^{(0)}_{t})\mathbb{E}[Y^{(3)}_{t}]\,dt,\mathbb{E}[Y_{0}^{(3)}]=0$

with unique solution $\mathbb{E}[Y^{(3)}]=0$. This proves (iii). ∎

######  Proposition .6.

Suppose we are in the setting of Proposition .5 and we are given a function
$g\in G^{4}(\mathbb{R})$. Set

$\displaystyle Z=$
$\displaystyle\frac{1}{2}\partial_{y}^{2}g(Y^{(0)})(Y^{(1)})^{2}+\partial_{y}g(Y^{(0)})Y^{(2)},$
$\displaystyle V^{\varepsilon}=$
$\displaystyle\varepsilon\partial_{y}g(Y^{(0)})Y^{(1)}+\varepsilon^{3}(g(Y))^{(3)}.$

Then we have $\mathbb{E}[V^{\varepsilon}]=0,\varepsilon\in(0,1)$, and

$\displaystyle
r^{\varepsilon}_{1,p}:=\frac{1}{\varepsilon^{4}}\|g(Y^{\varepsilon})-g(Y^{(0)})-V^{\varepsilon}-\varepsilon^{2}Z\|_{*p}\in
G(\mathbb{R}),$

uniformly in $\varepsilon\in(0,1)$, for all $p\geq 2$. In particular,

$r^{\varepsilon}_{2}:=\frac{1}{\varepsilon^{4}}\left|\mathbb{E}g(Y_{T}^{\varepsilon})-\left(g(Y_{T}^{(0)})+\varepsilon^{2}\left(\frac{1}{2}\partial_{y}^{2}g(Y^{(0)}_{T})\operatorname{Var}[Y^{(1)}_{T}]+\partial_{y}g(Y^{(0)}_{T})\mathbb{E}[Y^{(2)}_{T}]\right)\right)\right|$

is in $G(\mathbb{R})$, uniformly in $\varepsilon\in(0,1)$. Further,
$\sup_{\varepsilon\in(0,1)}\|r^{\varepsilon}_{1,p}\|_{G}$ and
$\sup_{\varepsilon\in(0,1)}\|r^{\varepsilon}_{2}\|_{G}$ depend only on, and
are increasing functions of the $\operatorname{Lip}$\- and $G^{l+1}$-norms of
$b$ and $\sigma$, as well as $\|g\|_{G^{4}}$, for all $p\geq 2$.

###### Proof.

As a special case of Remark .2 we have

$\displaystyle(g(Y))^{(0)}=$ $\displaystyle g(Y^{(0)}),$
$\displaystyle(g(Y))^{(1)}=$ $\displaystyle\partial_{y}g(Y^{(0)})Y^{(1)},$
$\displaystyle(g(Y))^{(2)}=$
$\displaystyle\partial_{y}g(Y^{(0)})Y^{(2)}+\frac{1}{2}\partial_{y}^{2}g(Y^{(0)})(Y^{(1)})^{2},$
$\displaystyle(g(Y))^{(3)}=$
$\displaystyle\partial_{y}g(Y^{(0)})Y^{(3)}+\partial_{y}^{2}g(Y^{(0)})Y^{(1)}Y^{(2)}+\frac{1}{6}\partial_{y}^{3}g(Y^{(0)})(Y^{(1)})^{3}.$

Thus,

$\sum_{k=0}^{3}(g(Y))^{(k)}\varepsilon^{k}=g(Y^{(0)})+V^{\varepsilon}+\varepsilon^{2}Z.$

From Proposition .5 we know that $\mathbb{E}[V^{\varepsilon}]=0$. Propositions
.3 and .4 imply $r_{1,p}^{\varepsilon}\in G(\mathbb{R}),$ uniformly in
$\varepsilon\in(0,1)$, for all $p\geq 2$. Then, it follows readily that
$r_{2}^{\varepsilon}\in G(\mathbb{R})$, uniformly in $\varepsilon\in(0,1)$. ∎

###  .3 Perturbation theory for optimal control of stochastic differential
equations

Proposition .6 ends with a statement on how the polynomial growth constant of
a remainder term $r_{2}^{\varepsilon}$ depends on various norms, each
depending on $b,\sigma$ and $g$. Similar statements can be found throughout
the section. The purpose of these statements is the ability to extend the
approximation result to discuss optimal control problems, in which the
coefficients of (.7) depend on the choice of control. From .6 we can
immediately deduce the following.

######  Corollary .7.

Let $I$ be a set and $T>0$. Suppose we are given functions

$\displaystyle
b:I\times(0,1)\times[0,T]\times\mathbb{R}\times\to\mathbb{R},(i,\varepsilon,t,x)\mapsto
b^{i,\varepsilon}_{t}(x),$
$\displaystyle\sigma:I\times(0,1)\times[0,T]\times\mathbb{R}\to\mathbb{R},(i,\varepsilon,t,x)\mapsto\sigma^{i,\varepsilon}_{t}(x)$

such that
$b_{t}^{i,\varepsilon},\sigma_{t}^{i,\varepsilon}\in\operatorname{Lip}^{4}\cap
G_{1}$, uniformly in $i\in I$, $t\in[0,T]$ and $\varepsilon\in(0,1)$, and

$\sigma^{(0)}=\sigma^{(2)}=b^{(1)}=b^{(3)}=0.$

Let $Y$ be the unique solution of the family of stochastic differential
equations (omitting $i$)

$dY_{t}^{\varepsilon}=b^{\varepsilon}_{t}(Y_{t}^{\varepsilon})\,dt+\sigma^{\varepsilon}_{t}(Y_{t}^{\varepsilon})\,dW_{t},\quad
Y^{(0)}\in\mathbb{R},$ (.12)

and $(Y^{(0)},\operatorname{Var}[Y^{(1)}],\mathbb{E}[Y^{(2)}])$ be the unique
solution of the family of systems of ordinary differential equations

$\displaystyle dY_{t}^{(0)}=$ $\displaystyle b^{(0)}_{t}(Y_{t}^{(0)})\,dt,$
$\displaystyle Y_{0}^{(0)}=Y_{0}$ $\displaystyle
d\operatorname{Var}[Y_{t}^{(1)}]=$ $\displaystyle
2\partial_{y}b^{(0)}_{t}(Y_{t}^{(0)})\operatorname{Var}[Y_{t}^{(1)}]+\sigma^{(1)}_{t}(Y^{(0)}_{t})^{2}\,dt,$
$\displaystyle\operatorname{Var}[Y_{0}^{(1)}]=0,$ $\displaystyle
d\mathbb{E}[Y_{t}^{(2)}]=$ $\displaystyle
b^{(2)}_{t}(Y^{(0)}_{t})+\frac{1}{2}\partial_{y}^{2}b^{(0)}_{t}(Y^{(0)}_{t})\operatorname{Var}[Y_{t}^{(1)}]$
$\displaystyle+\partial_{y}b^{(0)}_{t}(Y^{(0)}_{t})\mathbb{E}[Y^{(2)}_{t}]\,dt,$
$\displaystyle\mathbb{E}[Y_{0}^{(2)}]=0.$ (.13)

Then for every $g\in G^{4}(\mathbb{R})$, there exists a $C\in G(\mathbb{R})$,
with

$\sup_{i\in
I}\left|\mathbb{E}g(Y_{T}^{i,\varepsilon})-\left(g(Y_{T}^{i,(0)})+\varepsilon^{2}\frac{1}{2}\partial_{y}^{2}g(Y^{i,(0)}_{T})\operatorname{Var}[Y^{i,(1)}_{T}]+\partial_{y}g(Y^{i,(0)}_{T})\mathbb{E}[Y^{i,(2)}_{T}]\right)\right|\leq
C\varepsilon^{4}$

for all $\varepsilon\in(0,1)$.

As a consequence of Corollary .7 we may transfer deterministic control
problems between $Y$ and
$(Y^{(0)},\operatorname{Var}[Y^{(1)}],\mathbb{E}[Y^{(2)}])$.

######  Corollary .8.

In the setting of Corollary .7 the following holds true. For every $g\in
G^{4}(\mathbb{R})$, which is bounded from below, there exists a $C\in
G(\mathbb{R})$ with

$\left|\inf_{i\in I}\mathbb{E}g(Y_{T}^{i,\varepsilon})-\inf_{i\in
I}\left(g(Y_{T}^{i,(0)})+\varepsilon^{2}\left(\frac{1}{2}\partial_{y}^{2}g(Y^{i,(0)}_{T})\operatorname{Var}[Y^{i,(1)}_{T}]+\partial_{y}g(Y^{i,(0)}_{T})\mathbb{E}[Y^{i,(2)}_{T}]\right)\right)\right|\leq
C\varepsilon^{4},$

for all $\varepsilon\in(0,1)$.

###### Proof.

Note that for functions $f,g:I\to\mathbb{R}$, bounded from below, we have

$|\inf f-\inf g|\leq\sup|f-g|.$

Hence, the result follows from Corollary .7. ∎

##  Second-order diffusion approximations for SGD

In this section we prove a general second-order approximation result for
stochastic gradient descent and similar algorithms in higher dimensions. Our
approximating equations extends the second-order stochastic modified equation
in [15] by allowing for time-dependent drift and diffusion coefficients, e.g.
learning rate or batch size schedules. Moreover, we formulate all our results
in such a way that we can apply the diffusion approximation to study optimal
control problems (e.g. see the last sentence in Theorem .1).

###  .1 Main result

Let $(\Omega,\mathcal{F}_{\Omega},\mathbb{P})$ be a complete probability
space. Consider a random function

$f:\Omega\times[0,1]\times[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d},(\omega,h,t,x)\mapsto
f_{t}^{h}(\omega)(x),$

such that $(f_{t})_{t\in[0,T]}$ is an independent family. Let
$\mathcal{F}=(\mathcal{F}_{t})_{t\geq 0}$ be a filtration on
$(\Omega,\mathcal{F}_{\Omega},\mathbb{P})$ independent of $f$, satisfying the
usual conditions and $W$ be an $\mathbb{R}^{d}$-valued $\mathcal{F}$-Brownian
motion. We consider a parameter $h\in(0,1)$, which acts as discretization
parameter or maximal learning rate and is essential in describing the
diffusion approximation.

Given an initial value $x\in\mathbb{R}^{d}$ define the stochastic _one-step
method_ with _increment function_ $f$ by

$\chi_{n+1}^{h}=\chi_{n}^{h}+hf_{nh}^{h}(\chi_{n}^{h}),\quad\chi_{0}=x.$ (.1)

Assumption (A3) There exists a random variable $Z$ with with finite moments,
such that

$|f_{t}^{h}(x)|\leq Z(1+|x|),a.s.,$

for all $h\in[0,1],t\in[0,T]$ and $x\in\mathbb{R}^{d}$.

Further, define

$\bar{f}:[0,1]\times[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d},(h,t,x)\mapsto\mathbb{E}f_{t}^{h}(x).$

and

$V:[0,1]\times[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d\times
d},(h,t,x)\mapsto\mathbb{E}[(f_{t}^{h}(x)-\bar{f}_{t}^{h}(x))^{\otimes 2}].$

Here $z^{\otimes 2}=zz^{\dagger}$ for any $z\in\mathbb{R}^{d}$. Since $V$ is
positive semi-definite and symmetric, a unique matrix square root $\sqrt{V}$
exists everywhere. By Assumption (A.1) we have $\bar{f}^{h},\sqrt{V}^{h}\in
G_{1}([0,T]\times\mathbb{R}^{d})$, uniformly in $h$.

Assumption (A4) We have $\bar{f}^{h}_{t}\in\operatorname{Lip}^{4}$ and
$\sqrt{V}^{h}_{t}\in\operatorname{Lip}^{3}$, uniformly in $h$ and $t$, with
$\bar{f}^{h}\in C^{1,4}([0,T]\times\mathbb{R}^{d})$ and $\sqrt{V}^{h}\in
C^{0,3}([0,T]\times\mathbb{R}^{d})$ for all $h$. Further,
$\partial_{t}f^{h}_{t}\in G_{1}\cap\operatorname{Lip}^{3}$, uniformly in $h$
and $t$, and $\|g^{h}\|_{\operatorname{Lip}^{\mathbb{T}}}\in
G(\mathbb{R}^{d})$, uniformly in $h$ , for all
$g\in\\{\bar{f},\nabla\bar{f},\partial_{t}\bar{f},\sqrt{V}\\}$.

The conditions on $\bar{f}$ ensure that the drift coefficient in Equation .2
below satisfies

$\bar{f}_{t}^{h}-\frac{1}{2}h(\nabla\bar{f}_{t}^{h}\bar{f}_{t}^{h}+\partial_{t}\bar{f}_{t}^{h})\in
G_{1}\cap\operatorname{Lip}^{3},$

uniformly in $h$ and $t$.

The relevance of not assuming that $\sqrt{V}$ is differentiable in time is
that for volatility control problems it allows optimal controls which are not
differentiable, which frequently occur by imposing bounds on the controls.

For all $h\in(0,1)$ we consider the family of stochastic differential
equations

$dX_{t}^{h}=\left(\bar{f}_{t}^{h}(X_{t}^{h})-\frac{1}{2}h(\nabla\bar{f}_{t}^{h}\bar{f}_{t}^{h}+\partial_{t}\bar{f}_{t}^{h})(X_{t}^{h})\right)\,dt+\sqrt{hV_{t}^{h}}(X_{t}^{h})\,dW_{t},$
(.2)

where $\nabla g:[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d\times d}$ denotes
the Jacobian of a function $g:[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d}$ in
the space variable, i.e. $(\nabla g)_{i,j}=\partial_{x_{j}}f_{i}$ for all
$i,j\in\\{1,\dots,d\\}$. Crucially, observe the occurrence of the
$\partial_{t}\bar{f}$ term in (.2). It vanishes if $\bar{f}$ is constant in
$t$. Therefore, this term was not present in previous works such as [15]. To
exhibit this term we use an Itô-Taylor approximation for a time-inhomogeneous
SDEs (cf. Proposition .14 and Remark .15).

######  Theorem .1.

Assume (A.1) and (A.1). For all $h\in(0,1)$ let $X^{h}$ be the solution of
(.2). Then for all $g\in G^{3}(\mathbb{R}^{d})$ and $T>0$, there exists a
$C\in G(\mathbb{R}^{d})$, such that

$\max_{n\in\\{0,\dots,\left\lfloor
T/h\right\rfloor\\}}|\mathbb{E}g(\chi_{n}^{h})-\mathbb{E}g(X_{nh}^{h})|\leq
Ch^{2},$

for all $h\in(0,1)$. Further, $\|C\|_{G}$ depends only, and is an increasing
function of $\|g\|_{G}$, $\|Z\|_{\kappa}$ for some large
$\kappa\in\mathbb{N}$, and

  * •

$\sup_{\stackrel{{\scriptstyle
t\in[0,T]}}{{h\in(0,1)}}}\|\bar{f}^{h}_{t}\|_{\operatorname{Lip}^{4}},\sup_{\stackrel{{\scriptstyle
t\in[0,T]}}{{h\in(0,1)}}}\|\sqrt{V}^{h}\|_{\operatorname{Lip}^{3}}$,
$\sup_{\stackrel{{\scriptstyle
t\in[0,T]}}{{h\in(0,1)}}}(\|\partial_{t}\bar{f}^{h}_{t}\|_{\operatorname{Lip}^{3}}+\|\partial_{t}\bar{f}^{h}_{t}\|_{G_{1}})$,

  * •

$\sup_{h\in(0,1)}\|\|\tilde{g}^{h}\|_{\operatorname{Lip}^{\mathbb{T}}}\|_{G}$,
for all
$\tilde{g}\in\\{\bar{f},\nabla\bar{f},\partial_{t}\bar{f},\sqrt{V}\\}$.

The proof of Theorem .1 is postponed to Subsection .5.

###  .2 Diffusion approximations for optimal control

Similar to Subsection .3, Theorem .1 ends with a statement on how the
polynomial growth constant of

$h^{-2}\max_{n\in\\{0,\dots,\left\lfloor
T/h\right\rfloor\\}}|\mathbb{E}g(\chi_{n}^{h})-\mathbb{E}g(X_{nh}^{h})|$

depends on various norms, each depending on $f$ and $g$.

Consider now an index set $I$ and an $I$-indexed family of random functions

$f:\Omega\times
I\times[0,1]\times[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d},(\omega,h,t,x)\mapsto
f_{t}^{i,h}(\omega)(x).$

Suppose every statement in (A.1) and (A.1) holds, _uniformly_ in $i\in I$.
Then we can directly deduce the following.

######  Corollary .2.

For all $h\in(0,1)$ and $i\in I$ let $X^{i,h}$ be the solution of the
stochastic differential equation

$dX_{t}^{i,h}=\left(\bar{f}_{t}^{i,h}(X_{t}^{i,h})-\frac{1}{2}h(\nabla\bar{f}_{t}^{i,h}\bar{f}_{t}^{i,h}+\partial_{t}\bar{f}_{t}^{i,h})(X_{t}^{i,h})\right)\,dt+\sqrt{hV_{t}^{i,h}}(X_{t}^{i,h})\,dW_{t}.$
(.3)

Then for all $g\in G^{3}(\mathbb{R}^{d})$ and $T>0$, there exists a $C\in
G(\mathbb{R}^{d})$, such that

$\sup_{i\in I}\max_{n\in\\{0,\dots,\left\lfloor
T/h\right\rfloor\\}}|\mathbb{E}g(\chi_{n}^{i,h})-\mathbb{E}g(X_{nh}^{i,h})|\leq
Ch^{2},$

for all $h\in(0,1)$.

As a consequence of .2 we may transfer deterministic control problems between
the one-step method $\chi$ and its diffusion approximation.

######  Corollary .3.

For all $h\in(0,1)$ let $X$ be the solution of (.3). Then for all $g\in
G^{3}(\mathbb{R}^{d})$, which are bounded from below, and $T>0$, there exists
a $C\in G(\mathbb{R}^{d})$, such that

$\max_{n\in\\{0,\dots,\left\lfloor T/h\right\rfloor\\}}|\inf_{i\in
I}\mathbb{E}g(\chi_{n}^{i,h})-\inf_{i\in I}\mathbb{E}g(X_{nh}^{i,h})|\leq
Ch^{2},$

for all $h\in(0,1)$.

In the following remark we give simple conditions for SGD, featuring a
learning rate- and a (continuous) batch size schedule, to satisfy (A.1)
_uniformly_ in the choice of schedules.

######  Remark .4.

Let $L>0$ and consider the following index set of pairs consisting of a
learning rate control and a volatility control

$\displaystyle I=$ $\displaystyle\\{u:[0,T]\to[0,1]:u\in
C^{1},\|u\|_{\operatorname{Lip}},\|\partial_{t}u\|_{\operatorname{Lip}}\leq
L\\}$
$\displaystyle\times\\{\alpha:[0,T]\to[0,1]:\|\sqrt{\alpha}\|_{\operatorname{Lip}}\leq
L\\}.$

Suppose there exist functions $H:\mathbb{R}^{d}\to\mathbb{R}^{d}$ and
$S:\mathbb{R}^{d}\to\mathbb{R}^{d\times d}$, such that

$\bar{f}_{t}^{u}(x)=u_{t}H(x),\quad V_{t}^{\alpha}(x)=\alpha_{t}S(x),$

satisfying

$H\in G_{1}\cap\operatorname{Lip}^{4},\sqrt{S}\in
G_{1}\cap\operatorname{Lip}^{3}.$

Then,

$\displaystyle|\partial^{\alpha}\bar{f}_{t}(x)-\partial^{\alpha}\bar{f}_{t}(y)|\leq$
$\displaystyle\|H\|_{\operatorname{Lip}^{4}}|x-y|,\quad|\alpha|\leq 4,$
$\displaystyle|\bar{f}_{t}(x)-\bar{f}_{s}(x)|\leq$ $\displaystyle
L\|H\|_{G_{1}}|t-s|(1+|x|),$
$\displaystyle|\nabla\bar{f}_{t}(x)-\nabla\bar{f}_{s}(x)|\leq$ $\displaystyle
L\|\nabla H\|_{\infty}|t-s|$ $\displaystyle=$ $\displaystyle
L\|H\|_{\operatorname{Lip}}|t-s|,$
$\displaystyle|\partial_{t}\bar{f}_{t}(x)-\partial_{t}\bar{f}_{s}(x)|\leq$
$\displaystyle L\|H\|_{G_{1}}|t-s|(1+|x|),\quad|\alpha|\leq 3,$
$\displaystyle|\partial^{\alpha}\partial_{t}\bar{f}_{t}(x)-\partial^{\alpha}\partial_{t}\bar{f}_{t}(y)|\leq$
$\displaystyle L\|H\|_{\operatorname{Lip}^{3}}|x-y|,\quad|\alpha|\leq 3,$
$\displaystyle|\partial^{\alpha}\sqrt{V_{t}(x)}-\partial^{\alpha}\sqrt{V_{t}(y)}|\leq$
$\displaystyle\|\sqrt{S}\|_{\operatorname{Lip}^{3}}|x-y|,\quad|\alpha|\leq 3,$
$\displaystyle|\sqrt{V_{t}(x)}-\sqrt{V_{s}(x)}|\leq$ $\displaystyle
L\|\sqrt{S}\|_{G_{1}}|t-s|(1+|x|),$

for all $x,y\in\mathbb{R}^{d}$ and $s,t\in[0,T]$. Hence, $\bar{f}$ and
$\sqrt{V}$ satisfy Assumption (A.1), uniformly in $(u,\alpha)\in I$.

###  .3 Results from stochastic analysis

Here we collect minor extensions to well known results from stochastic
analysis to make the proofs of our main results self-contained. We consider
stochastic differential equations with coefficients

$b:[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d},S:[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d\times
d}.$

######  Theorem .5.

Suppose $b_{t},S_{t}\in G_{1}\cap\operatorname{Lip}$, uniformly in $t$. Then,
for every $p\geq 2,T>0$ and random field
$\varphi:\Omega\times[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d}$ with
$\|\varphi\|_{*p}<\infty$, the stochastic differential equation

$dX_{t}=b_{t}(X_{t})\,dt+S_{t}(X_{t})\,dW_{t},\quad X_{0}=\varphi$

admits a unique222Of course, we mean unique up to indistinguishability.
solution $X$ on $[0,T]$, such that the family of solutions $X=(X_{t})_{t\geq
0}$ satisfies

$\|X\|_{*p}\lesssim 1+\|\varphi\|_{*p}.$

The constant factor on the RHS depends only on, and is an increasing function
of the $G_{1}$\- and $\operatorname{Lip}$\- norms of $b$ and $S$.

###### Proof.

This essentially a standard result, cf. [14] Theorem 3.1 and 3.2 for example.
The extension to from an initial value $x\in\mathbb{R}^{d}$ to a process
$\varphi$ is discussed in [15] Theorem 18 and 19. ∎

######  Theorem .6.

Let $l\in\mathbb{N},p\geq 1$ and suppose $b_{t},S_{t}\in
G_{1}\cap\operatorname{Lip}^{l}$, uniformly in $t$. Let
$x\in\mathbb{R}^{d},s\in[0,T]$ and $X$ be the unique solution to the family of
stochastic differential equations

$dX_{t}=b_{t}(X_{t})\,dt+S_{t}(X_{t})\,dW_{t}.$

Then $X$ is $l$-times continuously differentiable w.r.t. to the initial
condition $x$ at any $(t,x)\in[s,T]\times\mathbb{R}^{d}$, a.s. and for every
multi-index $\alpha$ with $0<|\alpha|\leq l$, $\partial^{\alpha}X$ satisfies
the stochastic differential equation

$\partial^{\alpha}X_{t}=\psi_{\alpha}+\int_{s}^{t}\nabla
b_{u}(X_{u})\partial^{\alpha}X_{u}\,du+\int_{s}^{t}\nabla
S_{u}(X_{u})\partial^{\alpha}X_{u}\,dW_{u},$

where $\|\psi_{\alpha}\|_{*p}\in G(\mathbb{R}^{d})$ for all $p\geq 2$.
Moreover,

$\mathbb{E}(\partial^{\alpha}X_{t})=\partial^{\alpha}\mathbb{E}(X_{t}),$

for all $t\geq 0$. Further, $\|\|\psi_{\alpha}\|_{*p}\|_{G}$ depends only on,
and is an increasing function of the $G_{1}$\- and
$\operatorname{Lip}^{l}$-norms of $b$ and $S$.

###### Proof.

For the proof cf. [14] Theorem 3.4. More specifically, for every
$l\in\mathbb{N}$, assuming the result holds for all $l^{\prime}<l$ define

$\displaystyle
Y:=(X,\partial_{1}X,\dots\partial_{d}X,\partial_{1,1}X,\dots,\partial_{1,d}X,\partial_{2,1}X,\dots,\partial_{d,\dots,d}X)^{\dagger},$

where the last partial derivative is of the order $l-1$. Then $Y$ satisfies
the stochastic differential equation

$\displaystyle Y=$ $\displaystyle\begin{pmatrix}x\\\ e_{1}\\\ \vdots\\\
0\end{pmatrix}+\begin{pmatrix}0\\\ \psi_{1}\\\ \vdots\\\
\psi_{d,\dots,d}\end{pmatrix}+\int_{s}^{t}\begin{pmatrix}b_{u}(X_{u})\\\
\nabla b_{u}(X_{u})\partial_{1}X_{u}\\\ \vdots\\\
\nabla^{l-1}b_{u}(X_{u})\partial_{d,\dots,d}X_{u}\end{pmatrix}\,du$
$\displaystyle+\int_{s}^{t}\begin{pmatrix}S_{u}(X_{u})\\\ \nabla
S_{u}(X_{u})\partial_{1}X_{u}\\\ \vdots\\\
\nabla^{l-1}S_{u}(X_{u})\partial_{d,\dots,d}X_{u}\end{pmatrix}\,dW_{u},$

where the processes $\psi_{1},\dots,\psi_{d,\dots,d}$ consists of additional
integrals $\int_{s}^{t}\,du$ and $\int_{s}^{t}\,dW_{u}$ of the remaining terms
induced by repeated application of the chain rule. The terms within
$\int_{s}^{t}\,du$ and $\int_{s}^{t}\,dW_{u}$ respectively are seen to be
functions of $u$ and the state $Y$, satisfying the conditions of [14] Theorem
3.4. By applying it again to the SDE governing $Y$ the result follows via
induction on $l$. ∎

######  Proposition .7.

Let $l\in\mathbb{N},p\geq 1$ and $b_{t},S_{t}\in
G_{1}\cap\operatorname{Lip}^{l}$, uniformly in $t$. Let $X$ be the unique
solution to the family of stochastic differential equations

$dX_{t}^{s}(x)=b_{t}(X_{t}^{s}(x))\,dt+S_{t}(X_{t}^{s}(x))\,dW_{t},\quad
X_{s}^{s}(x)=x.$

and $g:\mathbb{R}^{d}\to\mathbb{R}\in G^{l}(\mathbb{R}^{d})$. Define

$v^{s}_{t}(x):=\mathbb{E}g(X^{s}_{t}(x)),\quad x\in\mathbb{R}^{d}.$

Then $v^{s}_{t}\in G^{l}(\mathbb{R}^{d})$, uniformly in $s$ and $t$. Further,
$\sup_{s\leq t}\|v_{t}^{s}\|_{G^{l}}$ depends only on, and is an increasing
function of the $G_{1}$\- and $\operatorname{Lip}^{l}$-norms of $b$ and $S$,
as well as the $G^{l}$-norm of $g$.

###### Proof.

Let $\alpha$ be a multi-index with $|\alpha|\leq l$. By induction one can show
$\mathbb{E}\partial^{\alpha}g(X)=\partial^{\alpha}\mathbb{E}g(X)$ using
Theorem .6. By the higher chain rule,

$\displaystyle|\partial^{\alpha}v^{s}_{t}|=$
$\displaystyle\mathbb{E}|\partial^{\alpha}g(X_{t}^{s})|\leq\sum_{j=1}^{|\alpha|}\|\nabla^{j}g(X)\|_{*2}\sum_{\mathcal{B}\in\mathcal{S}_{j}^{\alpha}}N(\alpha,\mathcal{B})\prod_{\beta\in\mathcal{B}}\|\partial^{\beta}X\|_{*2\\#\mathcal{B}}.$

Here,

$\|\nabla^{j}g(X)\|_{*2}=\|\sqrt{\sum_{|\beta|\leq
j}|\partial^{\beta}g(X)|^{2}}\|_{*2}.$

Further, $\mathcal{S}_{j}^{\alpha}$ is the set of all partitions of $\alpha$
into $j$ multi-set multi-indices (each partition being a multi-set as well),
$N(\alpha,\mathcal{B})\in\mathbb{N}$, $\\#\mathcal{B}$ is the size of the
partition and the product $\prod_{\beta\in\mathcal{B}}$ respects the
multiplicities of $\beta\in\mathcal{B}$. From $g\in G^{l}(\mathbb{R}^{d})$ and
Theorem .6 we conclude $\partial^{\alpha}v\in G(\mathbb{R}^{d})$. ∎

###  .4 Moment estimates and growth conditions

We collect various moment estimates for SGD-like algorithms and their
approximating SDEs in this section.

####  .4.1 Stochastic Gradient Descent

Recall the definition of $\chi$ in (.1), as well as Assumption (A.1). Denote
the stochastic one-step methods iterations starting at time $n$ with initial
value $x\in\mathbb{R}^{d}$ and parameter $h\in(0,1)$ by $\chi_{n}^{h,n}(x)$.
Given a discrete process $Y$, e.g. $Y=\chi^{h,k}(x)$, we write

$\Delta Y_{n}:=Y_{n+1}-Y_{n}.$ (.4)

We let $\Delta Y_{n}^{h}:=\Delta Y_{n}^{h,0}$. Observe that $\Delta
Y_{n}^{h,n}(x)=Y_{n+1}^{h,n}(x)-x$.

######  Lemma .8.

We have

$\displaystyle\mathbb{E}\Delta\chi_{n}^{h,n}=$ $\displaystyle h\bar{f}_{nh},$
$\displaystyle\mathbb{E}(\Delta\chi_{n}^{h,n})^{\otimes 2}=$ $\displaystyle
h^{2}(V_{nh}+\bar{f}_{nh}^{\otimes 2}).$

###### Proof.

Straightforward. ∎

######  Lemma .9.

Let $p\geq 1$. The following estimates hold true:

  1. (i)

For every $T>0$ there exists a constant $C>0$, such that

$\sup_{h\in(0,1)}\|\chi^{h}(x)\|_{*p,\left\lfloor\frac{T}{h}\right\rfloor}\leq
C(1+|x|),$

for $x\in\mathbb{R}^{d}$, and $C$ depends only on, and is an increasing
function of $\|Z\|_{p}$.

  2. (ii)

We have

$\|\Delta\chi_{n}^{h,i,n}(x)\|_{p}\leq h\|Z\|_{p}(1+|x|),$

for all $h\in(0,1),i\in I,n\in\mathbb{N}$ and $x\in\mathbb{R}^{d}$.

###### Proof.

  1. (i)

Let $p\in\mathbb{N}$. For every $h\in(0,1)$ and $n\in\\{0,\dots,\left\lfloor
T/h\right\rfloor\\}$,

$\|(\chi^{h})\|_{*p,n}=\sup_{i\in
I}\left(\mathbb{E}\max_{n^{\prime}\in\\{-1,\dots,n-1\\}}|\chi_{n^{\prime}+1}^{h,i}|^{p}\right)^{1/p}.$

We have

$\displaystyle|\chi^{h}_{n+1}|^{p}\leq$
$\displaystyle|\chi_{n}^{h}+hf_{nh}^{h}(\chi_{n}^{h})|^{p}$
$\displaystyle\leq$
$\displaystyle|\chi^{h}_{n}|^{p}+\sum_{k=1}^{p}\binom{p}{k}|\chi^{h}_{n}|^{p-k}h^{k}|f_{nh}^{h}(\chi_{n}^{h})|^{k},$

for all $n\in\\{0,\dots,\left\lfloor T/h\right\rfloor\\}$. Now, for
$k\in\\{1,\dots p\\}$, $h\in(0,1)$ and $n\in\\{0,\dots,\left\lfloor
T/h\right\rfloor\\}$,

$\displaystyle\|(|\chi^{h}|^{p-k}|f_{\cdot h}^{h}(\chi^{h})|^{k})\|_{*1,n}$
$\displaystyle\leq\|(|\chi^{h}|^{p-k}Z^{k}(1+|\chi^{h}|)^{k})\|_{*1,n}$
$\displaystyle\leq\mathbb{E}[Z^{k}]\|(|\chi^{h}|^{p-k}+|\chi^{h}|^{k+p-k})\|_{*1,n}$
$\displaystyle\leq 2\mathbb{E}[Z^{k}](1+\|(\chi^{h})\|_{*p,n}^{p})$

using the inequalities $y^{p}+y^{q}\leq 2(1+y^{q})$ for $0<p\leq q$ and $y\geq
0$, as well as Assumption (A.1). Therefore, if we let $\chi_{-1}=0$,

$\displaystyle\|(\chi^{h})\|_{*p,n+1}^{p}\leq$
$\displaystyle\mathbb{E}\max_{n^{\prime}\in\\{-1,\dots,n\\}}|\chi_{n^{\prime}}^{h}|^{p}$
$\displaystyle+\mathbb{E}\max_{n^{\prime}\in\\{-1,\dots,n\\}}\sum_{k=1}^{p}\binom{p}{k}h^{k}|\chi_{n^{\prime}}^{h}|^{p-k}|f_{n^{\prime}h}^{h}(\chi_{n^{\prime}}^{h,i})|^{k}$
$\displaystyle\leq$
$\displaystyle\|(\chi^{h})\|_{*p,n}^{p}+\sum_{k=1}^{p}\binom{p}{k}h^{k}\||\chi^{h}|^{p-k}|f_{\cdot
h}^{h}(\chi^{h})|^{k})\|_{*1,n}$ $\displaystyle\leq$
$\displaystyle\|(\chi^{h})\|_{*p,n}^{p}+Ch(1+\|(\chi^{h})\|_{*p,n}^{p})$
$\displaystyle=$ $\displaystyle(1+Ch)\|(\chi^{h})\|_{*p,n}^{p}+Ch,$

where $C:=\sum_{k=1}^{p}\binom{p}{k}\mathbb{E}[|Z|^{k}]$. By induction over
$n$,

$\|(\chi^{h})\|_{*p,n}^{p}\leq(1+Ch)^{n}\|(\chi^{h})\|_{*p,0}^{p}+Ch\left(\sum_{k=0}^{n-1}(1+Ch)^{k}\right),$

for all $h\in(0,1)$ and $n\in\\{0,\dots,\left\lfloor T/h\right\rfloor\\}$.
Consequently,

$\displaystyle\|\chi^{h}(x)\|_{*p,\left\lfloor\frac{T}{h}\right\rfloor}^{p}$
$\displaystyle\leq(1+Ch)^{\left\lfloor\frac{T}{h}\right\rfloor}|x|^{p}+Ch\sum_{k=0}^{\left\lfloor\frac{T}{h}\right\rfloor}(1+Ch)^{k}$
$\displaystyle\leq(1+Ch)^{\frac{T}{h}}|x|^{p}+Ch\frac{T}{h}(1+Ch)^{\frac{T}{h}}$
$\displaystyle=(CT+|x|^{p})e^{\log(1+Ch)\frac{T}{h}}$
$\displaystyle\leq(CT+|x|^{p})e^{CT},$

for all $h\in(0,T)$ and $x\in\mathbb{R}^{d}$, since $\log(1+y)\leq y$ for all
$y>-1$. Now, the inclusion follows for $p\in\mathbb{N}$. For arbitrary $p\geq
1$ we have $\|Y\|_{*p}\leq\|Y\|_{*\left\lceil p\right\rceil}$ and thus the
result is proven.

  2. (ii)

We have

$\|\Delta\chi_{n}^{h,n}(x)\|_{p}=\|hf_{nh}^{h}(x)\|_{p}\leq
h\|Z\|_{p}(1+|x|),$

for all $h\in(0,1),i\in I$ and $x\in\mathbb{R}^{d}$.

∎

####  .4.2 Diffusion Approximations

We shall now consider moments and growth conditions for solutions of (families
of) stochastic differential equations that will act as approximations to SGD.

Given the family of solutions $X$ to a stochastic differential equation, we
define the family of discrete processes

$\tilde{X}_{n}^{h}(x):=X_{nh}^{h}(x),$ (.5)

with $h\in(0,1),x\in\mathbb{R}^{d}$ and $n\in\\{0,\dots,\left\lfloor
T/h\right\rfloor\\}$. Then,

$\Delta\tilde{X}_{n}^{h,n}(x)=X_{nh}^{h}(x)-x.$

######  Lemma .10.

Let

$b:(0,1)\times[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d},S:[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d\times
d}\in G_{1}(\mathbb{R}^{d})\cap\operatorname{Lip},$

uniformly in $t$ and $h$, and $X$ be the unique solution to the family of
stochastic differential equations

$dX_{t}^{h}=b_{t}^{h}(X_{t}^{h})\,dt+\sqrt{h}S_{t}(X_{t}^{h})\,dW_{t}.$

Then for all $p\geq 2$ there exists a $C\in G(\mathbb{R}^{d})$, such that

$\|\Delta\tilde{X}_{n}^{h,n}\|_{p}\leq hC,$

for all $h\in(0,1)$ and $n\in\\{0,\dots,\left\lfloor T/h\right\rfloor\\}$.
Further, $\|C\|_{G}$ depends only, and is an increasing function of the
$G_{1}$\- and $\operatorname{Lip}$-norms of $b$ and $S$.

###### Proof.

We have

$\|\Delta\tilde{X}_{n}^{h,n}\|_{p}\leq\|\int_{nh}^{(n+1)h}b^{h}_{s}(X_{s}^{h})ds\|_{p}+\sqrt{h}\|\int_{nh}^{(n+1)h}S_{s}(X_{s}^{h})\,dW_{s}\|_{p}.$

On the one hand

$\displaystyle\|\int_{nh}^{(n+1)h}b_{t}^{h}(X_{t}^{h})dt\|_{p}\leq$
$\displaystyle
h^{1-\frac{1}{p}}\left(\int_{nh}^{(n+1)h}\mathbb{E}|b^{h}_{t}(X_{t}^{h})|^{p}\,dt\right)^{1/p}$
$\displaystyle\leq$ $\displaystyle
h\left(\mathbb{E}\sup_{t\in[0,T]}|b_{t}^{h}(X_{t}^{h})|^{p}\right)^{1/p}$
$\displaystyle\leq$ $\displaystyle h\|b^{h}(X^{h})\|_{*p}.$

By Theorem .5, and in particular by the last sentence, we have

$x\mapsto\|b^{h}(X^{h}(x))\|_{*p}\in G(\mathbb{R}^{d}),$

uniformly in $h$. An analogous statement is true for $S$. On the other hand,

$\displaystyle\sqrt{h}\|\int_{nh}^{(n+1)h}S_{t}(X_{t}^{h})\,dW_{t}\|_{p}\leq$
$\displaystyle\sqrt{\frac{p(p-1)}{2}}h^{1-\frac{1}{p}}\|S(X^{h})\|_{p}$
$\displaystyle\leq$ $\displaystyle c_{1}h\|S(X^{h})\|_{*p},$

for some $c_{1}>0$, where we have used Itô’s isometry and Jensen’s inequality.
∎

######  Proposition .11.

Let $l\in\mathbb{N}$, $k\in\\{0,\dots,\left\lfloor T/h\right\rfloor\\}$,

$b:(0,1)\times[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d},S:[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d\times
d}\in G_{1}(\mathbb{R}^{d})\cap\operatorname{Lip}^{l+1},$

uniformly in $h,t$, and let $X$ be the unique solution to the family of
stochastic differential equations

$dX_{t}^{h}=b_{t}^{h}(X_{t}^{h})\,dt+\sqrt{h}S_{t}(X_{t}^{h})\,dW_{t}.$

Suppose further we are given $\kappa\in\mathbb{N}$,

$g:(0,1)\times\mathbb{N}\times\mathbb{R}^{d}\to\mathbb{R},(h,k,x)\mapsto
g^{h}_{k}(x)\in G^{l+1}_{\kappa}(\mathbb{R}^{d}),$

uniformly in $k$ and $h$, and assume there exists a function $C\in
G(\mathbb{R}^{d})$ such that

$\displaystyle|\mathbb{E}(\Delta\chi_{k}^{h,k})^{\alpha}-\mathbb{E}(\Delta\tilde{X}_{k}^{h,k})^{\alpha}|\leq$
$\displaystyle h^{l+1}C,|\alpha|\leq l$
$\displaystyle\|\Delta\chi_{k}^{h,k}\|_{(2l+2)\vee\kappa}^{l+1},\|\Delta\tilde{X}_{k}^{h,k}\|_{(2l+2)\vee\kappa}^{l+1}\leq$
$\displaystyle h^{l+1}C,$

for all $h\in(0,1)$ and $k\in\\{0,\dots,\left\lfloor T/h\right\rfloor\\}$.
Then there exists a function $C^{\prime}\in G(\mathbb{R}^{d})$, such that

$|\mathbb{E}g_{k}^{h}(\chi_{k+1}^{h,k})-\mathbb{E}g_{k}^{h}(\tilde{X}_{k+1}^{h,k})|\leq
h^{l+1}C^{\prime},$

for all $h\in(0,1)$ and $k\in\\{0,\dots,\left\lfloor T/h\right\rfloor\\}$.
Further, $\|C^{\prime}\|_{G}$ depends only on, and is an increasing function
of $\|C\|_{G}$ and $\|g\|_{G^{l+1}}$.

###### Proof.

By Taylor’s theorem there exist
$\theta_{\Delta\chi_{k}^{h,k}},\theta_{\Delta\tilde{X}_{k}^{h,k}}\in(0,1)$ for
every $h\in(0,1)$ and $k$, such that

$\displaystyle g_{k}(\chi_{k+1}^{h,k})-g_{k}(\tilde{X}_{k+1}^{h,k})=$
$\displaystyle
g_{k}(\chi_{k+1}^{h,k})-g_{k}-(g_{k}(\tilde{X}_{k+1}^{h,k})-g_{k})$
$\displaystyle=$ $\displaystyle\sum_{0<|\alpha|\leq
l}\frac{1}{\alpha!}\partial^{\alpha}g_{k}\cdot((\Delta\chi_{k}^{h,k})^{\alpha}-(\Delta\tilde{X}_{k}^{h,k})^{\alpha})$
$\displaystyle+\sum_{|\beta|=l+1}\sum_{D\in\Delta\chi_{k}^{h,k},\Delta\tilde{X}_{k}^{h,k}}\frac{1}{\beta!}\partial^{\beta}g_{k}(\cdot+\theta_{D}D)D^{\beta}$

Since $g_{k}^{h}\in G^{l+1}(\mathbb{R}^{d})$, uniformly in $k$ and $h$, there
exists a $C\in G(\mathbb{R}^{d})$, such that

$\displaystyle|\mathbb{E}[\partial^{\beta}g(x+\theta_{D^{h}}D^{h}(x))D^{h}(x)^{\beta}]|\leq$
$\displaystyle\sup_{\stackrel{{\scriptstyle
h\in(0,1)}}{{t\in[0,T]}}}\|\partial^{\beta}g_{t}^{h}\|_{G_{\kappa}}(1+2^{\kappa-1}|x|^{\kappa}+2^{\kappa-1}\|D^{h}(x)\|_{2\kappa}^{\kappa})$
$\displaystyle\cdot\|D^{h}(x)\|_{2l+2}^{l+1}$ $\displaystyle\lesssim$
$\displaystyle(1+|x|^{\kappa}+C(x))h^{l+1}C(x),$

for $|\beta|=l+1$ and $D\in\Delta\chi,\Delta\tilde{X}$. Therefore,

$\displaystyle|\mathbb{E}g^{h}_{k}(\chi_{k+1}^{h,k}(x))-\mathbb{E}g^{h,i}_{k}(\tilde{X}_{k+1}^{h,k}(x))|\lesssim$
$\displaystyle\sum_{0<|\alpha|\leq l}\sup_{\stackrel{{\scriptstyle
h\in(0,1)}}{{t\in[0,T]}}}\|\partial^{\alpha}g_{t}^{h}\|_{G_{\kappa}}(1+|x|^{\kappa})h^{l+1}C(x)$
$\displaystyle+\sum_{|\beta|=l+1}\sup_{\stackrel{{\scriptstyle
h\in(0,1)}}{{t\in[0,T]}}}\|\partial^{\beta}g_{t}^{h}\|_{G_{\kappa}}(1+|x|^{\kappa}+C(x))h^{l+1}C(x).$

∎

######  Proposition .12.

Let $l\in\mathbb{N}$ and fix a function $g:\mathbb{R}^{d}\to\mathbb{R}\in
G^{l+1}(\mathbb{R}^{d})$. Suppose $X$ is given as in Proposition .11. Further,
let

$g.P_{k,n}^{h}(x):=\int_{\mathbb{R}^{d}}g(y)\,P_{k,n}^{h}(x,dy)=\mathbb{E}g(\tilde{X}_{n}^{h,k}(x)),$

where $P^{h}$ is the transition kernel of $(n,\tilde{X}_{n}^{h})_{n}$. Suppose
there exists a function $C\in G(\mathbb{R}^{d})$, such that

$|\mathbb{E}g.P_{k,n}^{h}(\chi_{k+1}^{h,k})-\mathbb{E}g.P_{k,n}^{h}(\tilde{X}_{k+1}^{h,k})|\leq
h^{l+1}C,$ (.6)

for all $h\in(0,1)$ and $k\in\\{0,\dots,\left\lfloor T/h\right\rfloor\\}$.
Then there exists a function $C^{\prime}\in G(\mathbb{R}^{d})$, such that

$\max_{n\in\\{0,\dots,\left\lfloor
T/h\right\rfloor\\}}|\mathbb{E}g(\chi_{n}^{h})-\mathbb{E}g(\tilde{X}_{n}^{h})|\leq
h^{l}C^{\prime}$

on $\mathbb{R}^{d}$. Further, $\|C^{\prime}\|_{G}$ depends only on, and is an
increasing function of the $G_{1}$\- and $\operatorname{Lip}^{l}$-norms of $b$
and $S$, the $G^{l}$-norm of $g$, the $G_{\kappa}$-norm of $C$, if finite, and
$\|Z\|_{\kappa}$.

###### Proof.

By Proposition .7, and in particular the last sentence, we have

$g.P:(k,n,h,x)\mapsto g.P_{k,n}^{h}(x)\in G^{l+1}(\mathbb{R}^{d}),$

uniformly in $k,n$ and $h$. Given $n\in\\{0,\dots,\left\lfloor
T/h\right\rfloor\\}$, $\mathbb{E}g(\tilde{X}_{n})-\mathbb{E}g(\chi_{n})$
equals

$\displaystyle\sum_{k=1}^{n-1}(\mathbb{E}g(\tilde{X}_{n}^{k-1}\chi_{k-1})-\mathbb{E}g(\tilde{X}_{n}^{k}\chi_{k}))+\mathbb{E}g(\tilde{X}_{n}^{n-1}\chi_{n-1})-\mathbb{E}g(\chi_{n})$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{n-1}\mathbb{E}\mathbb{E}(g(\tilde{X}_{n}^{k}\tilde{X}_{k}^{k-1}\chi_{k-1})|\tilde{X}_{k}^{k-1}\chi_{k-1})-\mathbb{E}\mathbb{E}(g(\tilde{X}_{n}^{k}\chi_{k})|\chi_{k})$
$\displaystyle+\mathbb{E}g.P_{n,n}(\tilde{X}_{n}^{n-1}\chi_{n-1})-\mathbb{E}g.P_{n,n}(\chi_{n})$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{n}(\mathbb{E}g.P_{k,n}(\tilde{X}_{k}^{k-1}\chi_{k-1})-\mathbb{E}g.P_{k,n}(\chi_{k})),$

Hence, (.6) and Lemma .9 imply

$\displaystyle|\mathbb{E}g(\tilde{X}_{n}^{h})-\mathbb{E}g(\chi_{n}^{h})|\leq$
$\displaystyle\sum_{k=1}^{\left\lfloor\frac{T}{h}\right\rfloor}h^{l+1}\mathbb{E}C(\chi_{k-1}^{h})\leq
h^{l}TC^{\prime},$

for some $C^{\prime}\in G(\mathbb{R}^{d})$, all $h\in(0,1)$ and
$n\in\\{0,\dots,\left\lfloor T/h\right\rfloor\\}$, since

$\displaystyle\mathbb{E}C(\chi_{k-1}^{h})\leq$
$\displaystyle\|C\|_{G_{\kappa}}(1+\mathbb{E}|\chi_{k-1}^{h}|^{\kappa})\leq\|C\|_{G_{\kappa}}\left(1+\sup_{h\in(0,1)}\|\chi\|_{*\kappa,\left\lfloor
T/h\right\rfloor}^{\kappa}\right)$ $\displaystyle\lesssim$ $\displaystyle
1+|\chi_{0}|^{\kappa},$

for some $\kappa\in\mathbb{N}$, all $h\in(0,1)$ and
$k\in\\{0,\dots,\left\lfloor T/h\right\rfloor\\}$. ∎

###  .5 Proof of the second-order diffusion approximation

The next lemma gives a Lipschitz-in-time-like condition for a family of
processes $(f_{t}(X_{t}(x)))_{t\in[0,T],x\in\mathbb{R}^{d}}$, where $X$ is the
solution of an SDE with Lipschitz coefficients of, say, linear growth.

######  Lemma .13.

Let $p\geq 2$ and $X:\Omega\times[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d}$
be a random field with $\|X\|_{\operatorname{Lip}_{p}^{\mathbb{T}}}\in
G(\mathbb{R}^{d})$ and $\|X_{t}\|_{p}\in G(\mathbb{R}^{d})$, uniformly in $t$.
Further, let $f:[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d}$ be a function,
with $\|f\|_{\operatorname{Lip}^{\mathbb{T}}}\in G(\mathbb{R}^{d})$ and
$f_{t}\in\operatorname{Lip}(\mathbb{R}^{d})$, uniformly in $t$. Then
$\|f(X)\|_{\operatorname{Lip}_{p}^{\mathbb{T}}}\in G(\mathbb{R}^{d})$.

###### Proof.

Let $C:=\|f\|_{\operatorname{Lip}^{\mathbb{T}}}$. We have

$\displaystyle\|f_{t}(X_{t})-f_{s}(X_{s})\|_{p}\leq$
$\displaystyle\|f_{t}(X_{t})-f_{s}(X_{t})\|_{p}+\|f_{s}(X_{t})-f_{s}(X_{s})\|_{p}$
$\displaystyle\leq$
$\displaystyle\|C(X_{t})\|_{p}(t-s)+\|f_{s}\|_{\operatorname{Lip}}\|X_{t}-X_{s}\|_{p}$
$\displaystyle\lesssim$ $\displaystyle(t-s)(1+|x|^{\kappa}),\quad 0\leq s\leq
t\leq T,$

for some $\kappa>0$. ∎

Given $u,v\in\mathbb{R}^{d}$ and $A,B\in\mathbb{R}^{d\times d}$ we write

$\langle u,v\rangle:=\sum_{j=1}^{d}u_{j}v_{j},\quad\langle
A,B\rangle:=\sum_{i,j=1}^{d}A_{i,j}B_{i,j}$

in the following.

######  Proposition .14.

Let

$b^{0},b^{1}:[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d},\sigma:[0,T]\times\mathbb{R}^{d}\to\mathbb{R}^{d\times
d}$

be in $\operatorname{Lip}(\mathbb{R}^{d})$ and $G_{1}(\mathbb{R}^{d})$,
uniformly in time. Further, assume $b^{0}\in
G^{1,2}([0,T]\times\mathbb{R}^{d})$ and $b^{1},\sigma\in
G^{0,1}([0,T]\times\mathbb{R}^{d})$, such that
$\|\partial_{t}b^{0}\|_{\operatorname{Lip}^{\mathbb{T}}},\|b^{1}\|_{\operatorname{Lip}^{\mathbb{T}}},\|\sigma\|_{\operatorname{Lip}^{\mathbb{T}}}\in
G(\mathbb{R}^{d})$. Let $n\in\\{0,\dots,\left\lfloor T/h\right\rfloor-1\\}$
and $X=(X_{t}(x))_{t\in[nh,(n+1)h],x\in\mathbb{R}^{d}}$ be the solution to the
family of stochastic differential equations

$dX_{t}(x)=b_{t}^{0}(X_{t}(x))+hb_{t}^{1}(X_{t}(x))\,dt+\sqrt{h}\sigma_{t}(X_{t}(x))\,dW_{t},\quad
X_{nh}(x)=x,$ (.7)

with $t\in[nh,(n+1)h]$, and $g\in G^{3}(\mathbb{R}^{d})$. Then,

$\displaystyle\mathbb{E}g(X_{(n+1)h})=g+$ $\displaystyle h\langle\nabla
g,b^{0}_{nh}\rangle+\frac{h^{2}}{2}(\langle\nabla g,\nabla
b^{0}_{nh}b^{0}_{nh}+2b^{1}_{nh}+\partial_{t}b^{0}_{nh}\rangle)$
$\displaystyle+$
$\displaystyle\frac{h^{2}}{2}\langle\nabla^{2}g,\sigma_{nh}^{\dagger}\sigma_{nh}+(b^{0}_{nh})^{\otimes
2}\rangle+h^{3}C$

for all $h\in(0,1)$, for some $C\in G(\mathbb{R}^{d})$. The function $C$ only
depends on, and is an increasing function of

  * •

$\sup_{t\in[0,T]}\|b^{0}_{t}\|_{\operatorname{Lip}},\sup_{t\in[0,T]}\|b^{1}_{t}\|_{\operatorname{Lip}},\sup_{t\in[0,T]}\|\sigma_{t}\|_{\operatorname{Lip}}$,

  * •

$\|\partial_{t}b^{0}\|_{\operatorname{Lip}^{\mathbb{T}}},\|b^{1}\|_{\operatorname{Lip}^{\mathbb{T}}},\|\sigma\|_{\operatorname{Lip}^{\mathbb{T}}}$,

  * •

$\|\partial_{t}^{k}\partial^{\alpha}b^{0}\|_{G},k=0,1,|\alpha|\leq 2$;
$\|\partial^{\alpha}b^{1}\|_{G},\|\partial^{\alpha}\sigma\|_{G},|\alpha|\leq
1$,

and $\|g\|_{G^{3}}$.

###### Proof.

Itô’s formula implies

$\displaystyle g(X_{(n+1)h})=g(X_{nh})$
$\displaystyle+\int_{nh}^{(n+1)h}\langle\nabla
g(X_{u}),b^{0}_{u}(X_{u})\rangle+h\langle\nabla
g(X_{u}),b_{u}^{1}(X_{u})\rangle\,du$
$\displaystyle+\frac{h}{2}\int_{nh}^{(n+1)h}\langle\nabla^{2}g(X_{u}),(\sigma_{u}^{\dagger}\sigma_{u})(X_{u})\rangle\,du+R_{1},$

where

$R_{1}:=\int_{nh}^{(n+1)h}\langle\nabla
g(X_{u}),\sigma_{u}(X_{u})\rangle\,dW_{u}.$

Note that $\mathbb{E}[R_{1}]=0$, by Hölder’s inequality, polynomial growth and
optional stopping. Using Einstein’s summation convention, a further
application of Itô’s formula yields that

$\int_{nh}^{(n+1)h}\langle\nabla
g(X_{u}),b^{0}_{u}(X_{u})\rangle\,du=\int_{nh}^{(n+1)h}\partial_{i}g(X_{u})b^{0}_{u}(X_{u})^{i}\,du$

equals

$\displaystyle\int_{nh}^{(n+1)h}\langle\nabla
g(X_{nh}),b^{0}_{nh}(X_{nh})\rangle\,du$
$\displaystyle+\int_{nh}^{(n+1)h}\int_{nh}^{u}\langle\nabla
g(X_{v}),\partial_{t}b^{0}_{v}(X_{v})\rangle\,dv\,du$
$\displaystyle+\int_{nh}^{(n+1)h}\int_{nh}^{u}(\partial_{ij}g(X_{v})b^{0}_{v}(X_{v})^{i}+\partial_{i}g(X_{u})\partial_{j}b^{0}_{v}(X_{v})^{i})(b^{0}_{v}(X_{v}))^{j}\,dv\,du$
$\displaystyle+h\int_{nh}^{(n+1)h}\int_{nh}^{u}(\partial_{ij}g(X_{v})b^{0}_{v}(X_{v})^{i}+\partial_{i}g(X_{u})\partial_{j}b^{0}_{v}(X_{v})^{i})(b^{1}_{v}(X_{v}))^{j}\,dv\,du$
$\displaystyle+\frac{h}{2}\int_{nh}^{(n+1)h}\int_{nh}^{u}\partial_{jk}(\partial_{i}g(X_{u})b^{0}_{u}(X_{u})^{i})(\sigma_{u}^{\dagger}\sigma_{u})(X_{v})^{jk}\,dv\,du$
$\displaystyle+\int_{nh}^{(n+1)h}\int_{nh}^{u}(\partial_{ij}g(X_{v})b^{0}_{v}(X_{v})^{i}+\partial_{i}g(X_{u})\partial_{j}b^{0}_{v}(X_{v})^{i})\sigma_{v}(X_{v})_{k}^{j}\,dW_{v}^{k}\,du.$

Note that

$(\partial_{ij}gb^{0}_{v}(X_{v})^{i}+\partial_{i}g(X_{u})\partial_{j}b^{0}_{v}(X_{v})^{i})(b^{0}_{v}(X_{v}))^{j}=\langle\nabla^{2}g,b^{0}_{v}(X_{v})^{\otimes
2}\rangle+\langle\nabla g,(\nabla b^{0}_{v}b^{0}_{v})(X_{v})\rangle.$

By Lemma .13, we have

$\displaystyle\|\langle\nabla g(X),(\nabla
b^{0}b^{0})(X)+\partial_{t}b^{0}(X)\rangle+\langle\nabla^{2}g,b^{0}(X)^{\otimes
2}\rangle\|_{\operatorname{Lip}^{\mathbb{T}}_{p}}\in G(\mathbb{R}^{d}).$

Further, setting

$\displaystyle Z:=$ $\displaystyle
h\int_{nh}^{(n+1)h}\int_{nh}^{u}(\partial_{ij}g(X_{v})b^{0}_{v}(X_{v})^{i}+\partial_{i}g(X_{u})\partial_{j}b^{0}_{v}(X_{v})^{i})(b^{1}_{v}(X_{v}))^{j}\,dv\,du$
$\displaystyle+\frac{h}{2}\int_{nh}^{(n+1)h}\int_{nh}^{u}\partial_{jk}(\partial_{i}g(X_{u})b^{0}_{u}(X_{u})^{i})(\sigma_{u}^{\dagger}\sigma_{u})(X_{v})^{jk}\,dv\,du$
$\displaystyle+\int_{nh}^{(n+1)h}\int_{nh}^{u}(\partial_{ij}g(X_{v})b^{0}_{v}(X_{v})^{i}+\partial_{i}g(X_{u})\partial_{j}b^{0}_{v}(X_{v})^{i})\sigma_{v}(X_{v})_{k}^{j}\,dW_{v}^{k}\,du,$

we have

$\|Z(x)\|_{p}\leq h^{3}C^{\prime}(x)$

for some $C^{\prime}\in G(\mathbb{R}^{d})$. To summarize,

$\displaystyle\mathbb{E}\int_{nh}^{(n+1)h}\langle\nabla
g(X_{u}),b^{0}_{u}(X_{u})\rangle\,du=$ $\displaystyle h\langle\nabla
g(X_{nh}),b^{0}_{nh}\rangle$ $\displaystyle+\frac{h^{2}}{2}(\langle\nabla
g,\nabla
b^{0}_{nh}b^{0}_{nh}+\partial_{t}b^{0}_{nh}\rangle+\langle\nabla^{2}g,(b^{0}_{nh})^{\otimes
2}\rangle)$ $\displaystyle+h^{3}C,$

for some $C\in G(\mathbb{R}^{d})$ and all $h\in(0,1)$. Similarly,

$\displaystyle h\mathbb{E}\int_{nh}^{(n+1)h}\langle\nabla
g(X_{u}),b_{u}^{1}(X_{u})\rangle=$ $\displaystyle h^{2}\langle\nabla
g,b_{nh}^{1}\rangle+h^{3}C^{\prime},$
$\displaystyle\frac{h}{2}\mathbb{E}\int_{nh}^{(n+1)h}\langle\nabla^{2}g(X_{u}),(\sigma_{u}^{\dagger}\sigma_{u})(X_{u})\rangle\,du=$
$\displaystyle\frac{h^{2}}{2}\langle\nabla^{2}g,\sigma_{nh}^{\dagger}\sigma_{nh}\rangle+h^{3}C^{\prime}$

for some $C^{\prime}\in G$. In total, we get

$\displaystyle\mathbb{E}g(X_{(n+1)h})=g+$ $\displaystyle h\langle\nabla
g,b^{0}_{nh}\rangle+\frac{h^{2}}{2}(\langle\nabla g,\nabla
b^{0}_{nh}b^{0}_{nh}+2b^{1}_{nh}+\partial_{t}b^{0}_{nh}\rangle)$
$\displaystyle+$
$\displaystyle\frac{h^{2}}{2}\langle\nabla^{2}g,\sigma_{nh}^{\dagger}\sigma_{nh}+(b^{0}_{nh})^{\otimes
2}\rangle+h^{3}C$

for all $h\in(0,1)$, for some $C\in G(\mathbb{R}^{d})$. ∎

######  Remark .15.

Consider the setting of Proposition .14. First, set

$g(z):=(z-x)_{l},l\in\\{1,\dots,d\\}.$

Then $g(x)=0,\nabla g(x)_{j}=\delta_{j,l},\nabla^{2}g(x)=0$ and for any
$v\in\mathbb{R}^{d}$,

$\langle\delta_{\cdot,l},v\rangle=v_{l}.$

Recall, $\Delta\tilde{X}_{n}^{h,n}(x)=X_{(n+1)h}^{nh}(x)-x$. By applying
Proposition .14 for all $l\in\\{1,\dots,d\\}$, we get

$\mathbb{E}[\Delta\tilde{X}_{n}^{h,n}]=hb^{0}_{nh}+\frac{h^{2}}{2}(\nabla
b^{0}_{nh}b^{0}_{nh}+2b^{1}_{nh}+\partial_{t}b^{0}_{nh})+h^{3}C,$

for all $h\in(0,1)$ and some $C\in G$. Similarly, consider now

$g(z):=(z-x)_{k}(z-x)_{l},\quad k,l\in\\{1,\dots,d\\}.$

Then

$g(x)=0,\nabla
g(x)=0,\nabla^{2}g(x)_{i,j}=\delta_{i,k}\delta_{j,l}+\delta_{i,l}\delta_{j,k},$

and for any $A\in\mathbb{R}^{d\times d}$,

$\langle\nabla^{2}g(x),A\rangle=A_{k,l}+A_{l,k}.$

Thus,

$\mathbb{E}[(\Delta\tilde{X}_{n}^{h,n})^{\otimes
2}]=h^{2}(\sigma^{\dagger}_{nh}\sigma_{nh}+(b_{nh}^{0})^{\otimes 2})+h^{3}C,$

for all $h\in(0,1)$ and some $C\in G$.

Recalling Lemma .8, we have

$\displaystyle\mathbb{E}\Delta\chi_{k}^{h}-\mathbb{E}\Delta\tilde{X}_{n}^{h,n}=$
$\displaystyle h(\bar{f}_{nh}-b^{0}_{nh})+\frac{1}{2}h^{2}(2b^{1}_{nh}+(\nabla
b^{0}b^{0})_{nh}+\partial_{t}b^{0}_{nh})+h^{3}C,$
$\displaystyle\mathbb{E}(\Delta\chi_{k}^{h})^{\otimes
2}-\mathbb{E}(\Delta\tilde{X}_{n}^{h,n})^{\otimes 2}=$ $\displaystyle
h^{2}(V-\sigma^{\dagger}\sigma+\bar{f}^{\otimes 2}-(b^{0})^{\otimes
2})_{nh}+h^{3}C.$

This tell us how to choose the coefficients $b^{0},b^{1}$ and $\sigma$, such
that all terms, except $h^{3}C$, vanish. We set

$b^{0}:=\bar{f},\quad
b^{1}:=-\frac{1}{2}\left(\nabla\bar{f}\bar{f}+\partial_{t}\bar{f}\right),\quad\sigma:=\sqrt{V}.$

Note that assumptions (A.1) and (A.1) are enough to satisfy the assumptions of
Proposition .14 for all $h\in(0,1)$ and $n\in\\{0,\dots,\left\lfloor
T/h\right\rfloor\\}$.

We are finally ready to prove Theorem .1.

###### Proof of Theorem .1.

By Remark .15

$|\mathbb{E}(\Delta\chi_{n}^{h,n})^{\alpha}-\mathbb{E}(\Delta\tilde{X}_{n}^{h,n})^{\alpha}|\leq
h^{3}C,$

for $|\alpha|\leq 2$, and by Lemma .9 and .10

$\|\Delta\chi_{n}^{h,n}\|_{p}^{3}\vee\|\Delta X_{n}^{h,n}\|_{p}^{3}\leq
h^{3}C$

for all $n\in\\{0,\dots,\left\lfloor T/h\right\rfloor\\},h\in(0,1),p\geq 2$
and some $C\in G(\mathbb{R}^{d})$. Denote by $P^{h}$. the transition kernel of
$(n,X^{h}_{nh})_{n\in\\{0,\dots,\left\lfloor T/h\right\rfloor\\}}$ Given any
$g\in G^{3}(\mathbb{R}^{d})$, by applying Proposition .11 to
$\tilde{g}_{n}^{h}:=g.P_{k,n}^{h}$, we have

$\left|\mathbb{E}g.P_{k,n}^{h}(\chi_{k+1}^{h,k})-\mathbb{E}g.P_{k,n}^{h}(X_{(k+1)h}^{h,kh})\right|\leq
h^{3}C$

for some $C\in G(\mathbb{R}^{d})$, for all $k\leq n$. Since $\|C\|_{G}$ is an
increasing function of the norms of the coefficients of $X$, as well as
$\|Z\|_{\kappa}$, for some large $\kappa$, we can choose $C$ independent of
$k$. Then, by Proposition .12 together with Lemma .9 and Proposition .7,

$\displaystyle\max_{n\in\\{0,\dots,\left\lfloor
T/h\right\rfloor\\}}|\mathbb{E}g(X_{nh}^{h})-\mathbb{E}g(\chi_{n}^{h})|\leq$
$\displaystyle h^{2}C$

for some $C\in G(\mathbb{R}^{d})$ and all $h\in(0,1)$. ∎

##  Optimal volatility control

In this section we derive and optimal volatility control for generic equations
of the form (.1). We make use of the Pontryagin maximum principle to solve the
optimal batch size control problem (cf. [19] Chapter 6.4 for more details).

Recall again equation (.1)

$dX_{t}^{h}=(b^{0}_{t}+hb^{1}_{t})(X_{t}^{h})\,dt+\sqrt{h\alpha_{t}}S_{t}(X_{t}^{h})\,dW_{t}.$

We make the following assumption on the coefficients of .1.

Assumption (A5) We have $b^{0}_{t},b^{1}_{t},S_{t}\in
G_{1}\cap\operatorname{Lip}^{4}\text{uniformly in }t$, $S(x)\in C^{1}([0,T])$
for all $x\in\mathbb{R}$, and $S>0$ everywhere. Further, the volatility
control $\alpha$ is Lipschitz continuous.

Assumption (A) ensures that Equation (.1) has a unique solution $X^{h}$ for
all $h\in(0,1)$. Consider an objective function $g:\mathbb{R}\to(0,\infty)$.

Assumption (A6) We have $g\in C^{2}$ with $g^{\prime\prime}(X_{T}^{0})>0$ and

$g(x)\lesssim 1+|x|^{2},x\in\mathbb{R}.$

Note again that the gradient flow $X^{0}$ does not depend on the batch size.
Thus, based on(.1) and (.1), we consider the objective

$\operatorname*{\operatorname{argmin}}_{\alpha\in
A(L)}\frac{1}{2}g^{\prime\prime}(X_{T}^{0})\operatorname{Var}[X^{(1/2),\alpha}_{T}]+g^{\prime}(X_{T}^{0})\mathbb{E}[X_{T}^{(1),\alpha}]+\lambda\int_{0}^{T}\frac{1}{\alpha_{t}}\,dt,$
(.1)

where

$\displaystyle d\operatorname{Var}[X^{(1/2),\alpha}_{t}]=$ $\displaystyle
2B_{t}^{1}\operatorname{Var}[X^{(1/2),\alpha}_{t}]+\alpha_{t}\sigma_{t}^{2}\,dt,$
(.2) $\displaystyle d\mathbb{E}[X_{t}^{(1),\alpha}]=$
$\displaystyle\frac{1}{2}B_{t}^{2}\operatorname{Var}[X^{(1/2),\alpha}_{t}]+B_{t}^{1}\mathbb{E}[X_{t}^{(1),\alpha}]+b^{1}_{t}(X_{t}^{0})\,dt,$
(.3)

with $\sigma_{t}:=S_{t}(X_{t}^{0})$ and
$B^{k}_{t}=\partial_{x}^{k}b^{0}(X^{0}_{t})$. Equivalently, setting

$\displaystyle\mu^{\alpha}=$
$\displaystyle\begin{pmatrix}\operatorname{Var}[X^{(1/2),\alpha}]\\\
\mathbb{E}[X^{(1),\alpha}]\end{pmatrix},A=\begin{pmatrix}2B^{1}&0\\\
\frac{1}{2}B^{2}&B^{1}\end{pmatrix},\beta(a)=\begin{pmatrix}a\sigma^{2}\\\
b^{1}(X^{0})\end{pmatrix},$

we have

$d\mu_{t}^{\alpha}=A_{t}\mu_{t}^{\alpha}+\beta_{t}(\alpha_{t})\,dt,$

and then the cost at the terminal time $T$ is $\mu\mapsto G^{\dagger}\mu$,
where

$G=\begin{pmatrix}\frac{1}{2}g^{\prime\prime}(X_{T}^{0})\\\
g^{\prime}(X_{T}^{0})\end{pmatrix}.$

The Hamiltonian for the control problem is given by

$\mathcal{H}(t,m,y,a)=m^{\dagger}A^{\dagger}_{t}y+\beta_{t}(a)^{\dagger}y+\frac{\lambda}{a}.$

We have

$0=\partial_{a}\mathcal{H}(t,m,y,a)=\sigma_{t}^{2}y_{1}-\lambda\frac{1}{a^{2}}.$

if and only, if

$a=\sqrt{\frac{\lambda}{y_{1}\sigma_{t}^{2}}},$

assuming $y_{1}>0$. Hence,

$\operatorname*{\operatorname{argmin}}_{a\in[0,1]}\mathcal{H}(t,\mu,y,a)=\sqrt{\frac{\lambda}{y_{1}\sigma_{t}^{2}}}\wedge
1.$ (.4)

Further,

$\nabla_{m}\mathcal{H}(t,m,y,a)=A_{t}^{\dagger}y$

and so the backward equation is given (in forward form) by

$dY_{t}=A_{t}^{\dagger}Y_{t}\,dt,\quad Y_{T}=G$ (.5)

Hence, its solution is

$Y_{t}=\exp\left(-\int_{t}^{T}A_{s}^{\dagger}\,ds\right)G.$

Note, that the matrix exponential of any upper triangular $2\times 2$-matrix
satisfies

$\exp\begin{pmatrix}a&b\\\ 0&d\end{pmatrix}=\begin{pmatrix}e^{a}&b\eta\\\
0&e^{d}\end{pmatrix},$

with

$\eta=\begin{cases}\frac{e^{a}-e^{d}}{a-d},&a\neq d,\\\
e^{a},&a=d\end{cases}.$

Therefore,

$\displaystyle Y_{t}=$
$\displaystyle\begin{pmatrix}e^{-2\beta_{t,T}^{1}}&-\frac{1}{2}\beta_{t,T}^{2}\eta_{t,T}\\\
0&e^{-\beta_{t,T}^{1}}\end{pmatrix}G=\begin{pmatrix}\frac{1}{2}e^{-2\beta_{t,T}^{1}}g^{\prime\prime}(X_{T}^{0})-\frac{1}{2}\beta_{t,T}^{2}\eta_{t,T}g^{\prime}(X_{T}^{0})\\\
e^{-\beta_{t,T}^{1}}g^{\prime}(X_{T}^{0})\end{pmatrix},$ (.6)

where

$\beta^{k}_{t,T}=\int_{t}^{T}B_{s}^{k}\,ds,$

and

$\displaystyle\eta_{t,T}:=$
$\displaystyle\begin{cases}\frac{e^{-2\beta_{t,T}^{1}}-e^{-\beta_{t,T}^{1}}}{-2\beta_{t,T}^{1}+\beta_{t,T}^{1}},&e^{-2\beta_{t,T}^{1}}\neq
e^{-\beta_{t,T}^{1}}.\\\
e^{-2\beta_{t,T}^{1}},&e^{-2\beta_{t,T}^{1}}=e^{-\beta_{t,T}^{1}}.\end{cases}$
$\displaystyle=$
$\displaystyle\begin{cases}\frac{e^{-\beta_{t,T}^{1}}-e^{-2\beta_{t,T}^{1}}}{\beta_{t,T}^{1}},&\beta_{t,T}^{1}\neq
0,\\\ 1,&\beta_{t,T}^{1}=0.\end{cases}$

Thus, the optimal control is given by

$\alpha_{t}^{*}=\sqrt{\frac{2\lambda}{\delta_{t,T}\sigma_{t}^{2}}}\wedge 1,$
(.7)

where

$\delta_{t,T}=e^{-2\beta_{t,T}^{1}}g^{\prime\prime}(X^{0}_{T})-\beta_{t,T}^{2}\eta_{t,T}g^{\prime}(X_{T}^{0}).$

Let

$J(t,\mu,\alpha)=\frac{1}{2}g^{\prime\prime}(X_{T}^{0})\operatorname{Var}_{t}^{\mu_{1}}[X^{(1/2)}_{T}]+g^{\prime}(X_{T}^{0})\mathbb{E}_{t}^{\mu_{2}}[X_{T}^{(1)}]+\lambda\int_{0}^{T}\frac{1}{\alpha_{t}}\,dt,$

where

$\operatorname{Var}_{t}^{\mu_{1}}[X^{(1/2)}_{T}]=\operatorname{Var}[X^{(1/2)}_{T}|X^{(1/2)}_{t}=\mu_{1}],$

and similarly for $\mathbb{E}_{t}^{\mu_{1}}[X^{(1)}_{T}]$. Consider the _value
function_ of the optimal control problem

$V(t,\mu)=\inf_{\alpha\in A(L)}J(t,\mu,\alpha).$

######  Proposition .1.

Assume (A) and (A). Then $\delta_{\cdot,T}$ is positive everywhere,
$\alpha^{*}$ is Lipschitz continuous and the optimal control for the objective
(.1).

###### Proof.

Given an initial time $t\in[0,T]$ and initial value $x\in\mathbb{R}$, the
solution to the linear ordinary differential equation (.2) is given by

$\operatorname{Var}[X_{T}^{(1/2),t}(x)]=xe^{2\beta^{1}_{t,T}}+\int_{t}^{T}e^{2\beta^{1}_{t,s}}\sigma_{s}^{2}\alpha_{s}\,ds,\quad
x\in\mathbb{R},t\leq T.$

Further, consider the solution $Y$ to the the backward equation (.5) and let

$\tau_{\varepsilon}=0\vee\sup\\{t\in[0,T]:(Y_{t})_{1}<\varepsilon\\}$

for any $\varepsilon>0$. Since $Y$ is continuous and
$(Y_{T})_{1}=\frac{1}{2}g^{\prime\prime}(X_{T}^{0})>0$ by Assumption (A), we
have $\tau_{\varepsilon}<T$ for all
$\varepsilon<\frac{1}{2}g^{\prime\prime}(X_{T}^{0})$. Note that $Y$ does not
depend on $\mu$ and so neither does $\tau_{\varepsilon}$.

Our goal now is to apply Theorem 6.4.6 in [19] on the interval
$[\tau_{\varepsilon},T]$ and conclude that $\alpha^{*}$ given in (.7) is an
optimal control on $[\tau_{\varepsilon},T]$. The candidate $\alpha^{*}$
minimizes the Hamiltonian according to (.4). It remains to show that given
$t\in[\tau_{\varepsilon},T]$ the map

$\mathbb{R}^{2}\times[0,1]\to\mathbb{R},(\mu,a)\mapsto\mathcal{H}(t,\mu,Y_{t},a)$

is convex. Indeed, this map is in $C^{2}(\mathbb{R}^{2}\times(0,1))$ with
Hessian

$\begin{pmatrix}0&0&0\\\ 0&0&0\\\ 0&0&2\lambda a^{-3}\end{pmatrix},$

which is positive semidefinite. Thus, $\alpha^{*}$ is optimal on
$[\tau_{\varepsilon},T]$.

Note that $X^{0}\in C^{1}([0,T])$ and $\partial
b^{0},\partial^{2}b^{0},g^{\prime},g^{\prime\prime}\in
C(\mathbb{R}),\sigma^{2}\in C^{1}([0,T])$. Hence, by the fundamental theorem
of calculus $\beta^{k}_{\cdot,T}\in C^{1}([0,T])$ for $k\in=1,2$, and so
$\alpha^{*}$ is Lipschitz continuous.

$(t,\mu)\mapsto\operatorname{Var}[X_{T}^{(1/2),t,\alpha^{*}}(\mu_{1})]$

is in $C^{1,3}([0,T]\times\mathbb{R})$. Similarly we can show

$(t,\mu)\mapsto\mathbb{E}[X_{T}^{(1),t,\alpha^{*}}(\mu_{2})]\in
C^{1,3}([0,T]\times\mathbb{R})$

and $\int_{\cdot}^{T}(\alpha^{*})^{-1}_{s}\,ds\in C^{1}([0,T])$. Hence,

$V=J(\cdot,\cdot,\alpha^{*})\in
C^{1,3}([\tau_{\varepsilon},T]\times\mathbb{R}^{2}).$

By Theorem 6.4.7 in [19] we can conclude that the solution of the backward
equation (.5) satisfies

$Y_{t}=\nabla_{\mu}V(t,\mu),t\in[\tau_{\varepsilon},T].$

Let us show $\partial_{\mu_{1}}V(t,\mu)$ is bounded away from zero. With
$e_{1}=\begin{pmatrix}1&0\end{pmatrix}^{\dagger}$, we have

$\displaystyle\frac{J(t,\mu+\delta e_{1},\alpha)-J(t,\mu,\alpha)}{\delta}=$
$\displaystyle\frac{1}{2}g^{\prime\prime}(X_{T}^{0})e^{2\beta^{1}_{t,T}}.$

Therefore,

$\displaystyle\partial_{\mu_{1}}V(t,\mu)=$ $\displaystyle\lim_{\delta\to
0}\frac{\inf_{\alpha\in A}J(t,\mu+\delta e_{1},\alpha)-\inf_{\alpha\in
A}J(t,\mu,\alpha)}{\delta}$ $\displaystyle\geq$ $\displaystyle\lim_{\delta\to
0}\frac{\inf_{\alpha\in A}(J(t,\mu+\delta
e_{1},\alpha)-J(t,\mu,\alpha))}{\delta}$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}g^{\prime\prime}(X_{T}^{0})e^{2\beta^{1}_{t,T}}$
$\displaystyle>$ $\displaystyle 0.$

Set
$\varepsilon=\frac{1}{4}g^{\prime\prime}(X_{T}^{0})\min_{t\in[0,T]}e^{2\beta_{t,T}^{1}}>0$.
If $\tau_{\varepsilon}>0$, then

$0<\partial_{\mu_{1}}V(t,\mu)=(Y_{\tau_{\varepsilon}})_{1}<\varepsilon\leq\frac{1}{2}\partial_{\mu_{1}}V(t,\mu),$

which is a contradiction. Hence $\tau_{\varepsilon}=0$. Therefore
$(Y_{\cdot})_{1}=\delta_{\cdot,T}$ is positive everywhere and $\alpha^{*}$ is
the optimal control on $[0,T]$. ∎

##  Proof of the main result

Using the our previous insights into the continuous-time theory of mini-batch
SGD we can finally prove our main result.

###### Proof of Theorem 2.1.

Firstly, Assumption (A2) implies global unique existence of continuous
solutions to (2.1) and the following family of stochastic differential
equations

$dX_{t}^{h}=-\mathcal{R}^{\prime}(X_{t}^{h})-\frac{h}{2}\mathcal{R}^{\prime\prime}(X_{t}^{h})\mathcal{R}^{\prime}(X_{t}^{h})\,dt+\sqrt{h\alpha_{t}\Sigma(X_{t}^{h})}\,dW_{t}.$
(.1)

Setting $g:=\mathcal{R}$, $\sigma_{t}:=\Sigma(X_{t}^{0})$,
$b^{0}=-\mathcal{R}^{\prime}$ and
$b^{1}=-\frac{1}{2}\mathcal{R}^{\prime\prime}\mathcal{R}^{\prime}$ we see that
it implies Assumptions (A) and (A). By Proposition .1, the solution to the
Langrage dual to problem (3.10) with Lagrange multiplier $\lambda>0$ is given
by $\alpha^{*}(\lambda)$. Note that by Assumption (A2), $\delta_{t,T}$ and
$\Sigma(X_{t}^{0})$ are continuous in $t$. Thus, $\alpha^{*}$ is bounded on
$[0,T]$ from below, away from $0$. Hence, the dominated convergence theorem
implies that

$C:(0,\infty)\to\mathbb{R},\lambda\mapsto\int_{0}^{T}\frac{1}{\alpha_{t}^{*}(\lambda)}\,dt$

is continuous. We have

$\lim_{\lambda\to
0}C(\lambda)=\infty,\quad\lim_{\lambda\to\infty}C(\lambda)=T.$

Hence, there exists a $\lambda>0$ with $C(\lambda)=c$, as $c\geq T$, and then
$\alpha^{*}(\lambda)$ is the optimum in (3.10). By Corollary .8 with
$\varepsilon=\sqrt{h}$ we can transfer the optimal control from the series
expansion $X^{0}+\sqrt{h}X^{(1/2)}+hX^{(1)}+h^{3/2}X^{(3/2)}$ back to the
solution of (.1), and so there exists a constant $C>0$, depending on the
initial value of $X$, with

$\min_{\alpha\in
A(L)}\mathbb{E}\mathcal{R}(X_{T}^{h,\alpha})=\mathbb{E}\mathcal{R}(X_{T}^{h,\alpha^{*}})+Ch^{2}$
(.2)

Now, Assumptions (A2) and (A2) ensure that (A.1) and (A.1) are fulfilled,
uniformly in $\alpha\in A(L)$ (cf. also Remark .4). Thus, we can approximate
(1.5) by the second-order diffusion approximation (.1). In particular, Theorem
.1, Corollary .3 and (.2) imply there exist constants $C_{1},C_{2},C_{3}>0$,
depending on the shared initial value of $\chi$ and $X$, with

$\displaystyle\min_{\alpha\in
A(L)}\mathbb{E}\mathcal{R}(\chi^{h,\alpha}_{\left\lfloor T/h\right\rfloor})=$
$\displaystyle\min_{\alpha\in
A(L)}\mathbb{E}\mathcal{R}(X_{T}^{h,\alpha})+C_{1}h^{2}$ $\displaystyle=$
$\displaystyle\mathbb{E}\mathcal{R}(X_{T}^{h,\alpha^{*}})+C_{2}h^{2}$
$\displaystyle=$
$\displaystyle\mathbb{E}\mathcal{R}(\chi^{h,\alpha^{*}}_{\left\lfloor
T/h\right\rfloor})+C_{3}h^{2},$

for all $h\in(0,1)$. ∎

##  Properties of the optimal volatility control for linear regression

Recall the optimal volatility control (4.1) in the case of linear regression
with SGD.

###  .1 Lipschitz constant

We want to determine an upper bound on the Lipschitz constant of
$\sqrt{\alpha^{*}}$. Set $s_{t}:=\gamma+e^{2\kappa t}$. Note that $\alpha^{*}$
is differentiable almost everywhere, with

$\displaystyle\partial_{t}\sqrt{\alpha^{*}_{t}}=-\frac{\kappa}{2\lambda}e^{2\kappa
t}(\alpha_{t}^{*})^{5/2},$

for $t>\check{t}$, and $\partial_{t}\sqrt{\alpha^{*}_{t}}=0$ for
$t\in[0,\check{t})$. Hence, we can get a bound on the the Lipschitz constant
of $\sqrt{\alpha^{*}}$,

$\displaystyle\|\sqrt{\alpha^{*}}\|_{\operatorname{Lip}}\leq$
$\displaystyle\frac{\kappa}{2\lambda}e^{2\kappa T}.$

Thus, in Theorem 2.1 we may pick any $L\geq\frac{\kappa}{2\lambda}e^{2\kappa
T}$.

###  .2 Determining the Lagrange multiplier

We have

$\displaystyle\int_{0}^{T}\frac{1}{\alpha^{*}_{t}(\lambda)}\,dt=$
$\displaystyle\int_{0}^{\check{t}(\lambda)}1\,dt+\lambda^{-1/2}\int_{\check{t}(\lambda)}^{T}\sqrt{\gamma+e^{2\kappa
t}}\,dt$ $\displaystyle=$
$\displaystyle\check{t}(\lambda)+\lambda^{-1/2}(F(T)-F(\check{t}(\lambda))),$

where

$F(t):=\frac{1}{\kappa}\left(\sqrt{\gamma+e^{2\kappa
t}}-\sqrt{\gamma}\operatorname{ArcTanh}\left(\frac{\sqrt{\gamma+e^{2\kappa
t}}}{\sqrt{\gamma}}\right)\right).$

We can apply Newton’s method to find a zero of
$\lambda\mapsto\check{t}(\lambda)+\lambda^{-1/2}(F(T)-F(\check{t}(\lambda)))-c$.
Alternatively, if $\lambda\leq\gamma+1$, then

$\displaystyle c=\int_{0}^{T}\frac{1}{\alpha^{*}_{t}(\lambda)}\,dt$
$\displaystyle\Leftrightarrow\lambda=\frac{(F(T)-F(0))^{2}}{c^{2}}.$

##  Setup of the numerical experiment

One run of the experiment proceeds as follows. First, we generate $N$
artificial data points according to the linear model

$\bm{y}=-\bm{x}+\bm{\varepsilon},$

where $\bm{x},\beta\sim\mathcal{N}(0,1)$ and $\bm{x},\beta$ are independent.
We fix a number of SGD steps $M$, such that $N$ is divisible by $M$. Then we
use mini batch SGD to fit a linear predictor using square loss in a single
epoch, with two different batch size schedules. The first schedule has
constant batch size, more precisely

$B_{n}^{c}:=N/M.$

With the second schedule, the batch size in the $n$-th step is given by

$B_{n}^{o}=\operatorname{round}(1/\alpha^{*}_{nh}(\lambda)).$

Here, $\alpha^{*}$ is the optimal volatility schedule in (4.1). Using binary
search we determine $\lambda$, such that

$\sum_{n=1}^{M}B_{n}^{o}=N.$

Both schedules are used $1000$ times for training, yielding instances
$\hat{\chi}^{1,c},\dots,\hat{\chi}^{1000,c}$ with constant batch size and
$\hat{\chi}^{1,o},\dots,\hat{\chi}^{1000,o}$ with “optimal” batch sizes. Then,
we calculate the average excess population risk

$r^{s}:n\mapsto\frac{1}{1000}\sum_{i=1}^{1000}(\mathcal{R}(\hat{\chi}_{n}^{i,s})-\mathcal{R}^{*}),$

for $s=c,o$. Then, we re-scale time to track the number of samples processed,
rather than the number of steps. That is, we plot

$\left(\sum_{n=0}^{\nu}B_{n}^{s},r^{s}(\nu)\right),\nu=0,1,\dots,M,$

for $s=c,o$. Additionally, we superimpose the plot of the sequence of
“optimal” batch sizes, in the same time scale

$\left(\sum_{n=0}^{\nu}B_{n}^{o},B_{\nu}\right),\nu=0,1,\dots,M.$

## References

  * [1] B. Acciaio, J. B. Veraguas, and A. Zalashko.  Causal optimal transport and its links to enlargement of filtrations and continuous-time stochastic optimization, Dec. 2017.  arXiv:1611.02610 [math].
  * [2] A. Ali, E. Dobriban, and R. Tibshirani.  The Implicit Regularization of Stochastic Gradient Flow for Least Squares.  In Proceedings of the 37th International Conference on Machine Learning, pages 233–244. PMLR, Nov. 2020.  ISSN: 2640-3498.
  * [3] J. An, J. Lu, and L. Ying.  Stochastic modified equations for the asynchronous stochastic gradient descent.  Information and Inference: A Journal of the IMA, 9(4):851–873, Dec. 2020.
  * [4] L. Balles, J. Romero, and P. Hennig.  Coupling Adaptive Batch Sizes with Learning Rates, June 2017\.  arXiv:1612.05086 [cs, stat].
  * [5] Y. N. Blagoveshchenskii.  Diffusion Processes Depending on a Small Parameter.  Theory of Probability & Its Applications, 7(2):130–146, Jan. 1962\.  Publisher: Society for Industrial and Applied Mathematics.
  * [6] N. M. Boffi and J.-J. E. Slotine.  A continuous-time analysis of distributed stochastic gradient.  Neural Computation, 32(1):36–96, Jan. 2020.  arXiv:1812.10995 [cs, math].
  * [7] L. Bottou, F. E. Curtis, and J. Nocedal.  Optimization Methods for Large-Scale Machine Learning, Feb. 2018\.  arXiv:1606.04838 [cs, math, stat].
  * [8] R. H. Byrd, G. M. Chin, J. Nocedal, and Y. Wu.  Sample size selection in optimization methods for machine learning.  Mathematical Programming, 134(1):127–155, Aug. 2012.
  * [9] S. De, A. Yadav, D. Jacobs, and T. Goldstein.  Automated Inference with Adaptive Batches.  In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pages 1504–1513. PMLR, Apr. 2017\.  ISSN: 2640-3498.
  * [10] M. P. Friedlander and M. Schmidt.  Hybrid Deterministic-Stochastic Methods for Data Fitting.  SIAM Journal on Scientific Computing, 34(3):A1380–A1405, Jan. 2012\.  arXiv:1104.2373 [cs, math, stat].
  * [11] B. Gess, S. Kassing, and V. Konarovskyi.  Stochastic Modified Flows, Mean-Field Limits and Dynamics of Stochastic Gradient Descent, Feb. 2023.  arXiv:2302.07125 [cs, math, stat].
  * [12] H. Gu and X. Guo.  An SDE Framework for Adversarial Training, with Convergence and Robustness Analysis, May 2021.  arXiv:2105.08037 [cs, math].
  * [13] S. Ji, S. Peng, Y. Peng, and X. Zhang.  Three Algorithms for Solving High-Dimensional Fully Coupled FBSDEs Through Deep Learning.  IEEE Intelligent Systems, 35(3):71–84, May 2020.  Conference Name: IEEE Intelligent Systems.
  * [14] H. Kunita.  Stochastic differential equations based on levy processes and stochastic flows of diffeomorphisms.  In Real and Stochastic Analysis : New Perspectives. Birkhäuser Boston, Boston, MA, 2004.
  * [15] Q. Li and C. Tai.  Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms I: Mathematical Foundations.  Journal of Machine Learning Research, 20, Mar. 2019.
  * [16] Q. Li, C. Tai, and W. E.  Stochastic Modified Equations and Adaptive Stochastic Gradient Algorithms.  In Proceedings of the 34th International Conference on Machine Learning, pages 2101–2110. PMLR, July 2017.  ISSN: 2640-3498.
  * [17] S. Mandt, M. D. Ho, and D. M. Blei.  Continuous-Time Limit of Stochastic Gradient Descent Revisited.  2015\.
  * [18] S. Pesme, L. Pillaud-Vivien, and N. Flammarion.  Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity.  In Advances in Neural Information Processing Systems, volume 34, pages 29218–29230. Curran Associates, Inc., 2021.
  * [19] H. Pham.  Continuous-time stochastic control and optimization with financial applications, volume 61.  Springer Science & Business Media, 2009.
  * [20] S. L. Smith, P.-J. Kindermans, C. Ying, and Q. V. Le.  Don’t Decay the Learning Rate, Increase the Batch Size, Feb. 2018.  arXiv:1711.00489 [cs, stat].
  * [21] Z. Xie, I. Sato, and M. Sugiyama.  A Diffusion Theory For Deep Learning Dynamics: Stochastic Gradient Descent Exponentially Favors Flat Minima, Jan. 2021.  arXiv:2002.03495 [cs, stat].
  * [22] J. Zhao, A. Lucchi, F. N. Proske, A. Orvieto, and H. Kersting.  Batch size selection by stochastic optimal control.  In Has it Trained Yet? NeurIPS 2022 Workshop, 2022.