Rectified deep neural networks overcome the curse of dimensionality for nonsmooth value functions in zero-sum games of nonlinear stiff systems

Introduction

In this paper, we study the expressive power of deep artificial neural networks (DNNs), and demonstrate that one can construct DNNs with polynomial complexity to approximate nonsmooth value functions associated with stiff stochastic differential equations (SDEs).

The above problem is called a zero-sum stochastic differential game since the underlying SDE (1.1) is controlled by two players with opposite objectives, i.e., the “inf-player” aims to minimize the associated cost function over all strategies $u_{1}\in\mathcal{U}_{1,d}$, while the “sup-player” aims to maximize the same cost function over all strategies $u_{2}\in\mathcal{U}_{2,d}$. The admissible controls $\mathcal{U}_{i,d}$, $i=1,2$, are called open-loop controls since they are deterministic processes; see page 23 of for different types of strategies. In the case with $\sigma_{d}\equiv 0$, (1.1) degenerates to a controlled ordinary differential equation. Moreover, if one of the sets $\mathcal{U}_{1,d}$ and $\mathcal{U}_{2,d}$ is singleton, the zero-sum game reduces to an optimal control problem.

admits a solution $y$ under the following strong monotonicity condition In general, the coefficients $U$ and $G$ need to satisfy other technical assumptions, such as continuity, coercivity and growth conditions, to ensure the well-posedness of (1.2) in $L^{2}(\Omega\times[0,T];V)$; see e.g. . However, since we only use (1.2) to motivate the high-dimensional stiff SDE (1.5) and shall establish approximation results for the corresponding high-dimensional value functions, we omit other technical assumptions on the coefficients $U$ and $G$ here and introduce the precise conditions for the finite-dimensional SDEs in Sections 2.1 and 2.2. : there exist some $\lambda,\beta>0$, such that for all $t\in[0,T]$, $u,v\in V$,

where $\langle\cdot,\cdot\rangle_{V\times V^{*}}$ denotes the duality product of $V\times V^{*}$ (see e.g. Assumption 2.1(i) in ). Important special cases of (1.2) include suitable semilinear parabolic PDEs with (additive or multiplicative) noise and the Zakai equation from nonlinear filtering (see e.g. ) or from a large pool limit of interacting particles (see e.g. ).

We are interested in the value functional associated with the SPDE (1.2):

where the discrete operators $A_{d},U_{d},G_{d}$ satisfy a monotonicity condition similar to (1.3). Then, under suitable regularity assumptions, one can show the well-posedness of a solution $y_{d}$ to the finite-dimensional SDE (1.5), and estimate the rate of convergence in terms of the dimension $d$. The convergence of $y_{d}(T)$ to $y(T)$ as $d\rightarrow\infty$ suggests us to approximate the functional $\mathcal{V}$ by the $d$-dimensional value function

Moreover, the control processes and the nonsmoothness of the terminal costs imply that the value function $v_{d}$ typically has weak regularity, e.g. $v_{d}$ is merely locally Lipschitz continuous and could grow quadratically at infinity. This prevents us from approximating the value function by using sparse grid approximations , or high-order polynomial expansions . Finally, since the mappings $A$, $U$ and $G$ in (1.2) could involve differential operators, the Lipschitz constants (with respect to the Euclidean norm) of $A_{d},U_{d},G_{d}$ in (1.5) will in general grow polynomially in dimension $d$. This stiffness of coefficients creates a difficulty in constructing efficient discrete-time dynamics to approximate the time evolution of the Itô-Galerkin SDE (1.5).

In recent years, DNNs have achieved remarkable performance in representing high-dimensional mappings in a wide range of applications (see e.g. and the references therein for applications in optimal control and numerical simulation of PDEs), and it seems that DNNs admit the flexibility to overcome the curse of dimensionality. However, even though there is a vast literature on the approximation theory of artificial neural networks (see e.g. ), to the best of our knowledge, only established DNNs’ expression rates for approximating nonsmooth value functions (associated with $d$-dimensional SDEs whose diffusion coefficients are affine with respect to the state variable and both the drift and diffusion coefficients are Lipschitz continuous with a constant independent of the dimension $d$).

In this work, we shall extend their results by giving a rigorous proof of the fact that DNNs do overcome the curse of dimensionality for approximating (nonsmooth) value functions of zero-sum games of controlled SDEs with stiff, time-inhomogeneous, nonlinear coefficients. More precisely, we shall establish that for a wide class of controlled stiff SDEs, to represent the corresponding value functions with accuracy $\varepsilon$, the number of parameters in the employed DNNs grows at most polynomially in both the dimension of the state equation and the reciprocal of the accuracy $\varepsilon$ (see Theorems 2.1 and 2.3). As a direct consequence of these expression rates, we show that one can approximate the viscosity solution to a Kolmogorov backward PDE with stiff coefficients by DNNs with polynomial complexity (see Corollary 2.2). In particular, if one further assumes that the Galerkin approximation of a controlled SPDE has a convergence rate $\mathcal{O}(d^{-\gamma})$ for some $\gamma>0$, our result indicates that we can represent the nonlinear value functional $\mathcal{V}$ without the curse of dimensionality.

The approach we take here is to first describe the evolution of a $d$-dimensional controlled SDE (1.1) by using a suitable discrete-time dynamical system, and then constructing the desired DNN by a specific realization of the discrete-time dynamics. This is of the same spirit as , where the authors represent an uncontrolled SDE with constant diffusion and nonlinear drift coefficients by its explicit Euler discretization. However, due to the stiffness of the Itô-Galerkin SDEs considered in this paper, such an explicit time discretization will in fact lead to an approximation error depending exponentially on the dimension $d$ (cf. [34, Proposition 4.4]), and hence it cannot be used in our construction. We shall overcome this difficulty by approximating the underlying dynamics with its partial-implicit Euler discretization, whose error depends polynomially on the dimension $d$ and the (time) stepsize. We also adopt a two-step approximation of the terminal cost function involving truncation and extrapolation, which allows us to construct rectified neural networks for quadratically growing terminal costs; see the discussion below (H.1) for details.

The rest of this paper is structured as follows. Section 2 states the assumptions and presents the main theoretical results of the expression rates. We discuss several fundamental operations of DNNs in Section 3, and analyze a perturbed linear-implicit Euler discretization of SDEs in Section 4. Based on these estimates, we establish the expression rates of rectified neural networks for uncontrolled systems in Section 6, and controlled systems in Section 7. Section 8 offers possible extensions and directions for further research.

Main results

In this section, we shall recall the notion of DNN, and state our main results on the expression rates of DNNs for approximating value functions associated with controlled SDEs with stiff coefficients.

Let $\mathcal{N}$ be the set of DNNs given by

Roughly speaking, one can describe a DNN by its architecture, that is the number of layers $L$ and the dimensions of all layers $N_{0},N_{1},\ldots,N_{L}$, together with the coefficients of the affine functions used to compute each layer from the previous one. Note that Definition 2.1 does not specify a fixed nonlinear activation function in the architecture of a DNN, but instead considers the realization of a DNN with respect to a given activation function, which allows us to study the approximation capacity of DNNs with arbitrary activation functions (see e.g. Lemma A.1).

To simplify the presentation, in the work we shall mainly focus on DNNs with the commonly used Rectified Linear Unit (ReLU) activation function, i.e., $\varrho(x)=\max(0,x)$, due to its representation flexibility. Moreover, we allow the weights of a DNN (i.e., the coefficients of the affine functions) to take arbitrary real numbers when approximating a given function. A similar analysis can be carried out for networks with quantization (i.e., the maximal magnitude of weights in the network is a priori fixed), by allowing the a priori bound of the weights to increase in a controlled way (see e.g. ).

In this section, we present the expression rate of DNNs for approximating value functions induced by nonlinear SDEs with stiff coefficients.

where $Y^{x,d}=(Y^{x,d}_{t})_{t\in[0,T]}$ is the strong solution to the following $d$-dimensional SDE:

We now list the main assumptions on the coefficients.

Let us briefly discuss the importance of the above assumptions. The monotonicity condition (2.3) in (H.1(a)) is weaker than the finite-dimensional analogue of the strong monotonicity condition (1.3), in the sense that (2.3) involves only the standard Euclidean norm instead of discrete Sobolev norms. The monotonicity, along with the Lipschitz continuity in (H.1(c)), ensures the well-posedness of (2.2) (see e.g. ), and allows us to derive precise regularity estimates (in $L^{p}$-norms for $p\in[2,2+\eta)$) of the solution $Y^{x,d}$ to the SDE (2.2) with respect to the coefficients and the initial condition.

It is worth emphasizing that (H.1) allows the operator norm of $A_{d}$ and the Lipschitz constants of the nonlinear functions $\mu_{d}$ and $\sigma_{d}$ to grow with respect to the dimension $d$, which is crucial for applications to stiff SDEs arising from Galerkin approximations of (controlled) SPDEs. In fact, most existing results on overcoming the curse of dimensionality with DNNs (see e.g. ) are for value functions associated with high-dimensional SDEs whose diffusion coefficients are affine with respect to the state variable and both drift and diffusion coefficients are Lipschitz continuous uniformly with respect to the dimensions. Note that it is easy to check that if $\mu_{d},\sigma_{d}$ satisfy (H.1(c)) with a Lipschitz constant independent of the dimension $d$, then the coefficients satisfy (H.1(a)). In particular, our setting includes the representation result in as a special case.

We remark that both the monotonicity condition (2.3) and the Lipschitz continuity of $\mu_{d}$ are crucial for constructing networks with polynomial complexity to approximate the desired value functions. With the help of the monotonicity condition (H.1(a)), we can demonstrate that both the regularity of the solution $Y^{x,d}$ to (2.2) and the error estimates of a corresponding partial-implicit Euler scheme depend polynomially on $\|A_{d}\|_{\rm{op}}$, $[\mu_{d}]_{1}$ and $[\sigma_{d}]_{1}$, i.e., the Lipschitz constants of the coefficients (see Section 4 for details; see also for SDEs with merely Lipschitz continuous coefficients, for which the corresponding estimates depend exponentially on the Lipschitz constants of the coefficients). These polynomial dependence results subsequently enable us to construct DNNs with polynomial complexities to approximate the value functions induced by stiff SDEs, including those arising from Galerkin approximations of SPDEs.

On the other hand, the Lipschitz continuity of $\mu_{d}$ allows us to construct the desired DNNs through a linear-implicit Euler scheme of (2.2), which is implicit in the linear part of the drift and remains explicit for the nonlinear part of the drift. In fact, to the best of our knowledge, if the function $\mu_{d}$ is not globally Lipschitz continuous, then one needs to adopt a fully-implicit scheme, a tamed explicit scheme or an adaptive Euler scheme to obtain a convergent approximation of (2.2) in the $L^{2}$-norm. These schemes in general involve of nonlinear mappings that are difficult to represent by ReLU networks; in particular, the fully-implicit scheme involves of the inverse of the mapping $y\mapsto y+\Delta t(A_{d}y-\mu_{d}(t,y))$ (see e.g. ), the tamed explicit scheme involves of the mapping $y\mapsto\frac{\mu_{d}(t,y)}{1+\Delta t\|\mu_{d}(t,y)\|}$ (see e.g. ), while the adaptive Euler scheme involves a non-uniform random stepsize which varies for different realisations of the Brownian motion and needs to be constructed in a problem-dependent way (see e.g. ).

The DNNs $(\phi^{\mu}_{\varepsilon,d},\phi^{\sigma,i}_{\varepsilon,d})_{i}$ have the same architecture, i.e.,

The DNNs $(\phi^{\mu}_{\varepsilon,d},\phi^{\sigma,i}_{\varepsilon,d},\phi^{f}_{\varepsilon,d,D})$ admit the following complexity estimates:

Since a ReLU network can be extended to an arbitrary depth and width without changing its realization (Lemma A.3), we assume without loss of generality in (H.2(a)) that $(\phi^{\mu}_{\varepsilon,d},\phi^{\sigma,i}_{\varepsilon,d})_{i=1,\ldots,d}$ have the same architecture to simplify our analysis.

where $A$ and $G$ are second-order and first-order linear differential operators, respectively. Moreover, by virtue of the fact that ReLU networks can efficiently represent the pointwise maximum/minimum operations (see Proposition 3.3), one can see (H.2(b),(c)) also hold for the discretizations of the following Hamilton–Jacobi–Bellman–Isaacs equation, since the (discretized) Hamiltonian can be exactly expressed by ReLU networks:

and ${\textbf{A}},{\textbf{B}}$ are two given finite sets. Finally, for general semilinear PDEs with bounded solutions, one may consider an equivalent semilinear PDE by truncating the nonlinearity outside a compact set, and approximate the truncated coefficients by DNNs.

Finally, we remark that (H.1(d)) and (H.2(c)) essentially assume that for any given $D>0$, there exists a deep ReLU network approximating the terminal function $f_{d}|_{B_{\infty}(D)}$ with polynomial complexity, and the difference between the terminal function $f_{d}$ and the deep ReLU network can be controlled by the quadratic growth of $f_{d}$ outside the hypercube $B_{\infty}(D)$. We refer the reader to Proposition 3.1, where we verify (H.1(d)) and (H.2(c)) for a class of quadratic cost functions.

Now we are ready to state one of the main results of this paper, which shows that one can construct DNNs with polynomial complexity to approximate the value functions induced by nonlinear stiff SDEs. Similar representation results have been shown in for SDEs with affine drift and diffusion coefficients, and in for SDEs with nonlinear drift and constant diffusion coefficients. Our results extend these results to SDEs with time-inhomogeneous nonlinear drift and diffusion coefficients. Moreover, we allow the Lipschitz constants of the coefficients to grow with the dimension $d$, which is crucial for the application to SPDE-constrained optimal control problems. The proof of this theorem is given in Section 6.

The following result is a direct consequence of Theorem 2.1 and the Feynman-Kac formula in [46, Theorem 2.2], which shows one can approximate the viscosity solution to a Kolmogorov backward PDE with stiff coefficients on a bounded domain without curse of dimensionality. The proof will be postponed to Section 6.

2 Expression rate for controlled SDEs with stiff coefficients

In this section, we extend the expression rates in Section 2.1, and construct DNNs with polynomial complexity to approximate value functions associated with a sequence of controlled SDEs with stiff coefficients.

We then state the assumptions on the coefficients of (2.8) for deriving the expression rates of DNNs. Roughly speaking, we assume (H.1) and (H.2) hold uniformly in terms of the control parameters. However, we would like to point out that even though the functions $\mu_{d},\sigma_{d}$ are continuous in time, the controlled drift and diffusion of (2.8) are discontinuous in time due to the jumps in the control processes.

The functions $f_{d}$ and $f_{d,D}$ satisfy (H.1(d)).

The cardinality of the set $U_{d}$ satisfies $|U_{d}|\leq\kappa_{0}d^{\kappa_{0}}$.

The DNNs $(\phi^{\mu}_{\varepsilon,d},\phi^{\sigma,i}_{\varepsilon,d})_{i}$ have the same architecture with the input dimension $d+m_{d}+1$.

The complexities of the DNNs $(\phi^{\mu}_{\varepsilon,d},\phi^{\sigma,i}_{\varepsilon,d},\phi^{f}_{\varepsilon,d,D})$ satisfy (H.2(b)) with the constant $\kappa_{1}$.

with given Lipschitz function $G$ and sufficiently regular basis functions $\{e_{i}\}_{i=1}^{\mathfrak{m}}$. Note that finitely many control parameters appear frequently in practical applications of optimal control theory, since it is difficult to implement control strategies that vary arbitrarily in time and space; see e.g. for elliptic optimal control problems with finite dimensional control spaces. Then it is clear that the discrete version of (2.9) (in both the space and control variables) is a special case of the zero-sum game (2.7) whose coefficients satisfy (H.3) (with $M=1$ in (2.6)).

Now we are ready to present the main theorem in this section, which shows one can represent the value function (2.7) by DNNs without curse of dimensionality, whose proof will be deferred to Section 7.

Note that here the value function (2.7) is induced by optimizing the cost functional over deterministic control strategies (i.e., open-loop controls). For general stochastic games with adapted stochastic strategies (i.e., closed-loop controls), the value function can be identified as the solution of a $d$-dimensional fully-nonlinear HJBI equation (see e.g. ), for which the analysis of DNN approximation rates is more involved (see for some results on overcoming the curse of dimensionality with DNNs for some semilinear PDEs).

ReLU network calculus

In this section, we shall discuss several basic operations to construct new DNNs from existing ones. We shall also establish some fundamental results on the representation flexibility of DNNs by following the setting of Definition 2.1, which are essential for our subsequent analysis.

Recall that it has been shown in that linear combination and composition of a finite number of ReLU DNNs can be realized by a ReLU DNN with polynomial complexity. Moreover, the identity function can be implemented as a ReLU network with one hidden layer. The precise statements of these results will be given in Appendix A for completeness.

It follows directly from the properties of $\phi_{1,\varepsilon}$ that $f_{\varepsilon,1,D}(x)=f_{1,D}(x)$ for $|x|>D$ and $|f_{\varepsilon,1,D}(x)-f_{1,D}(x)|_{L^{\infty}[-D,D]}\leq D^{2}\varepsilon$. Since $f_{\varepsilon,1,D}$ is a composition of the functions $x\mapsto[\mathcal{R}_{\varrho}(\phi_{1,\varepsilon})](x)$ and $x\rightarrow|x|=\varrho(x)+\varrho(-x)$, we know it is the realization of a ReLU network $\phi_{\varepsilon,1,D}$ with complexity $\mathscr{C}(\phi_{1,\varepsilon,D})\leq C\log(\varepsilon^{-1})$, for some constant $C$ independent of $\varepsilon$ and $D$.

Moreover, the following approximation property holds:

Therefore, it remains to show $f_{\varepsilon,d,D}$ is the realization of a ReLU network and estimate its complexity. The main tool to construct the desired ReLU network is a “parallelization” of the network $\phi_{1,\varepsilon,D}$ (see ). Suppose that the network $\phi_{1,\varepsilon,D}$ is given by $\phi_{1,\varepsilon,D}=((W_{1},b_{1}),(W_{2},b_{2}),\ldots,(W_{L},b_{L}))$, and the dimension is $\dim(\phi_{1,\varepsilon,D})=(N_{0},N_{1},\ldots,N_{L-1},N_{L})$. Then we consider the DNN $\phi_{d,\varepsilon,D}=((W^{\prime}_{1},b^{\prime}_{1}),(W^{\prime}_{2},b^{\prime}_{2}),\ldots,(W^{\prime}_{L+1},b^{\prime}_{L+1}))$, where we have for all $i=1,\ldots,L$,

some constant $C$ independent of $\varepsilon,d$ and $D$. ∎

Then there exists a DNN $\psi\in\mathcal{N}$ such that the depth $\mathcal{L}(\psi)=L+L^{\prime}-1$, the dimension

Assume in addition for the case $L^{\prime}\geq 2$ that, $N^{(1)}_{L-1}\leq 2d+\sum_{m=2}^{M}N^{(m)}_{L^{\prime}-1}$, and there exists $m_{0}\in\{2,\ldots,M\}$ such that we have for all $i\in\{2,\ldots,L^{\prime}-1\}$, $m\in\{2,\ldots,M\}$ that $N^{(m)}_{i}\leq N^{(m_{0})}_{i}$. Then it holds that

where $\phi^{\textnormal{Id}}_{d,2}$ is the two-layer representation of the $d$-dimensional identity function defined as in (A.1).

We shall assume the networks $(\phi_{m})_{m=1}^{M}$ are given as follows, and construct the desired network $\psi$ differently based on whether $L^{\prime}=1$ or $L^{\prime}\geq 2$:

Suppose $L^{\prime}=1,$ we shall consider the DNN $\psi=((W_{1},b_{1}),(W_{2},b_{2}),\ldots,(W_{L},b_{L}))$, where $(W_{i},b_{i})=(W^{(1)}_{i},b^{(1)}_{i})$ for $i\in\{1,\ldots,L-1\}$ and

which implies (3.3). Also it is clear that $\mathscr{C}(\psi)=\mathscr{C}(\phi_{1})$.

Now let $L^{\prime}\geq 2$, $\phi^{\textnormal{Id}}_{d,2}=((W^{\textnormal{Id}}_{1},0),(W^{\textnormal{Id}}_{2},0))\in\mathcal{N}^{d,2d,d}_{2}$ be the DNN representation of the $d$-dimensional identity function defined as in (A.1). We shall construct the desired DNN as follows:

where for $i\in\{1,\ldots,L-1\}$, we have $(W_{i},b_{i})=(W^{(1)}_{i},b^{(1)}_{i})$; for $i=L$, we have

Now we turn to estimate the complexity of $\psi$, which is given by

where we denote $\textbf{i}=2d$. Now using the assumptions that $N^{(1)}_{L-1}\leq\textbf{i}+\sum_{m=2}^{M}N^{(m)}_{L^{\prime}-1}$, and $N^{(m)}_{i}\leq N^{(m_{0})}_{i}$ for all $i\in\{2,\ldots,L^{\prime}-1\}$, $m\in\{2,\ldots,M\}$, we have

Then from the same arguments as [16, Proposition 5.3] (c.f. equation (124) in ), we can bound the terms in the square bracket and deduce that

which leads to the complexity estimate (3.4) by using $\mathscr{C}(\phi_{m_{0}})\leq\sup_{m\in\{2,\ldots,M\}}\mathscr{C}(\phi_{m})$. ∎

Note that the complexity of the resulting network $\psi$ is additive to that of the network $\phi_{1}$. Moreover, for fixed networks $(\phi_{m})_{m=2}^{M}$, if we start with a network $\phi_{1}$ whose the last hidden layer’s dimension satisfies $N^{(1)}_{L-1}\leq 2d+\sum_{m=2}^{M}N^{(m)}_{L^{\prime}-1}$, our construction ensures that the dimension of the last hidden layer of the resulting network $\psi$ also enjoys the same property. These two important observations enable us to iteratively apply Proposition 3.2, and construct a network with desired complexity in Sections 6 and 7.

We end this section with the fact that taking pointwise maximum or minimum preserves the property of being represented by a ReLU DNN. One can find similar results in [1, Lemma A.3], where the authors adopt a different notation of neural network by allowing connections between nodes in non-consecutive layers.

where we denote $f_{m}=\mathcal{R}_{\varrho}(\phi_{m})$ for all $m$, $g^{(1)}_{l}=\max_{m=1,\ldots,l}f_{m}$ and $g^{(2)}_{l}=\max_{m=l+1,\ldots,2l}f_{m}$. Then since $\phi_{m}$ has the same architecture, by induction hypothesis, we know $g^{(1)}_{l}$ and $g^{(2)}_{l}$ can be represented by networks $\psi^{(1)}$ and $\psi^{(2)}$, respectively, with the same architecture:

and verify that it represents the parallelization of $\psi^{(1)}$ and $\psi^{(2)}$:

implies that the max function can be represented by the following 2-layer ReLU network:

Therefore, by using (3.5) and Lemma A.4, we deduce that there exists a DNN $\psi_{2l}\in\mathcal{N}$ representing $g_{2l}$ with the complexity

Then by using the hypothesis on $\mathscr{C}(\psi^{(1)}_{l})$ and $\mathscr{C}(\psi^{(2)}_{l})$, we obtain that

which completes our proof for the pointwise maximum operation.

Finally, by observing the simple identity

and the fact that scaling a function can be achieved by adjusting the weights in the output layer of its DNN representation without change its architecture, we can conclude the same result for the pointwise minimum operation. ∎

Linear-implicit Euler discretizations for SDEs

In this section, we shall derive precise error estimates of linear-implicit Euler discretization for a finite-dimensional SDE. In particular, we shall demonstrate that under the monotonicity condition in (H.1(a)), the approximation error of the linear-implicit Euler scheme depends polynomially on the Lipschitz constants of the coefficients, which is crucial for our analysis on the DNN expression rates in Section 6.

In the sequel, we shall simply refer (4.2) and (4.3) as ES and PES, respectively.

We shall make the following assumptions on the coefficients of the SDE (4.1) and the Euler schemes, which are analogues of (H.1) and (H.2) for the fixed $d$-dimensional problem.

The matrix $A$ and the functions $\mu,\sigma$ satisfy the following monotonicity condition:

$\mu$ and $\sigma$ admit the following regularity:

Throughout this section, we shall assume without loss of generality that $\eta\in(0,1)$ in (H.5(a)). Moreover, for any given $h>0$, we can directly deduce from (H.5(b)) that $(I_{d}+hA)x\not=0$ for all $x\not=0$, which implies that the matrix $I_{d}+hA$ is nonsingular, and satisfies the estimates $\|(I_{d}+hA)^{-1}\|_{\textrm{op}}\leq 1$ and $\|hA(I_{d}+hA)^{-1}\|_{\textrm{op}}\leq 1$ (see e.g. [6, Proposition 7.2]).

It is straightforward to verify that the above inequality also holds for $\eta^{\prime}=0$.

On the other hand, by using (H.5(d)), we can obtain

which, together with the estimate (4.6) (with $\eta^{\prime}=3\eta/4$), gives us that

where we used the assumption that $\eta<1$ in the last inequality. ∎

With Lemma 4.1 in hand, we now present the following moment estimate and time regularity result for the strong solutions to (4.1). Note that both the moment estimate and the regularity estimate depend polynomially on the parameters $\|A\|_{\rm{op}}$, $C_{\mu,l}$, $C_{\sigma,l}$, $l=0,1$. This observation plays a crucial role in our subsequent analysis.

Suppose (H.5) holds. Then the SDE (4.1) admits a unique strong solution $(Y_{t})_{t\in[0,T]}$, which admits the following a priori estimate: for all $p\in[2,2+\eta)$ and $t\in[0,T]$,

with the constant $\alpha_{p}$ defined as:

and the following time regularity: for all $t,s\in[0,T]$,

with $\alpha=\frac{1}{2}C_{\mu,0}^{2}+\frac{1+\eta}{2\eta}C_{\sigma,0}^{2}$.

The a priori estimate follows precisely the steps in the arguments for [39, Theorem 4.1 pp. 59] by applying Itô’s formula to the quantity $(\alpha+\|Y_{t}\|^{2})^{\frac{p}{2}}$ and using the growth condition (4.4) in Lemma 4.1. Then one can deduce from (H.5(a)) that

Now we proceed to study the linear-implicit Euler schemes (4.2) and (4.3). The following proposition shows the stability of the linear-implicit Euler scheme.

Then we have the following stability estimate:

For notational simplicity, we introduce the following terms: $\delta X=X^{1}-X^{2}$, $\delta Y=Y^{1}-Y^{2}$, $\delta\mu={\mu}_{1}(t,Y^{1})-{\mu}_{2}(t,Y^{2})$, and $\delta\sigma={\sigma}_{1}(t,Y^{1})-{\sigma}_{2}(t,Y^{2})$. Then we can deduce from (4.8) that

Multiplying the above identity by $\delta X$, we obtain that

from which, by completing the square, one can deduce that

and the fact that $Z$ is independent of $\delta Y$, we can obtain that

which completes the proof of the desired stability estimates. ∎

The next two corollaries follow directly from Proposition 4.3, which give an $L^{2}$-estimate of the numerical solutions to ES (4.2) and PES (4.3), and establish an upper bound of the difference between these two solutions.

where \alpha_{1}=\frac{(1+\eta)^{2}}{\eta}\big{(}C_{\mu,0}^{2}+C_{\sigma,0}^{2}\big{)} and \alpha_{2}=\frac{2(1+\eta)^{2}}{\eta}\big{(}C_{\mu,0}^{2}+C_{\sigma,0}^{2}+\gamma^{2}\big{)}.

which leads to the following estimate: for all $n=0,\ldots,N-1$,

We can then conclude the desired result from the Cauchy-Schwarz inequality and Remark 4.1. ∎

Now we estimate the last three terms in the above inequality. It is clear that the Cauchy-Schwarz inequality gives us that

Moreover, by applying the Cauchy-Schwarz inequality to Frobenius inner product of matrices, we obtain that

Hence, by substituting the above estimates into (4.10) and rearranging the terms, we deduce that

Thus, following similar arguments as those for Corollary 4.4, we can conclude the desired estimate by using the fact that $\delta Y_{0}=0$. ∎

Now we proceed to derive precise error estimates of the linear-implicit Euler schemes (4.2) and (4.3). The following proposition shows the overall approximation error can be bounded by the one-step local truncation errors.

with $\delta Y_{0}=((I_{d}+hA)^{-1}-I_{d})x_{0}$, and the truncation errors $e^{1}_{n+1},e^{2}_{n+1}$ defined as:

For any $n=0,\ldots,N$, we define the random variables $\delta Y_{n}=Y^{\pi}_{n}-Y_{t_{n}}$, $\delta\mu_{n}={\mu}(t_{n},Y^{\pi}_{n})-{\mu}(t_{n},Y_{t_{n}})$, and $\delta\sigma_{n}={\sigma}(t_{n},Y^{\pi}_{n})-{\sigma}(t_{n},Y_{t_{n}})$. Note that we have

Then, by subtracting (4.12) from (4.2), multiplying the resulting equation with $\delta Y_{n+1}$, and completing the square (cf. (4.9)), we can deduce the following the following identity:

which, together with the following inequality:

Consequently, for any $h\leq\eta$, we have

from which, one can deduce by induction that

which leads to the desired statement for all large enough $N$ such that $(\frac{N+2\beta T}{N-T})^{T}\leq 2$. ∎

Now we are ready to present the strong convergence result of the perturbed Euler scheme.

For any given $n=0,\ldots,N-1$, by using (H.5(c)) and the Cauchy-Schwarz inequality, we can estimate the truncation error $e^{1}_{n+1}$ defined by (4.11) as follows:

Similarly, one can obtain the following upper bound of the truncation error $e^{2}_{n+1}$:

where $\delta Y_{0}=((I_{d}+hA)^{-1}-I_{d})x_{0}$. Then, we can directly deduce the following inequality from Remark 4.1:

which, together with $h<1$ and the time regularity of the solution $(Y_{t})_{t}$ (Lemma 4.2), leads us to

Finally, by further assuming $N\geq T\max(2\eta,1/\eta)$, and using Corollary 4.5, we can conclude that:

which completes the proof of the desired error estimate. ∎

We end this section with the following weak convergence rate of the perturbed Euler scheme (4.3) with a perturbed terminal cost.

The assumption (H.5(e)) implies that for all $n=0,\ldots,N$,

with the constant $\alpha_{p}$ defined as in (4.7) for all $p\in[2,2+\eta)$. Thus by choosing $p^{\prime}=1+\eta/4$, we deduce from Young’s inequality $xy\leq\frac{1}{p}x^{p}+\frac{1}{q}y^{q}$, $x,y\geq 0$, $p>1$, $q=p/(p-1)$, that

Thus, by using (4.13) and Theorem 4.7, we obtain that

which, along with the fact that $\psi(x)=x^{1/2}$ is subadditive on $[0,\infty)$, completes our proof. ∎

Linear-implicit Euler discretizations for controlled SDEs

In this section, we extend the convergence analysis in Section 4 to SDEs controlled by a piecewise-constant deterministic strategy, whose coefficients are merely piecewise Hölder continuous in time. We shall establish that, similar to Theorem 4.8, the approximation error of the perturbed Euler scheme depends polynomially on the Lipschitz constant of the coefficients. Such error estimate will be used in Section 7 to establish the expression rate of DNN for value functions of zero-sum games.

We shall assume the coefficients of the SDE (5.1) and the Euler schemes satisfy (H.5) uniformly with respect to the control parameter $(u_{k})_{k=0}^{M-1}$, which is an analogue of (H.3) and (H.4) for the fixed $d$-dimensional problem.

which, under (H.6), satisfy all conditions in (H.5) (with the same constants) except the $1/2$-Hölder continuous in time on $[0,T]$. Consequently, we can deduce that Lemmas 4.1 and 4.2, Proposition 4.3, Corollaries 4.4 and 4.5 and Proposition 4.6 (with $N$ replaced by $NM$ in the statements) also hold for the solutions to (5.1)-(5.3), whose proofs do not rely on the time regularity of coefficients.

Now we extend Theorems 4.7 and 4.8 to establish strong and weak convergence rates for the perturbed Euler scheme (5.3).

We can then proceed along the lines of Theorems 4.7 and 4.8 to obtain the desired error estimates. ∎

Proofs of Theorem 2.1 and Corollary 2.2

This section is devoted to the proofs of Theorem 2.1 and Corollary 2.2.

where $h=T/N$ and $\Delta B^{m}_{n+1}=B^{m}_{(n+1)h}-B^{m}_{nh}$, for all $n=0,\ldots,N-1$.

The following lemma demonstrates that there exists a realization of the perturbed Euler scheme approximating the value function $v_{d}$ globally with the desired accuracy.

Note that $(f^{\delta}_{d,D}({Y}^{x,d,m,\pi}_{N}))_{m=1}^{M}$ are independent and identically distributed random variables. Hence, by using the definition of $v_{d}$ and the weak uniqueness of the SDE (2.2), we can obtain that

where $(Y^{x,d,1}_{t})_{t\in[0,T]}$ is the solution to the SDE (2.2) driven by the Brownian motion $(B^{1}_{t})_{t\in[0,T]}$.

We shall then estimate the two terms in (6.3) separately. Note that Theorem 4.8 implies that for all $N\geq T\max\left(\frac{2\beta+2^{1/T}}{2^{1/T}-1},\frac{1}{\eta},2\eta\right)$, we have

Now by letting $D^{\frac{-2\eta}{\eta+4}}\leq Dh^{\frac{1}{2}}$, i.e., $D\geq h^{-\frac{\eta+4}{6\eta+8}}$, we can deduce from the above estimate that

Therefore, by squaring the above inequality and using the integrability condition of the probability measure $\nu_{d}$, we obtain the following estimate:

Thus, we can obtain from Corollary 4.4 that

enables us to bound the second term in (6.3) by

Therefore, under the conditions $N\geq T\max\left(\frac{2\beta+2^{1/T}}{2^{1/T}-1},\frac{1}{\eta},2\eta\right)$ and $D=\lceil h^{-\frac{\eta+4}{6\eta+8}}\rceil$, we can deduce from the estimates (6.3), (6.4) and (6.5) that

We now complete the proof of Theorem 2.1. By fixing the realization $\omega_{\varepsilon,d}\in\Omega$ in Lemma 6.1, we can see that it suffices to show that the map $x\mapsto\frac{1}{M}\sum_{m=1}^{M}f^{\delta}_{d,D}({Y}^{x,d,m,\pi}_{N})(\omega_{\varepsilon,d})$ can be represented by a neural network with the desired complexity.

Consequently, we can infer from Lemma A.4 that there exists a network $\psi^{f,m}_{N}\in\mathcal{N}$ representing the function $x\mapsto f^{\delta}_{d,D}({Y}^{x,d,m,\pi}_{N})(\omega_{\varepsilon,d})$ with the complexity $\mathscr{C}(\psi^{f,m}_{N})\leq 2(\mathscr{C}(\phi^{f}_{\delta,d,D})+\mathscr{C}(\psi_{N}^{m}))$.

for some constant $c>0$, depending only on $\beta,\eta,\kappa_{1},\kappa_{2},\tau$ and $T$. Hence the proof of Theorem 2.1 is finished.

In the remaining part of this section, we shall prove Corollary 2.2, which essentially follows from Theorem 2.1 and the Feynman-Kac formula in [46, Theorem 2.2].

Proof of Theorem 2.3

and $Y^{x,d,u_{1},u_{2}}=(Y^{x,d,u_{1},u_{2}}_{t})_{t\in[0,T]}$ is the solution to the following $d$-dimensional controlled SDE:

In the following we shall first extend Theorem 2.1 to construct DNNs for the function $w_{d}$, and then construct DNNs to represent the value function $v_{d}$.

Moreover, the family of DNNs $(\psi^{u_{1},u_{2}}_{\delta,d})_{u_{1}\in\mathcal{U}_{1,d},u_{2}\in\mathcal{U}_{2,d}}$ has the same architecture (see Proposition 3.2, where the architecture of the constructed network $\psi$ does not depend on the value of $u$).

for some constant $c>0$ independent of $d$ and $\delta$ (note that we have put the constant $\tfrac{34}{7}$ from Proposition 3.3 in the constant $c$, which is possible due to the fact that $\mathscr{C}(\psi^{u_{1},u_{2}}_{\delta,d})\geq 1$).

Finally, we specify the dependence of $\delta$ on the desired accuaracy $\varepsilon$. Note that the following inequality holds for all parametrized functions $(f^{\alpha,\beta},g^{\alpha,\beta})_{\alpha\in\mathcal{A},\beta\in\mathcal{B}}$:

Since $|\mathcal{U}_{1,d}\times\mathcal{U}_{2,d}|\leq(\kappa_{0}d^{\kappa_{0}})^{M}$, by choosing $\delta\leq\varepsilon(\kappa_{0}d^{\kappa_{0}})^{-M/2}$, one can construct a DNN $\psi_{\varepsilon,d}$ with the desired accuracy and complexity, and finish the proof of Theorem 2.3.

Conclusions

To the best of our knowledge, this is the first paper which rigorously explains the success of DNNs in high-dimensional control problems with stiff systems, which arise naturally from Galerkin approximations of controlled PDEs and SPDEs (see e.g. ). The main ingredient of our proof for DNN’s polynomial expression rate is that the underlying stochastic dynamics can be effectively described by a suitable discrete-time system, whose specific realization leads us to the desired DNNs. Similar ideas can be easily extended to study optimal control problems of controlled jump diffusion processes with regime switching (see e.g. ), which enables us to conclude that DNNs can overcome the curse of dimensionality in numerical approximations of weakly coupled systems of nonlocal PDEs.

Natural next steps would be to derive optimal expression rates of DNNs for control problems, and to construct DNNs for approximating value functions in stronger norms, such as $L^{p}$ norms with $p>2$, or Sobolev norms.

Appendix A Basic operations of ReLU DNNs

In this section, we collect several well-known results on the representation flexibility of DNNs.

The following lemma shows a linear combination of realizations of DNNs of the same architecture is again a realization of a DNN with the same activation function, whose proof can be found in [34, Lemma 5.1]. The result has been generalized to the case where the DNNs have the same length but different hidden layer dimensions in [29, Lemma 3.9].

The next result proves that the identity function can be represented by a ReLU network, which is proved in [12, Lemma 5.3].

Using the above representation of the identity function, one can extend a ReLU network to a network with arbitrary depth and widths of hidden layers without changing its realization.

The properties of $\mathcal{E}_{L}(\phi)$ have been proved in [12, Lemma 5.3]. Now we assume $\phi=((W_{i},b_{i}))_{i=1}^{L}\in\mathcal{N}$, and construct the network $\mathcal{W}(\phi)=((W^{\prime}_{i},b^{\prime}_{i}))_{i=1}^{L}\in\mathcal{N}$ by $(W^{\prime}_{i},b^{\prime}_{i})=(W_{i},b_{i})$ for all $i\in\{1,\ldots,L-1\}\setminus\{l,l+1\}$, and

We then recall the composition of two DNNs and the complexity of the resulting network (see [12, Lemma 5.3]).

References