# Neural Network Approximations of Compositional Functions With Applications
to Dynamical Systems ††thanks: This work was supported in part by U.S. Naval
Research Laboratory - Monterey, CA

Wei Kang Department of Applied Mathematics, Naval Postgraduate School,
Monterey, CA, USA<EMAIL_ADDRESS>Qi Gong Department of Applied Mathematics,
University of California, Santa Cruz, Santa Cruz, CA, USA<EMAIL_ADDRESS>
###### Abstract

As demonstrated in many areas of real-life applications, neural networks have
the capability of dealing with high dimensional data. In the fields of optimal
control and dynamical systems, the same capability was studied and verified in
many published results in recent years. Towards the goal of revealing the
underlying reason why neural networks are capable of solving some high
dimensional problems, we develop an algebraic framework and an approximation
theory for compositional functions and their neural network approximations.
The theoretical foundation is developed in a way so that it supports the error
analysis for not only functions as input-output relations, but also numerical
algorithms. This capability is critical because it enables the analysis of
approximation errors for problems for which analytic solutions are not
available, such as differential equations and optimal control. We identify a
set of key features of compositional functions and the relationship between
the features and the complexity of neural networks. In addition to function
approximations, we prove several formulae of error upper bounds for neural
networks that approximate the solutions to differential equations,
optimization, and optimal control.

##  1 Introduction

In recent years, the research at the intersection of the fields of optimal
control, dynamical systems and machine learning have attracted rapidly
increasing attention. Progresses have been made at a fast pace, for instance
[7, 8, 10, 11, 12, 14, 21, 22, 25]. In these papers, machine learning based on
artificial neural networks are used as an effective tool for finding
approximate solutions to high dimensional problems of optimal control and
partial differential equations. Many of these problems are not solvable using
other numerical methods due to the curse of dimensionality, i.e. the
solution’s complexity grows exponentially when the dimension of the problem
increases. Why do neural networks work well? Despite of years of research
efforts, the fundamental reasons are far from clear. Reviews of some related
topics and results can be found in [6, 13]. It is proved in [2] that the
neural network approximation of a function whose gradient has an integrable
Fourier transform can achieve an error upper bound $O(n^{-1/2})$, where $n>0$
is the number of neurons, i.e., the complexity of the neural network. This
rate has a constant exponent that is independent of the problem’s dimension,
$d$. Therefore, the curse of dimensionality is mitigated. However, it is
pointed out in [2] that a constant $C$ in $O(n^{-1/2})$ can indirectly depend
on $d$. If $C$ is exponentially large in $d$, then an exponentially large
value of the neural network’s complexity would be required for the
approximation to be bounded by a given error tolerance. Similar issues are
also brought up in [13] in a review of various neural network approximation
methods. If $L^{\infty}$ norm is used to measure errors, which is the norm
adopted in this paper, the complexity of deep neural networks for the
approximation of compositional functions is bounded above by
$O(\epsilon^{-r})$ for some constant $r>0$, where $\epsilon$ is the error
tolerance [19, 20, 23]. This theory is based on the assumption that
complicated functions can be represented by the compositions of relatively
simple functions. The upper bound of complexity, $O(\epsilon^{-r})$, has an
unknown constant which can grow with the increase of the function’s input
dimension. The growth rate depends on various factors or features associated
with the function. The relationship is not fully understood. What makes the
problem even more challenging is that some functions studied in this paper are
associated with dynamical systems such as the trajectory of differential
equations or the feedback law of optimal control. For these problems, most
existing results including those mentioned above are not directly applicable
to prove or guarantee error upper bounds.

In this paper, we aim to reveal the relationship between the complexity of
neural networks and the internal structure of the function to be approximated.
A theoretical foundation is developed that supports the error analysis of
neural networks for not only functions as input-output relations, but also
functions generated based on the trajectories of differential equations and
the feedback law of optimal control. By the structure of a function, we mean
compositional structure. In engineering applications, it is quite common that
a complicated function with a high input dimension is the result of a sequence
of compositions of simple functions that have low input dimensions. These
simple functions as well as the network structure determine the neural
network’s complexity that is required to accurately approximate the
compositional function. The main contributions of the paper include: 1) We
develop an algebraic framework and an approximation theory for compositional
functions. These results form the theoretical foundation for the proofs of
several theorems on the error upper bound and neural network complexity in the
approximation of compositional functions. The theoretical foundation is
developed in a way so that it supports the error analysis for numerical
algorithms. This capability is critical because it enables the analysis of
approximation errors for problems for which analytic solutions are not
available, such as differential equations and optimal control. 2) We identify
a set of key features of compositional functions. These key features are
quantitative. Their value determines an upper bound of the complexity of
neural networks when approximating compositional functions. These key features
serve as sufficient conditions for overcoming the curse of dimensionality. 3)
We prove several formulae of error upper bounds for neural networks that
approximate the solutions to differential equations, optimization, and optimal
control.

##  2 Composition vs. projection: what is the difference?

A widely used idea of representing functions is to project a function to a
sequence of finite dimensional subspaces. For instance, a large family of
functions can be represented by Fourier series

$\begin{array}[]{lllllllllll}f(x)=\displaystyle\frac{a_{0}}{2}+\displaystyle\sum_{n=1}^{\infty}\left(a_{n}\cos(2n\pi
x)+b_{n}\sin(2n\pi x)\right),&x\in\mathbb{R}.\end{array}$ (1)

In this representation, the $n$-th terms, $a_{n}\cos(2n\pi x)+b_{n}\sin(2n\pi
x)$, are considered to be the elementary units of the function. Because the
projection operator is linear, this representation is closed under linear
combination in the following sense: If both $f$ and $g$ are Fourier series,
then so is $h=af+bg$ for any constants $a$ and $b$; and the $n$-th term of $h$
is determined by the $n$-th term of $f$ and $g$, i.e., the elementary units of
$f$ and $g$ are the elementary units of $h$ as well. However, the Fourier
series representation is not closed under some other important algebraic
operations such as function composition. It is obvious that $h=f\circ g$, or
$h(x)=f(g(x))$, is not in the form of Fourier series. Although one can find a
Fourier series representation for $h$, its $n$-th term is not determined by
the $n$-terms of $f$ and $g$, i.e., the $n$-th terms of $f$ and $g$ are not
elementary units in the Fourier series of $h$.

Let’s consider functions generated through a network of multiple function
compositions. A formal definition of compositional functions is given in the
next section. Algebraic expressions of compositional functions can be
cumbersome due to the complexity of the function. Instead, we use directed
graphs. As an example, consider the following two vector valued functions

$\begin{array}[]{lllllllllll}{\bf
f}(x_{1},x_{2},x_{3})=\left[\begin{array}[]{c}\sin(x_{1}x_{2})\\\
\cos(x_{2}x_{3})\\\ x_{1}x_{3}\end{array}\right],&{\bf
g}(x_{1},x_{2},x_{3})=\left[\begin{array}[]{c}(x_{1}^{2}+x_{2}^{2})\\\
e^{-x^{2}_{1}}\\\ e^{-x^{2}_{3}}\end{array}\right].\end{array}$ (2)

In this paper, we use bold letters, such as ${\bf x}$ and ${\bf f}$, to
represent a vector or a vector valued function and regular font to represent a
scalar or a scalar valued function. The functions ${\bf f}$ and ${\bf g}$ can
be represented by a directed graph in which each node is a function with a
relatively low input dimension (Figure 1). These nodes are the elementary
units of the function.

Figure 1: Directed graphs representing the functions in (2).

Different from representations based on projection, the family of
compositional functions is closed under both linear combinations and
compositions. For example, ${\bf h}={\bf f}-{\bf g}$ is a compositional
function; and every elementary unit (or node) of ${\bf f}$ and ${\bf g}$ is an
elementary unit of ${\bf h}$. The graph of ${\bf h}$ and its nodes are shown
in Figure 2.

Figure 2: Directed graph representing ${\bf f}-{\bf g}$, where ${\bf f}$ and
${\bf g}$ are defined in (2).

If ${\bf h}={\bf f}\circ{\bf g}$, then ${\bf h}$ is a compositional function;
the nodes of ${\bf f}$ and ${\bf g}$ are also nodes of ${\bf h}$ (Figure 3).
In addition to linear combinations and compositions, we will prove in the next
section that the family of compositional functions is also closed under some
other algebraic operations, including inner product, division, and
substitution.

Figure 3: Directed graph representing ${\bf f}\circ{\bf g}$, where ${\bf f}$
and ${\bf g}$ are defined in (2).

Why is this interesting? In real-world applications, mathematical models of
complicated problems oftentimes have a compositional structure in which the
model can be represented by the composition of multiple functions that are
relatively simple. The compositional structure reflects the interactive
relations among basic components and sub-systems determined by physical laws
or engineering design and thus contains valuable insights of the problem. In
addition to functions as input-output relations, many computational algorithms
are compositional. For instance, an iterative algorithm is a process in which
a function is repeatedly applied to the result from the previous step until
the process converges to a small neighborhood of the target point. The
iterative process is equivalent to a finite sequence of function compositions.
For discrete dynamical systems, their trajectories are all compositional
functions. Obviously, neural networks are also compositional functions. In
fact, the family of neural networks is closed under the operation of
composition and linear combination. From the wide spectrum of subjects covered
by compositional functions, we believe that an algebraic framework for
compositional functions can provide a unified theoretical foundation for the
study of neural networks in the approximation of not only functions as input-
output relations, but also other subjects that have effective iterative
algorithms, such as differential equations and optimal control. Because the
family of compositional functions are closed under linear combinations and
compositions, it simplifies the problem of tracking error propagations inside
complicated compositional functions.

Mathematical study on compositional functions has a rich history. In Hilbert’s
13th problem it was conjectured that the roots of some 7th order polynomials
cannot be represented as compositions of functions of two variables. Hilbert’s
conjecture was disproved by Arnold and Kolmogorov. In [15] Kolmogorov showed
that any continuous function defined on a d-dimensional cube can be exactly
represented by a composition of a set of continuous one-dimensional functions
as

$f(x_{1},\cdots,x_{d})=\sum_{q=1}^{2d+1}\phi_{q}\left(\sum_{p=1}^{d}\psi_{pq}(x_{p})\right),$

where $\phi_{q}$ and $\psi_{pq}$ are continuous univariate functions. This
astonishing result of Kolmogorov’s representation theorem reveals that
compositional structure could be viewed as an inherent property of any high-
dimensional continuous functions. By relaxing Kolmogorov’s exact
representation to approximation and leveraging on techniques developed by
Kolmogorov, Ref. [16] gives a direct proof of a universal approximation
theorem of multilayer neural networks for any continuous functions.

In deep learning, compositional functions have been addressed by many authors
[3, 5, 6, 19, 20, 23]. In [3], which is a study of statistic risk with a given
sample size, the approach takes the advantage of the fact that deep networks
with ramp activation functions can be represented as a tree rooted at the
output node. In [5, 6], tree-like function spaces are introduced. They are
considered as the natural function spaces for the purposes of approximation
theory for neural networks. Compositional functions in [19, 20, 23] are
defined using directed acyclic graphs. Our definition of compositional
functions is also based on directed acyclic graphs. However, we give an
emphasis on the graph’s layering, in addition to its nodes and edges.

Before we introduce the main theorems, it is important to develop a
theoretical foundation for error estimation. In Section 3.1, some basic
concepts about compositional functions are defined. In Sections 3.2 and 3.3,
some algebraic properties of compositional functions are proved. These
concepts and properties form a set of pillars that supports the approximation
theory for compositional functions. In Section 4, neural networks are
introduced as a family of special compositional functions. The family of
neural networks is closed under several algebraic operations including linear
combination, composition, and substitution. This property enables the
capability for one to compose complicated deep neural networks based on simple
networks and algebraic operations. Also in Section 4, a set of key features of
compositional functions is identified. For neural network approximations, we
prove an error upper bound that is determined by the key features. Because
iterative computational algorithms can be considered as compositional
functions, the algebraic framework and the approximation theory are applicable
to the solutions to differential equations, optimization, and optimal control.
The results are proved in Sections 5 and 6.

##  3 Algebraic properties of compositional functions

Compositional functions are functions consisting of multiple layers of
relatively simple functions defined in low dimensional spaces. These simple
functions are integrated together through algebraic operations such as
function composition and linear combination. If compositional functions are
estimated by neural networks, errors are propagated through layers of
functions in a complicated way. Analyzing the estimation error requires a good
understanding of the interplay between the error propagation and the internal
structure of the compositional function. In this paper, some proofs of
theorems on neural network solutions to differential equations and optimal
control are impossible without first developing an algebraic foundation and
approximation theory for the family of compositional functions. In the
following, we first define a set of fundamental concepts and then prove some
basic algebraic properties of compositional functions. In Table 1, we
summarize a list of repeatedly used notations in the following sections.

| Notation
---
| Meaning
---
|  Notation
---
| Meaning
---
| ${\cal G}^{\bf f}$
---
| a DAG associated with ${\bf f}$
---
| ${\cal L}^{\bf f}(\cdot)$
---
| a mapping: node $\rightarrow$ layer number
---
| ${\cal V}^{\bf f}$
---
| the set of nodes in ${\cal G}^{\bf f}$
---
| ${\cal E}^{\bf f}$
---
| the set of edges in ${\cal G}^{\bf f}$
---
| ${\cal V}^{\bf f}_{L}$
---
| the set of linear nodes in ${\cal G}^{\bf f}$
---
| ${\cal V}^{\bf f}_{G}$
---
| the set of general nodes in ${\cal G}^{\bf f}$
---
| ${\cal V}^{\bf f}_{I}$
---
| the set of input nodes in ${\cal G}^{\bf f}$
---
| ${\cal V}^{\bf f}_{O}$
---
| the set of output nodes in ${\cal G}^{\bf f}$
---
| $f_{i,j}$
---
| the $j$-th node in the $i$-th layer
---
| $l_{max}^{\bf f}$
---
| the layer number of output nodes
---
| $d_{i,j}$
---
or $d_{i,j}^{\bf f}$
| the input dimension of $f_{i,j}$
---
| $m_{i,j}$
---
or $m^{\bf f}_{i,j}$
| the smoothness of $f_{i,j}$
---
| $R_{i,j}$
---
or $R^{\bf f}_{i,j}$
|  $[-R_{i,j},R_{i,j}]^{d_{i,j}}$ is the domain
---
of $f_{i,j}$
| $L_{i,j}$
---
or $L^{\bf f}_{i,j}$
| a Lipschitz constant associated
---
with $f_{i,j}$
| $\Lambda^{\bf f}$
---
| For all $f_{i,j}\in{\cal V}^{\bf f}_{G}$, the largest
---
$\max\\{(R_{i,j})^{m_{i,j}},1\\}\left\lVert
f_{i,j}\right\rVert_{W^{\infty}_{m_{i,j},d_{i,j}}}$
| $L_{max}^{\bf f}$
---
| the largest $L_{i,j}$ for $f_{i,j}\in{\cal V}^{\bf f}_{G}$
---
|  ${\bf f}$, ${\bf g}$, ${\bf x}$
---
$f_{i,j}$, $x_{i}$
| bold letters represent a vector or a vector valued function
---
regular font represents a scalar or a scalar valued function
Table 1: Some frequently used notations.

###  3.1 Definitions and notations

A directed acyclic graph (DAG) is a directed graph without directed cycles. A
DAG consists of a set of nodes and a set of directed edges. If each node is a
function with input (inward edges) and output (outward edges), then the DAG
represents a compositional function. Figure 4 is an example of DAG associated
with a function ${\bf f}:\mathbb{R}^{4}\rightarrow\mathbb{R}^{2}$. The nodes
that have no inward edges are call input nodes; those that have no outward
edges are called output nodes.

Figure 4: An example of compositional function. The DAG has four input nodes
representing, $x_{1},x_{2},x_{3},x_{4}$, and two output nodes,
$f_{4,1},f_{4,2}$.

DAGs allow layerings that agree with the direction of edges. More
specifically, suppose $(h_{i},h_{j})$ is a directed edge in a DAG in which
$h_{i}$ is a node in the $i$-th layer and $h_{j}$ is in the $j$-th layer, then
$j>i$. For the compositional function in Figure 4, it has a total of five
layers. In this paper, the set of input nodes is always the first layer,
labeled as layer $0$; two layers next to each other are labeled using adjacent
integers; the set of output nodes forms the terminal layer which has the
highest layer number. We would like to point out that the layering of a DAG is
not unique. Moreover, a function may have more than one associated DAGs. For
example, consider the following function

$\begin{array}[]{lllllllllll}f(x_{1},x_{2},x_{3})=\sin(x_{1}x_{2})+\cos(x_{2}x_{3})+x_{1}x_{3}.\end{array}$
(3)

In Figure 5, three DAGs are shown. As a function, they all represent $f$.
Figure 5(a) has three layers. Both (b) and (c) have four layers. However, the
set of nodes in two of the layers are different. In Figure 5, some nodes are
colored and some are white. The reason will be explained following Definition
1.

Figure 5: Three DAGs associated with the same function in (3).

###### Definition 1

(Compositional function) A compositional function is a triplet, $({\bf
f},{\cal G}^{\bf f},{\cal L}^{\bf f})$, consisting of a function, ${\bf
f}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{q}$, a layered DAG, ${\cal G}^{\bf
f}$, and a mapping, ${\cal L}^{\bf f}$. If $h$ is a node in ${\cal G}^{\bf
f}$, then ${\cal L}^{\bf f}(h)$ equals an integer that is the layer number of
$h$. We also use subscripts to represent the layer number, i.e., $f_{i,j}$ is
the $j$-th node in the $i$-th layer. Every node in ${\cal G}^{\bf f}$ that has
at least one inward edge is a function,
$f_{i,j}:\mathbb{R}^{d_{i,j}}\rightarrow\mathbb{R}$, where $d_{i,j}$ is the
number of inward edges of the node. A node that has no inward edge is called
an input node. It can take any value in the domain of ${\bf f}$. All input
nodes in ${\cal G}^{\bf f}$ are labeled as layer $\mathit{0}$, called the
input layer. A node that has no outward edge is called an output node. All
output nodes are located in the final layer, called the output layer. All
layers between input and output layers are called hidden layers. We always
assume that the ranges and domains of all nodes are compatible for
composition, i.e. if $(f_{i,j},f_{l,k})$ is an edge in ${\cal G}^{\bf f}$,
then the range of $f_{i,j}$ is contained in the interior of the domain of
$f_{l,k}$.

For each node in a compositional function, the number of inward edges,
$d_{i,j}$, defines the number of free variables of the node. Each node takes
its value in $\mathbb{R}$, i.e., all nodes are scalar valued functions. The
set of nodes and edges in ${\cal G}^{\bf f}$ are denoted by ${\cal V}^{\bf f}$
and ${\cal E}^{\bf f}$, respectively. Given a node, $f_{i,j}$, if it is a 1st
order polynomial, then it is called a linear node. Otherwise, it is called a
general node. All input nodes are treated as linear nodes. In the figure of
${\cal G}^{\bf f}$, linear nodes have white color. The set of linear nodes are
denoted by ${\cal V}^{\bf f}_{L}$ and the set of general nodes are denoted by
${\cal V}^{\bf f}_{G}$. The set of input nodes, i.e., the first layer of
${\cal G}^{\bf f}$, is denoted by ${\cal V}_{I}^{\bf f}$. Similarly, the layer
formed by output nodes is ${\cal V}_{O}^{\bf f}$. Therefore, ${\cal L}^{\bf
f}({\cal V}_{O}^{\bf f})$ is the largest layer number in the graph. It is
denoted by $l_{max}^{\bf f}$. Given an edge
$(f_{i_{1},j_{1}},f_{i_{2},j_{2}})$. If $i_{2}\geq i_{1}+2$, then we say that
this edge skips layers.

###### Example 1

A complicated function defined in high dimensional spaces can be a
compositional function consisting of simple nodes. In a model of power systems
[1, 24], the electric air-gap torque, ${\bf P}_{e}$, is a vector valued
function that can be approximated by

$\begin{array}[]{lllllllllll}({\bf
P}_{e})_{i}=E_{i}^{2}G_{ii}+\displaystyle\sum_{j=1,j\neq
i}^{m}E_{i}E_{j}(G_{ij}\cos(\delta_{i}-\delta_{j})+B_{ij}\sin(\delta_{i}-\delta_{j})),&1\leq
i\leq m,\end{array}$ (4)

where $m$ is the number of generators, $\delta_{i}$, $i=1,2,\cdots,m$, are
rotor angles of the generators. Other notations represent constant parameters.
This function is used to determine the equilibrium point of the power system.
It is also a part of the torques applied to a rotor in a generator. If the
system have $m=20$ generators, then the model is a function ${\bf
P}_{e}:\mathbb{R}^{20}\rightarrow\mathbb{R}^{20}$. This function can be
represented as a compositional function with simple nodes. Shown in Figure 6
is $({\bf P}_{e})_{i}$ in a DAG with four layers. Except for the layer of
$\sin(z)$ and $\cos(z)$, all nodes are linear. It will be shown later that
linear nodes in a compositional function do not increase the complexity of the
neural network that approximates the function. For all general nodes, their
domains have a low dimension, $d_{i,j}=1$. Theorems in this paper help to
reveal that a low input dimension of individual nodes implies low complexity
when the function is approximated by neural networks. The complexity is not
directly dependent on the overall dimension, in this case $d=20$.

Figure 6: DAG of $({\bf P}_{e})_{i}$ defined in (4)

###### Example 2

Many numerical algorithms are compositional functions. For instant, numerical
algorithms of ODEs such as the Euler method and all explicit Runge-Kutta
methods are compositional functions. Consider

$\begin{array}[]{lllllllllll}\dot{\bf x}={\bf f}({\bf x}),&{\bf
x}\in\mathbb{R}^{d},\,{\bf f}({\bf
x})\in\mathbb{R}^{d},\,t\in[0,T].\end{array}$ (5)

For any initial state ${\bf x}_{0}$, the following is a numerical solution
based on the forward Euler method:

$\begin{array}[]{lllllllllll}{\bf x}_{k}={\bf x}_{k-1}+h{\bf f}({\bf
x}_{k-1}),&1\leq k\leq K,\end{array}$ (6)

where $h=T/K$ is the step size. This algorithm is, in fact, a compositional
function. The structure of its DAG is shwon in Figure 7. Each box represents a
layer that may have multiple nodes if $d>1$. In fact, the box of ${\bf f}$ is
a DAG if ${\bf f}$ is also a compositional function.

Figure 7: DAG structure of the Euler method. If ${\bf f}$ is a compositional
function, then each box represents a layer that may have multiple nodes. The
white box in the upper left represents the input layer of ${\cal G}^{\bf f}$.
The box marked as “${\bf f}({\bf x})$” contains all hidden layers and the
output layer of ${\cal G}^{\bf f}$.

###### Example 3

Neural networks are compositional functions. Let
$\sigma:\mathbb{R}\rightarrow\mathbb{R}$ be an activation function. A function

$\begin{array}[]{lllllllllll}f({\bf
x})=\displaystyle\sum_{j=1}^{n}a_{j}\sigma\left({\bf w}_{j}^{T}{\bf
x}+b_{j}\right),&{\bf x}\in\mathbb{R}^{d},\end{array}$ (7)

is a shallow neural network with a single hidden layer (Figure 8), where ${\bf
w}_{j}$, $a_{j}$ and $b_{j}$ are parameters. Similarly, deep neural networks
are also compositional functions.

Figure 8: DAG of a typical shallow neural network. In the hidden layer,
$f_{1,j}({\bf x})=\sigma\left({\bf w}_{j}^{T}{\bf x}+b_{j}\right)$.

In this paper, the algebraic foundation and approximation theory on
compositional functions are developed as a unified framework for various
applications of neural networks. Before we introduce these applications, we
must define some basic concepts about algebraic operations between
compositional functions, such as linear combination, multiplication, division,
substitution and composition. Many complicated functions and numerical
algorithms, such as the solutions of differential equations or optimal
control, are the results of a sequence of these algebraic operations of
compositional functions.

###### Definition 2

(Linear combintation, multiplication and division of compositional functions)
Given compositional functions $({\bf f}_{1},{\cal G}^{{\bf f}_{1}},{\cal
L}^{{\bf f}_{1}})$ and $({\bf f}_{2},{\cal G}^{{\bf f}_{2}},{\cal L}^{{\bf
f}_{2}})$ in which both ${\bf f}_{1}$ and ${\bf f}_{2}$ are from
$\mathbb{R}^{d}$ into $\mathbb{R}^{q}$. Let $a,b\in\mathbb{R}$ be constant
numbers. Define

$\begin{array}[]{lllllllllll}{\bf g}=a{\bf f}_{1}+b{\bf f}_{2}.\end{array}$
(8)

Then ${\bf g}$ is a compositional function associated with a layered DAG that
is induced by $({\bf f}_{1},{\cal G}^{{\bf f}_{1}},{\cal L}^{{\bf f}_{1}})$
and $({\bf f}_{2},{\cal G}^{{\bf f}_{2}},{\cal L}^{{\bf f}_{2}})$. The induced
DAG and its layering are defined as follows (see Figure 9 for an
illustration).

  1. 1.

Input layer: Let ${\cal V}^{{\bf f}_{1}}_{I}={\cal V}^{{\bf f}_{2}}_{I}={\cal
V}^{\bf g}_{I}$, i.e., the input layer of ${\cal G}^{\bf g}$ is formed by
overlapping the input nodes of ${\bf f}_{1}$ and ${\bf f}_{2}$. The outward
edges of the input nodes in ${\cal G}^{{\bf f}_{1}}$ and ${\cal G}^{{\bf
f}_{2}}$ are combined.

  2. 2.

Hidden layers: all nodes in $\left({\cal V}^{{\bf f}_{1}}\setminus{\cal
V}^{{\bf f}_{1}}_{I}\right)\cup\left({\cal V}^{{\bf f}_{2}}\setminus{\cal
V}^{{\bf f}_{2}}_{I}\right)$ are nodes of ${\cal G}^{\bf g}$. The layer number
of each node is kept the same as that in their original DAG. The edges
pointing to or from these nodes are kept unchanged.

  3. 3.

Output layer: Create $q$ output nodes. Each one has two inward edges. For the
$k$-th node, where $k=1,2,\cdots,q$, one inward edge starts from $f_{l^{{\bf
f}_{1}}_{max},k}$ and the other one from $f_{l^{{\bf f}_{2}}_{max},k}$. Each
output node is a function

$\begin{array}[]{lllllllllll}h=az_{1}+bz_{2}.\end{array}$ (9)

The layer number of output nodes in ${\cal G}^{\bf h}$ is

$\begin{array}[]{lllllllllll}\max\left\\{l_{max}^{{\bf f}_{1}},l_{max}^{{\bf
f}_{2}}\right\\}+1.\end{array}$ (10)

One can define the induced DAGs for the compositional functions ${\bf
f}_{1}^{T}{\bf f}_{2}$ and $f_{1}/f_{2}$ (if $q=1$, $f_{1}$ and $f_{2}$ are
scalar valued functions and $f_{2}\neq 0$) by modifying the output layer
accordingly.

Figure 9: Induced DAG of $a{\bf f}_{1}+b{\bf f}_{2}$. In the output layer, the
$k$-th node is $af^{{\bf f}_{1}}_{l^{{\bf f}_{1}}_{max},k}+bf^{{\bf
f}_{2}}_{l^{{\bf f}_{2}}_{max},k}$, where $f^{{\bf f}_{i}}_{l^{{\bf
f}_{i}}_{max},k}$ is the $k$-th output node of ${\bf f}_{i}$, $i=1,2$. For
${\bf f}_{1}^{T}{\bf f}_{2}$, the DAG is the same except that the output layer
has one node only, which is $\sum_{k=1}^{d}f^{{\bf f}_{1}}_{l^{{\bf
f}_{1}}_{max},k}f^{{\bf f}_{2}}_{l^{{\bf f}_{2}}_{max},k}$. For $q=1$, the DAG
of $f_{1}/f_{2}$ has an output layer that has one node,
$f^{f_{1}}_{l^{f_{1}}_{max},1}/f^{f_{2}}_{l^{f_{2}}_{max},1}$.

This definition implies that the family of compositional functions is closed
under inner product and division, in addition to linear combination and
composition. Unless otherwise stated, in this paper we always use the induced
DAG for functions that are generated through algebraic operations of
compositional functions. In the following, we define the induced DAG for a few
more types of algebraic operations involving compositional functions. In
Figure 10(a)-(b), two compositional functions, $f$ and $g$, are shown. We
would like to substitute $g$ for the node $f_{2,1}$, a function that has the
same number of inputs as $g$. Figure 10(c) shows a layered DAG of $\tilde{f}$,
the function resulting from the substitution. The blue nodes and edges are
those from ${\cal G}^{f}$. The red nodes and edges are those from ${\cal
G}^{g}$. In the substitution, all input nodes of ${\cal G}^{g}$ are removed;
their outward edges are attached to the corresponding nodes in ${\cal G}^{f}$;
$f_{2,1}$ is replaced by the output node of ${\cal G}^{g}$. The layering is
changed depending on the depth of ${\cal G}^{g}$.

###### Definition 3

(Node substitution) Given a compositional function $({\bf f},{\cal G}^{\bf
f},{\cal L}^{\bf f})$. Let $f_{i,j}:\mathbb{R}^{d_{i,j}}\rightarrow\mathbb{R}$
be a node in the $i$-th layer, where $i\geq 1$. Let $(g,{\cal G}^{g},{\cal
L}^{g})$, $g:\mathbb{R}^{d_{i,j}}\rightarrow\mathbb{R}$, be a compositional
function. Substituting $g$ for $f_{i,j}$ results in a new compositional
function, $\tilde{\bf f}$. The induced DAG and its layering are defined as
follows.

  1. 1.

${\cal V}^{\tilde{\bf f}}=\left({\cal V}^{\bf
f}\setminus\\{f_{i,j}\\}\right)\cup\left({\cal V}^{g}\setminus{\cal
V}^{g}_{I}\right)$

  2. 2.

If $\\{v_{1},\cdots,v_{d_{i,j}}\\}$ is the ordered set of inward edges of
$f_{i,j}$, then each $v_{i}$ is replaced by the set of outward edges of
$g_{0,i}$. For the outward edges of $f_{i,j}$, their new starting node in
${\cal G}^{\tilde{\bf f}}$ is the output node of $g$. All other edges in
${\cal G}^{\bf f}$ and ${\cal G}^{g}$ are kept unchanged.

  3. 3.

Let ${\it\Delta}i$ be a positive integer so that $i-{\it\Delta}i$ be the
highest layer number of layers in ${\cal G}^{\bf f}$ from which at least one
node has an outward edge pointing to $f_{i,j}$. The layering in ${\cal
G}^{\tilde{\bf f}}$ is defined as follows.

$\begin{array}[]{lllllllllll}\mbox{For }f_{l,k}\in{\cal V}^{\bf
f}\setminus\\{f_{i,j}\\},&{\cal L}^{\tilde{\bf
f}}(f_{l,k})=\left\\{\begin{array}[]{lll}l,&l\leq i-1\\\
l+\max\\{0,l_{max}^{g}-{\it\Delta}i\\},&l\geq i\end{array}\right.,\\\
\mbox{For }g_{l,k}\in{\cal V}^{g}\setminus\left({\cal V}^{g}_{I}\cup{\cal
V}^{g}_{O}\right),&{\cal L}^{\tilde{\bf f}}(g_{l,k})=l+i-{\it\Delta}i,\\\
\mbox{For }g_{l,k}\in{\cal V}^{g}_{O},&{\cal L}^{\tilde{\bf
f}}(g_{l,k})=\max\\{i,i-{\it\Delta}i+l^{g}_{max}\\}.\end{array}$ (11)

Figure 10: Node substitution. The compositional function in (c) is the result
of substituting $g$ in (b) for the node $f_{2,1}$ in (a).

Many numerical algorithms are iterative, i.e., the same function is repeatedly
applied to the result from the previous iteration until the process converges
to a small neighborhood of the target point. If each iteration is a
compositional function, then the numerical process can be considered as a
sequence of compositions of compositional functions.

###### Definition 4

(Composition of compositional functions) Given positive integers $d$, $q$ and
$s$. Consider two compositional functions $({\bf f},{\cal G}^{\bf f},{\cal
L}^{\bf f})$ and $({\bf g},{\cal G}^{\bf g},{\cal L}^{\bf g})$, ${\bf
f}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{q}$, ${\bf
g}:\mathbb{R}^{q}\rightarrow\mathbb{R}^{s}$. Let ${\bf h}={\bf g}\circ{\bf
f}:{\bf x}\in\mathbb{R}^{d}\rightarrow g(f({\bf x}))\in\mathbb{R}^{s}$. Then
${\bf h}$ is a compositional function. Stacking ${\cal G}^{\bf g}$
horizontally to the right of ${\cal G}^{\bf f}$ forms the induced DAG of ${\bf
h}$ as illustrated in Figure 11. More specifically,

  1. 1.

${\cal V}^{\bf h}={\cal V}^{\bf f}\cup\left({\cal V}^{\bf g}\setminus{\cal
V}^{\bf g}_{I}\right)$.

  2. 2.

The outward edges from the input nodes in ${\cal G}^{\bf g}$ are attached to
the corresponding output nodes in ${\cal G}^{\bf f}$ as new starting nodes.

  3. 3.

The order of layers are kept unchanged, i.e.,

$\begin{array}[]{lllllllllll}{\cal L}^{\bf h}(f_{i,j})={\cal L}^{\bf
f}(f_{i,j}),&\mbox{for }f_{i,j}\in{\cal V}^{\bf f},\\\ {\cal L}^{\bf
h}(g_{i,j})=l^{\bf f}_{max}+{\cal L}^{\bf g}(g_{i,j}),&\mbox{for
}g_{i,j}\in{\cal V}^{\bf g}\setminus{\cal V}^{\bf g}_{I}.\end{array}$ (12)

Figure 11: Composition of compositional functions. The function in (c) is the
composition of the functions in (a) and (b).

In this study, we find that the layering of a DAG plays an important role in
the propagation of approximation errors through a network of nodes. For
example, given a node in the $i$-th layer of a compositional function. The
variation of this node impacts the value of nodes in the layers $l\geq i+1$,
but not those in the layers $l\leq i$. In the following, we introduce the
concept of compositional truncation along a layer. The concept leads us to the
definition of the Lipschitz constant associated with nodes. Consider a
compositional function with five layers shown in Figure 12(a). Its truncation
along the layer $l=1$ is a function, $\bar{\bf f}$, that is shown in Figure
12(b). In the truncation process, we first remove all edges that end at nodes
in layers $l\leq 1$. Subsequently, $f_{0,1}$ and $f_{0,2}$ become isolated
nodes, i.e., they have neither outward nor inward edge. Remove them from the
graph. Align all nodes in layers $l\leq 1$, $f_{1,1}$, $f_{1,2}$, $f_{0,3}$
and $f_{0,4}$, to form the input layer of the truncated function. In the new
input layer, the nodes from layer $l=1$ in ${\cal G}^{\bf f}$ (in this
example, $f_{1,1}$ and $f_{1,2}$) are kept in the same order; the nodes moved
up from layer $l=0$ (in this case $f_{0,3}$ and $f_{0,4}$) are located at the
lower half of the layer. Their order is not important. A set of dummy
variables, $(z_{1},z_{2},z_{3},z_{4})$, is introduced as the input of
$\bar{\bf f}$, the truncated function. It is important to clarify that the
domain of $z_{k}$ is the intersection of the domains of all nodes that are
directly connected with $z_{k}$ in $\bar{\bf f}$. For example, $z_{2}$ in
Figure 12 can take any value that is in the domains of $f_{2,1}$, $f_{2,2}$
and $f_{2,3}$ simultaneously. The value is not necessarily in the range of the
original node $f_{1,2}$ in ${\cal G}^{\bf f}$.

###### Definition 5

(Compositional truncation) Given a compositional function $({\bf f},{\cal
G}^{\bf f},{\cal L}^{\bf f})$. Let $i$ be an integer, $1\leq i\leq
l_{max}^{\bf f}-1$. The compositional truncation of ${\bf f}$ along layer $i$
is another compositional function, $\bar{\bf f}$. Its layered DAG is obtained
by the following process: (i) removing all edges in ${\cal G}^{\bf f}$ whose
ending nodes are located in layers $l\leq i$; (ii) removing all isolated nodes
whose inward and outward edges are all removed in (i); (iii) forming the input
layer of $\bar{\bf f}$ by aligning all nodes in layers $l\leq i$ in ${\cal
G}^{\bf f}$ that are not removed in (ii). We find it convenient in discussions
if the order of $f_{i,j}$’s in ${\cal G}^{\bf f}$ remains the same in the new
input layer and they are located at the top portion of the layer. All other
nodes in the new input layer are located at the bottom of the layer organized
in any order one may choose. Given any $f_{l,k}\in{\cal G}^{\bf f}$, $l\geq
i$, its layer number in ${\cal G}^{\bar{\bf f}}$ is $l-i$. The variables
associate with the input layer of ${\cal G}^{\bar{\bf f}}$ are called dummy
inputs. Each dummy input can take any value that is in the common domain of
all nodes in ${\cal G}^{\bar{\bf f}}$ that have inward edges starting from
this input node.

Figure 12: Compositional truncation. The function in (b) is the compositional
truncation of the function in (a) along layer $l=1$.

The concept of the Lipschitz constant is essential in several theorems proved
in this paper. In the following, we define the Lipschitz constant associated
with nodes based on a given norm. For vectors in $\mathbb{R}^{d}$, its
$p$-norm is

$\begin{array}[]{lllllllllll}\left\lVert{\bf
x}\right\rVert_{p}=\left\\{\begin{array}[]{ll}\left(\left|x_{1}\right|^{p}+\left|x_{2}\right|^{p}+\cdots+\left|x_{d}\right|^{p}\right)^{1/p},&1\leq
p<\infty\\\
\max\\{|x_{1}|,|x_{2}|,\cdots,|x_{d}|\\},&p=\infty\end{array}\right.\end{array}$
(13)

###### Definition 6

(The Lipschitz constant associated with a node) Given a compositional function
$({\bf f},{\cal G}^{\bf f},{\cal L}^{\bf f})$ and a constant $1\leq
p\leq\infty$. Consider a node, $f_{i,j}$, in the $i$-th layer, where $0\leq
i\leq l^{\bf f}_{max}-1$. Let $\bar{\bf f}(z_{1},\cdots,z_{j},\cdots)$ be the
truncation of ${\bf f}$ along the $i$-th layer. If $L_{i,j}>0$ is a constant
satisfying

$\begin{array}[]{lllllllllll}\left\lVert\bar{\bf
f}(z_{1},\cdots,z_{j}+{\it{\it\Delta}}z,\cdots)-\bar{\bf
f}(z_{1},\cdots,z_{j},\cdots)\right\rVert_{p}\leq
L_{i,j}\left|{\it\Delta}z\right|\end{array}$ (14)

for all $(z_{1},\cdots,z_{j},\cdots)$ and
$(z_{1},\cdots,z_{j}+{\it\Delta}z,\cdots)$ within the domain of $\bar{\bf f}$,
$L_{i,j}$ is called a Lipschitz constant (under the $p$-norm) associated with
$f_{i,j}$. In some discussions, we denote the constant by $L^{\bf f}_{i,j}$ to
differentiate Lipschitz constants associated with different functions.

We should point out that a Lipschitz constant associated with a node,
$f_{i,j}$, is different from the Lipschitz constant of $f_{i,j}$. The later is
about the rate of change of $f_{i,j}({\bf z})$ when ${\bf z}$ is changed; the
former is about the rate of change of $\bar{\bf f}$, the compositional
truncation, when the value of $f_{i,j}$ is changed, where the node itself is
treated as a free variable. The role of the Lipschitz constant of individual
nodes in a DAG is studied in [19, 20], where a good error propagation
phenomenon is illustrated. Definition 6 provides a different way of tracking
error propagation. It leads to a feature (to be introduced in Section 4) that
has direct impact on an error upper bound of function approximations using
neural networks.

###  3.2 Some properties of Lipschitz constants

Algebraic operations may change Lipschitz constants associate with nodes. The
propositions in this section are about the rules that Lipschitz constants
follow in some algebraic operations of compositional functions.

###### Proposition 1

Given a compositional function, $({\bf f},{\cal G}^{\bf f},{\cal L}^{\bf f})$,
and a node, $f_{i,j}$, in the $i$-th layer. Suppose $(g,{\cal G}^{g},{\cal
L}^{g})$ is another compositional function in which $g$ is a scalar valued
function that has the same domain as $f_{i,j}$. Let $(\tilde{\bf f},,{\cal
G}^{\tilde{\bf f}},{\cal L}^{\tilde{\bf f}})$ be the compositional function
resulting from substituting $g$ for $f_{i,j}$, assuming that the range of $g$
is compatible for the substitution. For all nodes in ${\cal G}^{\bf f}$ in
layers $l\geq i$, their associated Lipschitz constants can be carried over to
${\cal G}^{\tilde{\bf f}}$. Or equivalently, one can assign

$\begin{array}[]{lllllllllll}L^{\tilde{\bf
f}}_{l+\max\\{0,l^{g}_{max}-{\it\Delta}i\\},k}=L^{\bf f}_{l,k},&l\geq
i,\end{array}$ (15)

where $i-{\it\Delta}i$ is the highest layer number of layers in ${\cal G}^{\bf
f}$ from which at least one edge points to $f_{i,j}$.

Proof. From Definition 3, substituting $g$ for $f_{i,j}$ does not change the
nodes and edges above the $i$-th layer. The number of nodes in the $i$-th and
higher layers in ${\cal G}^{\bf f}$ is the same as that in the layers
$l\geq(i+\max\\{0,l^{g}_{max}-{\it\Delta}i\\})$ in ${\cal G}^{\tilde{\bf f}}$.
All edges in ${\cal G}^{\bf f}$ that end at nodes in the layers $l\geq(i+1)$
have a one-to-one correspondence with the edges in ${\cal G}^{\tilde{\bf f}}$
that end at nodes in the layers
$l\geq(i+\max\\{0,l^{g}_{max}-{\it\Delta}i\\})+1$. Therefore, the
compositional truncation of ${\bf f}$ along the $l$-th layer ($l\geq i$) is
identical to the compositional truncation of $\tilde{\bf f}$ along the
$(l+\max\\{0,l^{g}_{max}-{\it\Delta}i\\})$-th layer. Because Lipschitz
constants are defined based on compositional truncations, (15) holds true.
$\blacklozenge$

The following result is about the change of Lipschitz constants after the
composition of two compositional functions.

###### Proposition 2

Given positive integers $d$, $q$ and $s$. Consider two compositional functions
$({\bf f},{\cal G}^{\bf f},{\cal L}^{\bf f})$, ${\bf
f}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{q}$, and $({\bf g},{\cal G}^{\bf
g},{\cal L}^{\bf g})$, ${\bf g}:\mathbb{R}^{q}\rightarrow\mathbb{R}^{s}$. Let
${\bf h}={\bf g}\circ{\bf f}:{\bf x}\in\mathbb{R}^{d}\rightarrow g(f({\bf
x}))\in\mathbb{R}^{s}$. Let $L^{\bf f}$, $L^{\bf g}$ and $L^{\bf h}$ be some
Lipschitz constants of ${\bf f}$, ${\bf g}$ and ${\bf h}$ under a $p$-norm.

  1. 1.

Given any node $f_{i,j}$ in ${\cal G}^{\bf f}$. As a node in ${\cal G}^{\bf
h}$, a Lipschitz constant associate with this node is $L^{\bf f}_{i,j}L^{\bf
g}$.

  2. 2.

A Lipschitz constant of ${\bf h}$ is $L^{\bf h}=L^{\bf f}L^{\bf g}$.

Proof. Part (2) is well known. For part (1), let $\bar{\bf
f}(z_{1},\cdots,z_{j},\cdots)$ be the truncation of ${\bf f}$ along the $i$-th
layer in which $f_{i,j}$ is located. For ${\bf h}$, the truncation along the
layer of the same node is ${\bf g}\circ\bar{\bf f}$. For any
${\it\Delta}z\in\mathbb{R}$,

$\begin{array}[]{lllllllllll}\left\lVert{\bf g}(\bar{\bf
f}(z_{1},\cdots,z_{j}+{\it\Delta}z,\cdots))-{\bf g}(\bar{\bf
f}(z_{1},\cdots,z_{j},\cdots))\right\rVert_{p}\\\ \leq L^{\bf
g}\left\lVert\bar{\bf f}(z_{1},\cdots,z_{j}+{\it\Delta}z,\cdots)-\bar{\bf
f}(z_{1},\cdots,z_{j},\cdots)\right\rVert_{p}\\\ \leq L^{\bf g}L^{\bf
f}_{i,j}\left|{\it\Delta}z\right|.\end{array}$ (16)

$\blacklozenge$

###  3.3 Some properties of error propagation

For compositional functions in which all nodes have low input dimensions, one
can approximate each node using a shallow NN. Substituting these neural
networks for the corresponding nodes that they approximate, the process
results in a deep neural network. The error of using this deep neural network
as an approximation of the function depends on all “local errors”, i.e., the
estimation error of each node. These local errors propagate through the DAG
network interactively. In this section, we study the relationship between the
Lipschitz constants associated with nodes and the propagation of local errors.
To measure errors, we need to introduce an appropriate norm. Given a function,
$f:D^{f}\subset\mathbb{R}^{d}\rightarrow\mathbb{R}$, where $D^{f}$ is a
compact set. Its $L^{\infty}$-norm is the essential supremum

$\begin{array}[]{lllllllllll}\left\lVert
f\right\rVert_{L^{\infty}}=\inf\left\\{M\geq 0;\;\left|f({\bf x})\right|\leq
M\mbox{ almost everywhere in }D^{f}\right\\}.\end{array}$ (17)

Suppose $\tilde{f}$ is an approximation of $f$. We say that the approximation
error is bounded by $\epsilon>0$ if

$\begin{array}[]{lllllllllll}\left\lVert
f-\tilde{f}\right\rVert_{L^{\infty}}\leq\epsilon.\end{array}$ (18)

If both functions are continuous, this is equivalent to

$\begin{array}[]{lllllllllll}\left|f({\bf x})-\tilde{f}({\bf
x})\right|\leq\epsilon,&\mbox{ for all }{\bf x}\in D^{f}.\end{array}$ (19)

In this paper, all approximations are measured using a uniformly bounded error
like the one shown in (19). If ${\bf f}$ is a vector valued function, a
$p$-norm is used to measure the estimation error

$\begin{array}[]{lllllllllll}\left\lVert{\bf f}({\bf x})-\tilde{\bf f}({\bf
x})\right\rVert_{p}\leq\epsilon,&\mbox{ for all }{\bf x}\in D^{\bf
f}.\end{array}$ (20)

When deep neural networks are used to approximate compositional functions, two
types of algebraic operations are frequently used. One is node substitution
and the other is composition. The following propositions are about the
relationship between the approximation errors before and after an algebraic
operation.

###### Proposition 3

Let $({\bf f},{\cal G}^{\bf f},{\cal L}^{\bf f})$ be a compositional function.
Let $\\{h_{1},h_{2},\cdots,h_{K}\\}\subseteq{\cal V}^{\bf f}\setminus{\cal
V}^{\bf f}_{I}$ be a set of nodes. Under a $p$-norm, let $L_{j}^{\bf f}>0$ be
a Lipschitz constant associated with $h_{j}$, $1\leq j\leq K$. Suppose

$\begin{array}[]{lllllllllll}\left\\{(\tilde{h}_{j},{\cal
G}^{{\tilde{h}}_{j}},{\cal L}^{{\tilde{h}}_{j}});1\leq j\leq
K\right\\}\end{array}$ (21)

is a set of compositional functions in which $\tilde{h}_{j}$ has the same
domain as $h_{j}$ and a compatible range for substitution. Assume that

$\begin{array}[]{lllllllllll}\left|{\tilde{h}}_{j}({\bf w})-h_{j}({\bf
w})\right|\leq\epsilon_{j},&\mbox{for all }{\bf w}\mbox{ in the domain of
}h_{j},\end{array}$ (22)

where $\epsilon_{j}$, $j=1,2,\cdots,K$, are some positive numbers. Let
$\tilde{\bf f}$ be the function obtained by substituting $\tilde{h}_{j}$ for
$h_{j}$, $j=1,2,\cdots,K$. Then

$\begin{array}[]{lllllllllll}\left\lVert\tilde{\bf f}({\bf x})-{\bf f}({\bf
x})\right\rVert_{p}\leq\displaystyle\sum_{j=1}^{K}L_{j}^{\bf
f}\epsilon_{j},&\mbox{for all }x\mbox{ in the domain of }{\bf f}.\end{array}$
(23)

Proof. We prove the case for $K=1$ and $2$. The proof can be extended to
arbitrary $K$ through mathematical induction. Let $K=1$. Let $\bar{\bf f}$ and
$\bar{\tilde{\bf f}}$ be the compositional truncation of ${\bf f}$ and
$\tilde{\bf f}$ along the layer in which $h_{1}$ is located. From the proof of
Proposition 1, we know that $\bar{\bf f}=\bar{\tilde{\bf f}}$ . The following
fact follows the definition of compositional truncations,

$\begin{array}[]{lllllllllll}{\bf f}({\bf x})=\bar{\bf f}({\bf z}({\bf
x})),\\\ {\tilde{\bf f}}({\bf x})=\bar{\tilde{\bf f}}(\tilde{\bf z}({\bf
x})),\end{array}$ (24)

where ${\bf z}({\bf x})$, the dummy input of the truncated function, takes the
value of the corresponding nodes in ${\cal G}^{\bf f}$ before the truncation.
Therefore, it depends on ${\bf x}$. The value of ${\tilde{\bf z}}({\bf x})$ is
similarly defined. Without loss of generality, assume that $h_{1}$ is the
first node in its layer. Then, $z_{1}$ takes the value of $h_{1}$ in the
evaluation of ${\bf f}({\bf x})$, and ${\tilde{z}}_{1}$ takes the value of
${\tilde{h}}_{1}$. The value of $z_{1}$ is different from that of
$\tilde{z}_{1}$ because $h_{1}$ is replaced by $\tilde{h}_{1}$. All other
components in $z$ and $\tilde{z}$ are equal because $h_{1}$ is the only node
that is substituted. We have

$\begin{array}[]{lllllllllll}\begin{aligned} \left\lVert{\bf f}({\bf
x})-\tilde{\bf f}({\bf x})\right\rVert_{p}&=\left\lVert\bar{\bf f}({\bf
z})-\bar{\tilde{\bf f}}(\tilde{\bf z})\right\rVert_{p}\\\
&=\left\lVert\bar{\bf f}({\bf z})-\bar{{\bf f}}(\tilde{\bf
z})\right\rVert_{p}\\\ &\leq L^{\bf f}_{1}\left|z_{1}-\tilde{z}_{1}\right|\\\
&=L^{\bf f}_{1}\left|h_{1}({\bf w})-\tilde{h}_{1}({\bf w})\right|,&\\\ &\leq
L^{\bf f}_{1}\epsilon_{1},\end{aligned}\end{array}$ (25)

where ${\bf w}$ takes the value of nodes that have edges pointing to $h_{1}$.
If $K=2$, suppose $\\{h_{1},h_{2}\\}$ is ordered in consistent with the layer
number of the nodes, i.e., ${\cal L}^{\bf f}(h_{1})\leq{\cal L}^{\bf
f}(h_{2})$. Let ${\bf g}$ be the function obtained by substituting
$\tilde{h}_{1}$ for $h_{1}$ in ${\cal G}^{\bf f}$; and $\tilde{\bf f}$ be the
function obtained by substituting both $\tilde{h}_{1}$ and $\tilde{h}_{2}$ for
$h_{1}$ and $h_{2}$, respectively. When the node $h_{2}\in{\cal V}^{\bf f}$ is
considered as a node in ${\cal G}^{\bf g}$, its associated Lipschitz constant
as a node in ${\cal G}^{\bf f}$ can be carried over to ${\cal G}^{\bf g}$
because ${\cal L}^{\bf f}(h_{1})\leq{\cal L}^{\bf f}(h_{2})$ (Proposition 1).
Therefore, $L_{2}^{\bf f}$ is a Lipschitz constant associated with $h_{2}$ as
a node in ${\cal G}^{\bf g}$. Applying the proved result for $K=1$ to both
${\bf f}({\bf x})-{\bf g}({\bf x})$ and ${\bf g}({\bf x})-\tilde{\bf f}({\bf
x})$, we have

$\begin{array}[]{lllllllllll}\left\lVert{\bf f}({\bf x})-\tilde{\bf f}({\bf
x})\right\rVert_{p}\\\ \leq\left\lVert{\bf f}({\bf x})-{\bf g}({\bf
x})\right\rVert_{p}+\left\lVert{\bf g}({\bf x})-\tilde{\bf f}({\bf
x})\right\rVert_{p}\\\ \leq L^{\bf f}_{1}\epsilon_{1}+L^{\bf
f}_{2}\epsilon_{2}\end{array}$ (26)

for all $x$ in the domain of ${\bf f}$. $\blacklozenge$

Given a function ${\bf f}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$. A sequence
of repeated self-compositions is denoted by

$\begin{array}[]{lllllllllll}({\bf f}(\cdot))^{k}({\bf x}):=\overbrace{{\bf
f}\circ{\bf f}\circ\cdots\circ{\bf f}}^{k}({\bf x}).\end{array}$ (27)

###### Proposition 4

Consider compositional functions $({\bf f},{\cal G}^{\bf f},{\cal L}^{\bf
f})$, ${\bf f}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$, $({\bf g},{\cal
G}^{\bf g},{\cal L}^{\bf g})$, ${\bf
g}:\mathbb{R}^{q}\rightarrow\mathbb{R}^{d}$, and $({\bf h},{\cal G}^{\bf
h},{\cal L}^{\bf h})$, ${\bf h}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{q}$.
Suppose that the domains and ranges of them are compatible for compositions.
Let $L^{\bf f}$ and $L^{\bf h}$ be Lipschitz constants of ${\bf f}$ and ${\bf
h}$ under a $p$-norm. Suppose $\tilde{\bf f}$, $\tilde{\bf g}$ and $\tilde{\bf
h}$ are functions satisfying

$\begin{array}[]{lllllllllll}\left\lVert{\bf f}({\bf x})-\tilde{\bf f}({\bf
x})\right\rVert_{p}\leq e_{1},&{\bf x}\mbox{ in the domain},\\\
\left\lVert{\bf g}({\bf x})-\tilde{\bf g}({\bf x})\right\rVert_{p}\leq
e_{2},&{\bf x}\mbox{ in the domain},\\\ \left\lVert{\bf h}({\bf x})-\tilde{\bf
h}({\bf x})\right\rVert_{p}\leq e_{3},&{\bf x}\mbox{ in the
domain},\end{array}$ (28)

for some $e_{1}>0$, $e_{2}>0$ and $e_{3}>0$. Given any integer $K>0$, we have

$\begin{array}[]{lllllllllll}\left\lVert({\bf f}(\cdot))^{K}\circ{\bf g}({\bf
x})-(\tilde{\bf f}(\cdot))^{K}\circ{\tilde{\bf g}}({\bf
x})\right\rVert_{p}\leq\displaystyle\frac{(L^{\bf f})^{K}-1}{L^{\bf
f}-1}e_{1}+(L^{\bf f})^{K}e_{2}.\end{array}$ (29)

and

$\begin{array}[]{lllllllllll}\left\lVert{\bf h}\circ({\bf f}(\cdot))^{K}({\bf
x})-\tilde{\bf h}\circ(\tilde{\bf f}(\cdot))^{K}({\bf x})\right\rVert_{p}\leq
L^{\bf h}\displaystyle\frac{(L^{\bf f})^{K}-1}{L^{\bf
f}-1}e_{1}+e_{3}.\end{array}$ (30)

Proof. The inequality (29) is true if $K=1$ because

$\begin{array}[]{lllllllllll}\left\lVert{\bf f}\circ{\bf g}({\bf
x})-\tilde{\bf f}\circ{\tilde{\bf g}}({\bf x})\right\rVert_{p}\\\
\leq\left\lVert{\bf f}\circ{\bf g}({\bf x})-{\bf f}\circ{\tilde{\bf g}}({\bf
x})\right\rVert_{p}+\left\lVert{\bf f}\circ{\tilde{\bf g}}({\bf x})-\tilde{\bf
f}\circ{\tilde{\bf g}}({\bf x})\right\rVert_{p}\\\ \leq L^{\bf
f}e_{2}+e_{1}.\end{array}$ (31)

Suppose the inequality holds if the power of ${\bf f}(\cdot)$ is $K-1$. Then,

$\begin{array}[]{lllllllllll}\left\lVert({\bf f}(\cdot))^{K}\circ{\bf g}({\bf
x})-(\tilde{\bf f}(\cdot))^{K}\circ\tilde{\bf g}({\bf x})\right\rVert_{p}\\\
\leq\left\lVert{\bf f}\circ({\bf f}(\cdot))^{K-1}\circ{\bf g}({\bf x})-{\bf
f}\circ(\tilde{\bf f}(\cdot))^{K-1}\circ\tilde{\bf g}({\bf
x})\right\rVert_{p}+\left\lVert{\bf f}\circ(\tilde{\bf
f}(\cdot))^{K-1}\circ\tilde{\bf g}({\bf x})-\tilde{\bf f}\circ(\tilde{\bf
f}(\cdot))^{K-1}\circ\tilde{\bf g}({\bf x})\right\rVert_{p}\\\ \leq L^{\bf
f}\left\lVert({\bf f}(\cdot))^{K-1}\circ{\bf g}({\bf x})-(\tilde{\bf
f}(\cdot))^{K-1}\circ\tilde{\bf g}({\bf x})\right\rVert_{p}+e_{1}\\\ \leq
L^{\bf f}\left(\displaystyle\frac{(L^{\bf f})^{K-1}-1}{L^{\bf
f}-1}e_{1}+(L^{\bf f})^{K-1}e_{2}\right)+e_{1}\\\ =\displaystyle\frac{(L^{\bf
f})^{K}-1}{L^{\bf f}-1}e_{1}+(L^{\bf f})^{K}e_{2}.\end{array}$ (32)

The inequality (30) is implied by (29) and the following inequality

$\begin{array}[]{lllllllllll}\left\lVert{\bf h}\circ({\bf f}(\cdot))^{K}({\bf
x})-\tilde{\bf h}\circ(\tilde{\bf f}(\cdot))^{K}({\bf x})\right\rVert_{p}\\\
\leq\left\lVert{\bf h}\circ({\bf f}(\cdot))^{K}({\bf x})-{\bf
h}\circ(\tilde{\bf f}(\cdot))^{K}({\bf x})\right\rVert_{p}+\left\lVert{\bf
h}\circ(\tilde{\bf f}(\cdot))^{K}({\bf x})-\tilde{\bf h}\circ(\tilde{\bf
f}(\cdot))^{K}({\bf x})\right\rVert_{p}\end{array}$ (33)

$\blacklozenge$

The following proposition is simply a version of the triangular inequality. It
is useful when a sequence of approximations are applied to a function.

###### Proposition 5

Given a sequences of functions ${\bf
f}_{j}:D\subset\mathbb{R}^{d}\rightarrow\mathbb{R}^{q}$, $1\leq j\leq K$.
Suppose $\\{e_{j}\\}_{j=1}^{K-1}$ is a sequence of positive numbers satisfying

$\begin{array}[]{lllllllllll}\left\lVert{\bf f}_{j+1}({\bf x})-{\bf
f}_{j}({\bf x})\right\rVert_{p}\leq e_{j},&\mbox{ for }{\bf x}\in D,\;1\leq
j\leq K-1.\end{array}$ (34)

Then,

$\begin{array}[]{lllllllllll}\left\lVert{\bf f}_{1}({\bf x})-{\bf f}_{K}({\bf
x})\right\rVert_{p}\leq\displaystyle\sum_{j=1}^{K-1}e_{j}.\end{array}$ (35)

##  4 Neural networks as compositional functions

Let $W^{\infty}_{m,d}$ be the space of scalar valued functions whose
derivatives up to $m$-th order exist almost everywhere in
$D^{f}\subset\mathbb{R}^{d}$ and they are all essentially bounded. The Sobolev
norm of $f\in W^{\infty}_{m,d}$ is defined by

$\begin{array}[]{lllllllllll}\left\lVert
f\right\rVert_{W^{\infty}_{m,d}}=\displaystyle\sum_{0\leq{\bf k},\left|{\bf
k}\right|\leq m}\left\lVert\displaystyle\frac{\partial^{\left|{\bf
k}\right|}f}{\partial{\bf x}^{{\bf k}}}\right\rVert_{L^{\infty}}\end{array}$
(36)

where ${\bf
k}=\left[\begin{array}[]{rrrrrrrrrrrrrrrrrrrr}k_{1},k_{2},\cdots,k_{d}\end{array}\right]$
represents a vector of integers and $\left|{\bf
k}\right|=\left|k_{1}\right|+\cdots+\left|k_{d}\right|$. Most theorems proved
in this paper are based on similar assumptions. They are stated as follows.

Assumption A1 (Compositional functions) Given a compositional function $({\bf
f},{\cal G}^{\bf f},{\cal L}^{\bf f})$. We assume that ${\bf f}$ is a function
from $[-R,R]^{d}$ to $\mathbb{R}^{q}$ for some $R>0$ and positive integers $d$
and $q$. Assume that the nodes, $\\{f_{i,j}\\}$, are functions in
$W^{\infty}_{m_{i,j},d_{i,j}}$ for some integers $m_{i,j}\geq 1$ and
$d_{i,j}\geq 1$. The domain of $f_{i,j}$ is a hypercube with edge length
$R_{i,j}>0$. The ranges and domains of all nodes are compatible for
composition, i.e., if $(f_{i,j},f_{l,k})$ is an edge in ${\cal G}^{\bf f}$,
then the range of $f_{i,j}$ is contained in the interior of the domain of
$f_{l,k}$.

In the following, we introduce four key features of compositional functions.
These features play a critical role in the estimation of the complexity of
deep neural networks when approximating compositional functions.

###### Definition 7

(Features of compositional functions) Given a compositional function $({\bf
f},{\cal G}^{\bf f},{\cal L}^{\bf f})$, ${\bf
f}:[-R,R]^{d}\rightarrow\mathbb{R}^{q}$, that satisfies A1. The notations
$r^{\bf f}_{max}$, $\Lambda^{\bf f}$ and $L^{\bf f}_{max}$ represent positive
numbers satisfying

$\begin{array}[]{lllllllllll}\begin{aligned} d_{i,j}/m_{i,j}&\leq r^{\bf
f}_{max},\\\ \max\\{(R_{i,j})^{m_{i,j}},1\\}\left\lVert
f_{i,j}\right\rVert_{W^{\infty}_{m_{i,j},d_{i,j}}}&\leq\Lambda^{\bf f},\\\
\left|L_{i,j}\right|&\leq L^{\bf f}_{max},\end{aligned}\end{array}$ (37)

for all nodes in ${\cal V}^{\bf f}_{G}$, where $L_{i,j}$ is defined under a
fixed $p$-norm. These upper bounds, $r^{\bf f}_{max}$, $\Lambda^{\bf f}$ and
$L^{\bf f}_{max}$, together with $\left|{\cal V}^{\bf f}_{G}\right|$ are
called features of the compositional function.

###### Example 4

The function ${\bf
f}:[-R,R]^{d}\subset\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ in (44) is the
vector field that defines the Loranz-96 model [17],

$\displaystyle{\bf f}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{c}x_{0}(x_{2}-x_{-1})-x_{1}+F\\\
x_{1}(x_{3}-x_{0})-x_{2}+F\\\ \vdots\\\ x_{i-1}(x_{i+1}-x_{i-2})-x_{i}+F\\\
\vdots\\\ x_{d-1}(x_{d+1}-x_{d-2})-x_{d}+F\end{array}\right],$ (44)

where $x_{-1}=x_{d-1}$, $x_{0}=x_{d}$, $x_{d+1}=x_{1}$ and $F$ is a constant.
Let’s treat ${\bf f}$ as a compositional function, $({\bf f},{\cal G}^{\bf
f},{\cal L}^{\bf f})$, with a DAG shown in Figure 13.

Figure 13: DAG structure of the function (44). For a clear illustration, edges
pointing to the first, the second, and the third layer are shown in red, blue
and green respectively.

All general nodes in $({\bf f},{\cal G}^{\bf f},{\cal L}^{\bf f})$ are located
in the second layer. They are defined by

$\begin{array}[]{lllllllllll}f_{2,j}(x_{j-1},z_{j})=x_{j-1}z_{j},\
j=1,\cdots,d.\end{array}$ (45)

The formulae of linear nodes are shown in Figure 13. All general nodes have
the dimension $d_{2,j}=2$ and the domain $[-2R,2R]^{2}$. To compute the
Lipchitz constant associated with the general node, $f_{2,j}$, we construct
the truncation of $({\bf f},{\cal G}^{\bf f},{\cal L}^{\bf f})$ along the
second layer, which is given by

$\begin{array}[]{lllllllllll}\bar{\bf
f}(z_{1},\cdots,z_{2d})&=&\left[\begin{array}[]{ccc}z_{1}-z_{d+1}\\\
z_{2}-z_{d+1}\\\ \vdots\\\ z_{d}-z_{2d}\end{array}\right],\end{array}$ (46)

where the dummy inputs $\ z_{i}\in[-2R,2R]$ for all $i=1,\cdots,2d$. Clearly
$L_{2,j}=1$, for all $j=1,\cdots,d$. Since $f_{2,j}$ is smooth, we can set
$m_{2,j}=m$ for any integer $m\geq 2$. Thus,

$\|f_{2,j}\|_{W^{\infty}_{m,2}}=1+2R+4R^{2}.$

Now it is straightforward to compute the features of the compositional
function $({\bf f},{\cal G}^{\bf f},{\cal L}^{\bf f})$:

$\begin{array}[]{lllllllllll}r_{max}^{\bf f}&=&2/m,\\\ \Lambda^{\bf
f}&=&\mbox{max}\\{(2R)^{m},1\\}(1+2R+4R^{2}),\\\ L^{\bf f}_{max}&=&1,\\\
\left|{\cal V}^{\bf f}_{G}\right|&=&d.\end{array}$ (47)

Shallow and deep neural networks are defined as follows. They are
compositional functions in which all general nodes are based on a single
function.

###### Definition 8

(Neural network) A Neural network is a compositional function of a special
type. Given a function $\sigma:\mathbb{R}\rightarrow\mathbb{R}$, which is
called an activation function.

  1. 1.

A shallow NN is a function

$\begin{array}[]{lllllllllll}f({\bf
x})=\displaystyle\sum_{j=1}^{n}a_{j}\sigma\left({\bf w}_{j}^{T}{\bf
x}+b_{j}\right)\end{array}$ (48)

where $a_{j},b_{j}\in\mathbb{R}$ and ${\bf w}_{j}\in\mathbb{R}^{d}$, $1\leq
j\leq n$, are parameters. Its DAG is shown in Figure 14(a), which has one
hidden layer and a linear output node. Each node in the hidden layer,
$f_{1,j}$, is a function of the form ${\bf x}\rightarrow\sigma({\bf w}^{T}{\bf
x}+b)$. In this paper, unless otherwise stated, a shallow neural network is a
scalar valued function.

  2. 2.

A deep neural network is a compositional function $({\bf f},{\cal G}^{\bf
f},{\cal L}^{\bf f})$, ${\bf f}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{q}$, that
has multiple hidden layers (Figure 14(b)). The output layer consists of linear
nodes. Every node in hidden layers is a function of the form ${\bf
z}\rightarrow\sigma({\bf w}^{T}{\bf z}+b)$.

  3. 3.

A node in a hidden layer is called a neuron. The complexity of a neural
network or deep neural network is the total number of neurons in it.

Figure 14: (a): DAG of typical shallow neural networks. (b): DAG structure of
deep neural networks.

###### Remark 1

In many applications of neural networks, edges connecting neurons do not skip
layers. This is different from the deep neural network defined in Definition 8
where edges can skip layers. It is addressed later in this section that one
can construct neural networks without edges that skip layers by adding
identity functions in the DAG. We are not the first ones in the study of DAG
based neural networks. For instance, error analysis and potential
computational advantages were addressed for DAG based neural networks in [4,
19, 20, 23] and references therein. In this paper, all neural networks are DAG
based. For the reason of simplicity, we do not always specify the layered DAG,
${\cal G}^{{\bf f}^{NN}}$ and ${\cal L}^{{\bf f}^{NN}}$, when introducing a
neural network.

###### Remark 2

In Definition 8, there is no linear nodes in the hidden layers. This
requirement is not essential because one can easily modify the DAG of a neural
network to remove all linear nodes by merging them into neurons. Figure 15(a)
shows a portion of a DAG in which $f_{i,j}$ is a linear node. It evaluates the
summation of the three inputs. This linear node is directly connected with a
neuron $\sigma_{l.k}$. We can remove the linear node; and then connect its
inward edges directly to the neuron. Adjusting the neuron’s parameters
accordingly, the result is a simplified DAG shown in Figure 15(b). Following
the same process, one can remove all linear nodes in hidden layers without
increasing the number of neurons. The compositional function resulting from
this process is a deep neural network defined in Definition 8. In the rest of
the paper, we call a function a deep neural network even if it has linear
nodes in addition to neurons, with the understanding that the function is
equivalent to a deep neural network as defined in Definition 8 by merging all
linear nodes into neurons.

Figure 15: An example of merging linear nodes into neurons. The linear node
$f_{i,j}$ in (a) can be removed by merging it into the neuron $\sigma_{l,k}$.
The new DAG is shown in (b).

Based on Remark 2, it is obvious that the family of neural networks is closed
under several algebraic operations, including linear combination,
substitution, and composition.

###### Proposition 6

Given two neural networks, ${\bf f}^{NN}$ and ${\bf g}^{NN}$. Suppose that
their domains and ranges are compatible for the operations discussed below.
Then the following statements hold true.

  1. 1.

The linear combination, $a{\bf f}^{NN}+b{\bf g}^{NN}$ for any constants $a$
and $b$, is a neural network.

  2. 2.

The compositional function, ${\bf g}^{NN}\circ{\bf f}^{NN}$, is a neural
network.

  3. 3.

If a neuron in ${\bf f}^{NN}$ is substituted by $g^{NN}$, the resulting
compositional function is still a neural network.

Based on this proposition, one can compose complicated deep neural networks
using simple and shallow neural networks through sequences of algebraic
operations. When this approach is applied to approximate functions, the
approximation error of a complicated neural network depends on the accuracy of
individual shallow neural networks that are used as building blocks in the
composition. The following theorem on the approximation error of shallow
neural networks, which is proved in [18], is fundamental in the proof of
several theorems about deep neural network approximations of various subjects,
including the solutions of differential equations, optimization problems and
optimal control.

###### Theorem 1

(Shallow neural network approximation [18]) Let $m,d,n\geq 1$ be integers. Let
$\sigma:\mathbb{R}\rightarrow\mathbb{R}$ be an infinitely differentiable
function in some open interval in $\mathbb{R}$. Assume that there is a point,
$b\in\mathbb{R}$, at which $\sigma$ and all its derivatives do not equal zero.
For any positive integer, $n$, there exist vectors $\\{{\bf
w}_{j}\\}_{j=1}^{n}\subset\mathbb{R}^{d}$ and a constant $C$ satisfying the
following property. For any function, $f:[-1,1]^{d}\rightarrow\mathbb{R}$ in
$W^{\infty}_{m,d}$, there exist coefficients $a_{j}(f)$ such that

$\begin{array}[]{lllllllllll}\left|f({\bf
x})-\displaystyle\sum_{j=1}^{n}a_{j}(f)\sigma\left({\bf w}_{j}^{T}{\bf
x}+b\right)\right|\leq Cn^{-m/d}\left\lVert
f\right\rVert_{W^{\infty}_{m,d}},&\mbox{ for all }{\bf
x}\in[-1,1]^{d}.\end{array}$ (49)

The constant $C$ is determined by $d$ and $m$ but is independent of $f$ and
$n$.

This theorem is based on the assumption that the domain of $f$ is a hypercube
whose edge length is 2. However, the domain of each node in a compositional
function do not necessarily satisfy this assumption. The following is an error
upper bound for $f$ defined in a hypercube that has an arbitrary edge length.
The result is proved for domains centered at the origin. Applying translation
mappings, the result can be extended to hypercubes centered at any point.

###### Corollary 1

Making the same assumptions as in Theorem 1 except that the domain of $f$ is
$[-R,R]^{d}$. Then, there exist vectors $\\{{\bf
w}_{j}\\}_{j=1}^{n}\subset\mathbb{R}^{d}$, $b\in\mathbb{R}$, a constant $C$
and coefficients $a_{j}(f)$ such that

$\begin{array}[]{lllllllllll}\left|f({\bf
x})-\displaystyle\sum_{j=1}^{n}a_{j}(f)\sigma\left({\bf w}_{j}^{T}{\bf
x}+b\right)\right|\leq Cn^{-m/d}\max\\{R^{m},1\\}\left\lVert
f\right\rVert_{W^{\infty}_{m,d}},&{\bf x}\in[-R,R]^{d}.\end{array}$ (50)

The constant $C$ is determined by $d$ and $m$ but independent of $f$ and $n$.

Proof. Define a mapping ${\bf x}=R\tilde{\bf x}$ and a new function
$\tilde{f}(\tilde{\bf x})=f(R\tilde{\bf x})$. The domain of the new function
is $[-1,1]^{d}$. From Theorem 1, we have

$\begin{array}[]{lllllllllll}\left|\tilde{f}({\bf
x})-\displaystyle\sum_{j=1}^{n}a_{j}({\tilde{f}})\sigma\left({\bf
w}_{j}^{T}{\bf x}+b\right)\right|\leq
Cn^{-m/d}\left\lVert\tilde{f}\right\rVert_{W^{\infty}_{m,d}}\end{array}$ (51)

for all ${\bf x}$ in $[-1,1]^{d}$. It is obvious that

$\begin{array}[]{lllllllllll}\left\lVert\displaystyle\frac{\partial^{\left|{\bf
k}\right|}{\tilde{f}}}{\partial{\tilde{\bf x}}^{{\bf
k}}}\right\rVert_{L^{\infty}}=\left\lVert\displaystyle\frac{\partial^{\left|{\bf
k}\right|}f}{\partial x^{\bf k}}\right\rVert_{L^{\infty}}R^{\left|{\bf
k}\right|}.\end{array}$ (52)

Therefore,

$\begin{array}[]{lllllllllll}\begin{aligned}
\left\lVert\tilde{f}\right\rVert_{W^{\infty}_{m,d}}&=\displaystyle\sum_{0\leq{\bf
k},\left|\bf k\right|\leq m}\left\lVert\displaystyle\frac{\partial^{\left|\bf
k\right|}\tilde{f}}{\partial\tilde{\bf x}^{\bf k}}\right\rVert_{L^{\infty}}\\\
&=\displaystyle\sum_{j=0}^{m}R^{j}\left(\sum_{\left|\bf
k\right|=j}\left\lVert\displaystyle\frac{\partial^{\left|\bf
k\right|}f}{\partial{\bf x}^{\bf k}}\right\rVert_{L^{\infty}}\right)\\\
&\leq\displaystyle\sum_{j=0}^{m}\max\\{R^{j},1\\}\left(\sum_{\left|\bf
k\right|=j}\left\lVert\displaystyle\frac{\partial^{\left|\bf
k\right|}f}{\partial{\bf x}^{\bf k}}\right\rVert_{L^{\infty}}\right)\\\
&\leq\max\\{R^{m},1\\}\left(\displaystyle\sum_{j=0}^{m}\sum_{\left|\bf
k\right|=j}\left\lVert\displaystyle\frac{\partial^{\left|\bf
k\right|}f}{\partial{\bf x}^{\bf k}}\right\rVert_{L^{\infty}}\right)\\\
&=\max\\{R^{m},1\\}\left\lVert
f\right\rVert_{W^{\infty}_{m,d}}.\end{aligned}\end{array}$ (53)

Then, (51) and (53) imply (50). $\blacklozenge$

Consider a compositional function $({\bf f},{\cal G}^{\bf f},{\cal L}^{\bf
f})$ in which the nodes, $\\{f_{i,j}\\}$, are functions in
$W^{\infty}_{m_{i,j},d_{i,j}}$ for some positive integers $m_{i,j},d_{i,j}\geq
1$. From Theorem 1, there exists a set of constant $C_{i,j}$ and a set of
shallow neural networks, $\\{f_{i,j}^{NN}\\}$, such that

$\begin{array}[]{lllllllllll}\left|f_{i,j}({\bf x})-f_{i,j}^{NN}({\bf
x})\right|\leq
C_{i,j}n^{-m_{i,j}/d_{i,j}}\max\\{R_{i,j}^{m_{i,j}},1\\}\left\lVert
f_{i,j}\right\rVert_{W^{\infty}_{m_{i,j},d_{i,j}}},\mbox{ for all }{\bf
x}\mbox{ in the domain,}\end{array}$ (54)

where $n$ is the complexity, i.e. the number of neurons in $f_{i,j}^{NN}$.
Substituting the shallow neural networks for all general nodes in ${\cal
G}^{\bf f}$ results in a new compositional function consisting of neurons and
linear nodes, i.e. a deep neural network. It is an approximation of ${\bf f}$.
Its error upper bound is proved in the following theorem.

###### Theorem 2

Consider a compositional function $({\bf f},{\cal G}^{\bf f},{\cal L}^{\bf
f})$, ${\bf f}:[-R,R]^{d}\rightarrow\mathbb{R}^{q}$, and a set of its features
(Definition 7). Suppose that the function satisfies A1.

  1. 1.

For any integer $n_{width}>0$, there exists a set of shallow neural networks
of width $n_{width}$ that approximates the nodes in ${\cal V}^{\bf f}_{G}$.
The deep neural network, ${\bf f}^{NN}$, resulting from substituting the
shallow neural networks for all general nodes in ${\cal G}^{\bf f}$ has the
following error upper bound,

$\begin{array}[]{lllllllllll}\left\lVert{\bf f}({\bf x})-{\bf f}^{NN}({\bf
x})\right\rVert_{p}\leq C(n_{width})^{-1/r^{\bf f}_{max}},&\mbox{for all }{\bf
x}\in[-R,R]^{d},\end{array}$ (55)

where $C$ is a constant.

  2. 2.

The constant, $C$, in (55) depends on the features of $({\bf f},{\cal G}^{\bf
f},{\cal L}^{\bf f})$,

$\begin{array}[]{lllllllllll}C=C_{1}L_{max}^{\bf f}\Lambda^{\bf f}\left|{\cal
V}^{\bf f}_{G}\right|,\end{array}$ (56)

where $C_{1}$ is a constant determined by
$\\{d_{i,j},m_{i,j};\;\;f_{i,j}\in{\cal V}^{\bf f}_{G}\\}$.

  3. 3.

The complexity of $f^{NN}$ is $\left|{\cal V}^{\bf f}_{G}\right|n_{width}$.

###### Remark 3

Theorem 2 implies that approximations using neural networks can avoid the
curse of dimensionality, provided that the features of the compositional
function do not grow exponentially with the dimension. More specifically, for
a compositional function defined in a domain in $\mathbb{R}^{d}$, the
complexity of its neural network approximation depends directly on the
features of the function, but not directly on the dimension $d$. Given a
family of compositional functions for $d>0$. If the value of their features do
not increase exponentially as $d\rightarrow\infty$, then neural network
approximations of these compositional functions do not suffer the curse of
dimensionality. We would like to point out that the inequality (55) can be
found in [23]. Different from [23], we rigorously prove the inequality as well
as the relationship between $C$ and the features of compositional functions.

Proof of Theorem 2. For every node $f_{i,j}\in{\cal V}^{\bf f}_{G}$, there
exists a shallow neural network, $f_{i,j}^{NN}$, that approximates the node
(Theorem 1 and Corollary 1). If the number of neurons in $f_{i,j}^{NN}$ is
$n_{width}$, we can find one that satisfies

$\begin{array}[]{lllllllllll}\left|f_{i,j}({\bf z})-f_{i,j}^{NN}({\bf
z})\right|\leq
C_{i,j}(n_{width})^{-m_{i,j}/d_{i,j}}\max\\{R^{m}_{i,j},1\\}\left\lVert
f_{i,j}\right\rVert_{W^{\infty}_{m_{i,j},d_{i,j}}},\end{array}$ (57)

for all ${\bf z}$ in the domain of $f_{i,j}$, where $C_{i,j}$ depends on
$d_{i,j}$ and $m_{i,j}$ but not $f_{i,j}$. Suppose $C_{1}$ is the largest
$C_{i,j}$. From Proposition 3, ${\bf f}^{NN}$ satisfies

$\begin{array}[]{lllllllllll}\left\lVert{\bf f}({\bf x})-{\bf f}^{NN}({\bf
x})\right\rVert_{p}\\\ \leq\displaystyle\sum_{f_{i,j}\in{\cal V}^{\bf
f}_{G}}L_{i,j}^{\bf f}C_{i,j}\max\\{R^{m}_{i,j},1\\}\left\lVert
f_{i,j}\right\rVert_{W^{\infty}_{m_{i,j},d_{i,j}}}(n_{width})^{-m_{i,j}/d_{i,j}}\\\
\leq\displaystyle\sum_{f_{i,j}\in{\cal V}^{\bf f}_{G}}L_{max}^{\bf
f}C_{1}\Lambda^{\bf f}(n_{width})^{-1/r^{\bf f}_{max}}\\\ =C_{1}L_{max}^{\bf
f}\Lambda^{\bf f}\left|{\cal V}^{\bf f}_{G}\right|(n_{width})^{-1/r^{\bf
f}_{max}}.\end{array}$ (58)

$\blacklozenge$

###### Remark 4

The expression of $C$ in (56) is conservative. From the proof, an alternative
error upper bound is in (58). More specifically,

$\begin{array}[]{lllllllllll}\left\lVert{\bf f}({\bf x})-{\bf f}^{NN}({\bf
x})\right\rVert_{p}\leq\displaystyle\sum_{f_{i,j}\in{\cal V}^{\bf
f}_{G}}L_{i,j}^{\bf f}C_{i,j}\max\\{R^{m}_{i,j},1\\}\left\lVert
f_{i,j}\right\rVert_{W^{\infty}_{m_{i,j},d_{i,j}}}(n_{width})^{-m_{i,j}/d_{i,j}}\end{array}$
(59)

Moreover, the proof suggests that the number of hidden layers in the neural
network (after all linear nodes in hidden layers are merged into neurons) is
$l^{\bf f}_{max}$. The output layer consists of all linear nodes. The width of
layer $1\leq l\leq l^{\bf f}_{max}$ in the neural network is bounded by
$n_{width}\times n_{l}$, where $n_{l}$ is the number of general nodes in the
$l$-th layer in ${\cal G}^{\bf f}$.

###### Remark 5

The edges in ${\cal G}^{{\bf f}^{NN}}$ in Theorem 2 may skip layers, which is
not in the traditional format of deep neural networks. Any compositional
function, in fact, allows a DAG in which no edges skip layers. Adding identity
functions as nodes is a way to achieve this. Shown in Figure 16(a) is the DAG
of a compositional function in which two edges skip layers,
$(f_{0,3},f_{2,3})$ and $(f_{0,4},f_{3,3})$. In Figure 16(b), three identity
functions are added as nodes to the DAG at each location where an edge skips a
layer. Under the new DAG, no edges skip layers. In Theorem 2, if ${\bf f}$ has
no edges that skip layers and if we substitute shallow neural networks for all
nodes in ${\cal V}^{\bf f}\setminus{\cal V}^{\bf f}_{I}$ (including identity
and linear nodes), then the DAG of ${\bf f}^{NN}$ in Theorem 2 has no edges
that skip layers. After merging linear nodes in ${\cal G}^{{\bf f}^{NN}}$ into
neurons, one can achieve a traditional deep neural network in which edges do
not skip layers.

Figure 16: Functions in (a) and (b), as input-output relations, are equal to
each other. Adding identity nodes, the DAG in (b) has no edge that skips
layers.

###### Corollary 2

Consider a compositional function $({\bf f},{\cal G}^{\bf f},{\cal L}^{\bf
f})$ that satisfies the same assumptions made in Theorem 2. Then, there is an
$\epsilon_{0}>0$. For any $0<\epsilon\leq\epsilon_{0}$, there always exists a
deep neural network, ${\bf f}^{NN}$, satisfying

$\begin{array}[]{lllllllllll}\left\lVert{\bf f}({\bf x})-{\bf f}^{NN}({\bf
x})\right\rVert_{p}\leq\epsilon,&{\bf x}\in[-R,R]^{d}.\end{array}$ (60)

The complexity of ${\bf f}^{NN}$ is

$\begin{array}[]{lllllllllll}n\leq C\left(L_{max}^{\bf f}\Lambda^{\bf
f}\right)^{r^{\bf f}_{max}}\left|{\cal V}^{\bf f}_{G}\right|^{r^{\bf
f}_{max}+1}\epsilon^{-r^{\bf f}_{max}},\end{array}$ (61)

where $C$ is a constant determined by $\\{d_{i,j},m_{i,j};\;\;f_{i,j}\in{\cal
V}^{\bf f}_{G}\\}$.

Proof. From Theorem 2, there exists a deep neural network, denoted by ${\bf
f}^{NN}$, that satisfy (55)-(56). Let $n_{width}$ be the smallest integer such
that

$\begin{array}[]{lllllllllll}CL_{max}^{\bf f}\Lambda^{\bf f}\left|{\cal
V}^{\bf f}_{G}\right|(n_{width})^{-1/r^{\bf f}_{max}}\leq\epsilon.\end{array}$
(62)

Then (60) holds. As the smallest integer satisfying (62), $n_{width}$
satisfies

$\begin{array}[]{lllllllllll}n_{width}\leq\left(CL_{max}^{\bf f}\Lambda^{\bf
f}\left|{\cal V}^{\bf f}_{G}\right|\right)^{r^{\bf f}_{max}}\epsilon^{-r^{\bf
f}_{max}}+1.\end{array}$ (63)

Because $C^{r^{\bf f}_{max}}$ is a constant depending on
$\\{d_{i,j},m_{i,j};\;\;f_{i,j}\in{\cal V}^{\bf f}_{G}\\}$ and $n=\left|{\cal
V}^{\bf f}_{G}\right|n_{width}$, (63) implies

$\begin{array}[]{lllllllllll}n\leq C\left(L_{max}^{\bf f}\Lambda^{\bf
f}\right)^{r^{\bf f}_{max}}\left|{\cal V}^{\bf f}_{G}\right|^{r^{\bf
f}_{max}+1}\epsilon^{-r^{\bf f}_{max}}+\left|{\cal V}^{\bf
f}_{G}\right|.\end{array}$ (64)

If $\epsilon$ is small enough, then we can double the constant $C$ and remove
the last term, $\left|{\cal V}^{\bf f}_{G}\right|$, i.e. (61) holds.
$\blacklozenge$

###### Example 5

Consider the compositional function (44) in Example 4, whose features are
given in (47). By Theorem 2, for any integer $n_{width}>0$, there exists a
deep neural network, ${\bf f}^{NN}$, such that

$\begin{array}[]{lllllllllll}\left\lVert{\bf f}({\bf x})-{\bf f}^{NN}({\bf
x})\right\rVert_{p}\leq
C_{1}d\left(1+2R+4R^{2}\right)\mbox{max}\\{(2R)^{m},1\\}(n_{width})^{-m/2},\end{array}$

for all ${\bf x}\in[-R,R]^{d}$ and all integer $m\geq 2$, where $C_{1}$ is a
constant determined by $m$. The complexity of $f^{NN}$ is $dn_{width}$. The
approximation error and the complexity depend on the dimension, $d$, linearly.
If the value of $m$ and the domain size $R$ are set to be constants, the
neural network approximation is curse-of-dimensionality free.

Given a function $f:D\subset\mathbb{R}^{d}\rightarrow\mathbb{R}$. The radius
of its range is defined by

$\begin{array}[]{lllllllllll}\left(\displaystyle\max_{{\bf x}\in D}\\{f({\bf
x})\\}-\min_{{\bf x}\in D}\\{f({\bf x})\\}\right)/2.\end{array}$ (65)

###### Theorem 3

Consider two compositional functions $({\bf f},{\cal G}^{\bf f},{\cal L}^{\bf
f})$, ${\bf f}:[-R,R]^{d}\rightarrow\mathbb{R}^{q}$, and $({\bf g},{\cal
G}^{\bf g},{\cal L}^{\bf g})$, ${\bf g}:[-R,R]^{d}\rightarrow\mathbb{R}^{q}$.
Suppose they both satisfy A1. Let ${\bf f}^{NN}$ and ${\bf g}^{NN}$ be two
neural networks with complexity $n_{1}$ and $n_{2}$, respectively. Suppose

$\begin{array}[]{lllllllllll}\left\lVert{\bf f}({\bf x})-{\bf f}^{NN}({\bf
x})\right\rVert_{p}\leq e_{1},\\\ \left\lVert{\bf g}({\bf x})-{\bf
g}^{NN}({\bf x})\right\rVert_{p}\leq e_{2},\\\ \end{array}$ (66)

for some positive numbers $e_{1}$, $e_{2}$ and for all ${\bf x}$ in the
domain.

  1. 1.

Consider ${\bf h}=a{\bf f}+b{\bf g}$, where $a,b\in\mathbb{R}$ are constants.
Then ${\bf h}^{NN}=a{\bf f}^{NN}+b{\bf g}^{NN}$ is a neural network satisfying

$\begin{array}[]{lllllllllll}\left\lVert{\bf h}({\bf x})-{\bf h}^{NN}({\bf
x})\right\rVert_{p}\leq\left|a\right|e_{1}+\left|b\right|e_{2}\end{array}$
(67)

for all ${\bf x}$ in the domain. The complexity of ${\bf h}^{NN}$ is
$n_{1}+n_{2}$.

  2. 2.

Consider $h={\bf f}^{T}{\bf g}$. Let $p=2$ in (66). Then, for any integers
$n_{width}>0$ and $m>0$, there is a deep neural network, $h^{NN}$, satisfying

$\begin{array}[]{lllllllllll}\left|h({\bf x})-h^{NN}({\bf x})\right|\\\
\leq\displaystyle\max_{{\bf x}\in[-R,R]^{d}}\\{\left\lVert{\bf f}({\bf
x})\right\rVert_{2}\\}e_{2}+\displaystyle\max_{{\bf
x}\in[-R,R]^{d}}\\{\left\lVert{\bf g}({\bf
x})\right\rVert_{2}\\}e_{1}+e_{1}e_{2}+C\Lambda
q(n_{width})^{-m/2},\end{array}$ (68)

where $C$ is a constant depending on $m$ and $q$. The parameter, $\Lambda$, is
defined as follows based on $f_{j}$ and $g_{j}$ (the $j$-th component of ${\bf
f}$ and ${\bf g}$, respectively)

$\begin{array}[]{lllllllllll}\Lambda=\displaystyle\max_{1\leq j\leq
q}\left\\{\max\\{(R_{j})^{m},1\\}(A_{j}B_{j}+A_{j}+B_{j}+2)\right\\},\\\
A_{j}=\displaystyle\max_{x}\\{\left|f_{j}({\bf
x})\right|\\},B_{j}=\displaystyle\max_{x}\\{\left|g_{j}({\bf x})\right|\\},\\\
R_{j}=\max\\{\mbox{radii of the ranges of }f_{j},g_{j}\\}.\end{array}$ (69)

The complexity of ${\bf h}^{NN}$ is $n_{1}+n_{2}+qn_{width}$.

  3. 3.

If $f$ and $g$ are scalar valued compositional functions. Suppose $g({\bf
x})\neq 0$. Consider $h=f/g$. Suppose

$\begin{array}[]{lllllllllll}e_{2}\leq\displaystyle\frac{1}{2}\displaystyle\min_{{\bf
x}\in[-R,R]^{d}}\\{\left|g({\bf x})\right|\\}.\end{array}$ (70)

Then, for any integers $n_{width}>0$ and $m>0$, there is a deep neural
network, $h^{NN}$, satisfying

$\begin{array}[]{lllllllllll}\left|h({\bf x})-h^{NN}({\bf
x})\right|\leq\displaystyle\frac{2A}{B^{2}}e_{2}+\displaystyle\frac{2}{B}e_{1}+C\Lambda(n_{width})^{-m/2},\end{array}$
(71)

where $C$ is a constant depending on $m$,

$\begin{array}[]{lllllllllll}\Lambda=\max\\{R^{m}_{1},1\\}\left(m!(A+B)\displaystyle\frac{1-(1/B)^{m+1}}{B-1}\right),\\\
A=\displaystyle\max_{{\bf x}\in[-R,R]^{d}}\\{\left|f({\bf
x})\right|\\},\;B=\displaystyle\min_{{\bf x}\in[-R,R]^{d}}\\{\left|g({\bf
x})\right|\\},\\\ R_{1}=\max\\{\mbox{radii of the ranges of
}f,g\\}.\end{array}$ (72)

The complexity of $h^{NN}$ is $n_{1}+n_{2}+n_{width}$.

Proof. The inequality (67) is obvious. From Definition 2, the last layer of
the induced DAG for $a{\bf f}^{NN}+b{\bf g}^{NN}$ consists of all linear
nodes. It does not change the complexity of the deep neural network.

To prove (2), we construct a compositional function $\psi:({\bf u},{\bf
v})\in\mathbb{R}^{q}\times\mathbb{R}^{q}\rightarrow{\bf u}^{T}{\bf
v}\in\mathbb{R}$ (Figure 17(a)). Then

$\begin{array}[]{lllllllllll}h({\bf x})=\psi({\bf f}({\bf x}),{\bf g}({\bf
x})).\end{array}$ (73)

Figure 17: (a): DAG of inner product, ${\bf u}^{T}{\bf v}$, as a compositional
function. (b) DAG of division, $u/v$, as a compositional function.

The Lipschitz constants associated with each general node in ${\cal G}^{\psi}$
(all located in the layer $l=1$) is $L_{1,j}^{\psi}=1$. It is straightforward
to show that

$\begin{array}[]{lllllllllll}\left\lVert\psi_{1,j}\right\rVert_{W^{\infty}_{m,2}}\leq(A_{j}B_{j}+A_{j}+B_{j}+2),\end{array}$
(74)

for any $m\geq 1$. From Theorem 2, there exists a deep neural network,
$\psi^{NN}$, so that

$\begin{array}[]{lllllllllll}\left|\psi(u,v)-\psi^{NN}(u,v)\right|\leq
C\Lambda q(n_{width})^{-m/2},\end{array}$ (75)

where C is a constant depending on $m$ ($d_{i,j}=2$), $\Lambda$ is defined in
(69). Define $h^{NN}=\psi^{NN}\circ(f^{NN},g^{NN})$. It is a deep neural
network. We have

$\begin{array}[]{lllllllllll}\left|h({\bf x})-h^{NN}({\bf x})\right|\\\
=\left|\psi({\bf f}({\bf x}),{\bf g}({\bf x}))-\psi^{NN}({\bf f}^{NN}({\bf
x}),{\bf g}^{NN}({\bf x}))\right|\\\ =\left|\psi({\bf f}({\bf x}),{\bf g}({\bf
x}))-\psi(f^{NN}({\bf x}),{\bf g}^{NN}({\bf x}))\right|+\left|\psi({\bf
f}^{NN}({\bf x}),g^{NN}({\bf x}))-\psi^{NN}({\bf f}^{NN}({\bf x}),{\bf
g}^{NN}({\bf x}))\right|\\\ \leq\left|{\bf f}({\bf x})^{T}{\bf g}({\bf
x})-({\bf f}^{NN}({\bf x}))^{T}{\bf g}^{NN}({\bf x})\right|+C\Lambda
q(n_{width})^{-m/2}\\\ \leq\left|{\bf f}({\bf x})^{T}{\bf g}({\bf x})-{\bf
f}({\bf x})^{T}{\bf g}^{NN}({\bf x})\right|+\left|{\bf f}({\bf x})^{T}{\bf
g}^{NN}({\bf x})-({\bf f}^{NN}({\bf x}))^{T}{\bf g}^{NN}({\bf
x})\right|+C\Lambda q(n_{width})^{-m/2}\\\ \leq\left\lVert{\bf f}({\bf
x})\right\rVert_{2}\left\lVert{\bf g}({\bf x})-{\bf g}^{NN}({\bf
x})\right\rVert_{2}+\left\lVert{\bf f}({\bf x})-{\bf f}^{NN}({\bf
x})\right\rVert_{2}\left\lVert{\bf g}^{NN}({\bf x})\right\rVert_{2}+C\Lambda
q(n_{width})^{-m/2}\\\ \leq\displaystyle\max_{\bf x}\\{\left\lVert{\bf f}({\bf
x})\right\rVert_{2}\\}e_{2}+(\displaystyle\max_{\bf x}\\{\left\lVert{\bf
g}({\bf x})\right\rVert_{2}\\}+e_{2})e_{1}+C\Lambda
q(n_{width})^{-m/2}.\end{array}$ (76)

The proof of (3) is similar to the idea shown above but for $q=1$. We
construct a compositional function
$\psi:(u,v)\in\mathbb{R}\times\mathbb{R}\rightarrow u/v\in\mathbb{R}$. This is
a compositional function with a single general node and two input nodes
(Figure 17(b)). Then

$\begin{array}[]{lllllllllll}h({\bf x})=\psi(f({\bf x}),g({\bf
x})).\end{array}$ (77)

A Lipschitz constant associated with the single general node in ${\cal
G}^{\psi}$ is $L_{1,1}=1$. Skipping the proof that is based on typical
algebraic derivations, we claim that the norm of $\psi$ satisfies

$\begin{array}[]{lllllllllll}A=\displaystyle\max_{\bf x}\\{\left|f({\bf
x})\right|\\},B=\displaystyle\min_{\bf x}\\{\left|g({\bf x})\right|\\},\\\
\left\lVert\psi\right\rVert_{W^{\infty}_{m,2}}\leq\left(m!(A+B)\displaystyle\frac{1-(1/B)^{m+1}}{B-1}\right),\\\
\end{array}$ (78)

for any $m\geq 1$. From Theorem 2, there exists a deep neural network,
$\psi^{NN}$, so that

$\begin{array}[]{lllllllllll}\left|\psi(u,v)-\psi^{NN}(u,v)\right|\leq
C\Lambda(n_{width})^{-m/2},\end{array}$ (79)

where C is a constant depending on $m$, $\Lambda$ is defined in (72). Define
$h^{NN}=\psi^{NN}\circ(f^{NN},g^{NN})$. We have

$\begin{array}[]{lllllllllll}\left|h({\bf x})-h^{NN}({\bf x})\right|\\\
=\left|\psi(f({\bf x}),g({\bf x}))-\psi^{NN}(f^{NN}({\bf x}),g^{NN}({\bf
x}))\right|\\\ =\left|\psi(f({\bf x}),g({\bf x}))-\psi(f^{NN}({\bf
x}),g^{NN}({\bf x}))\right|+\left|\psi(f^{NN}({\bf x}),g^{NN}({\bf
x}))-\psi^{NN}(f^{NN}({\bf x}),g^{NN}({\bf x}))\right|\\\ \leq\left|f({\bf
x})/g({\bf x})-f^{NN}({\bf x})/g^{NN}({\bf
x})\right|+C\Lambda(n_{width})^{-m/2}\\\ \leq\left|f({\bf x})/g({\bf
x})-f({\bf x})/g^{NN}({\bf x})\right|+\left|f({\bf x})/g^{NN}({\bf
x})-f^{NN}({\bf x})/g^{NN}({\bf x})\right|+C\Lambda(n_{width})^{-m/2}\\\
\leq\left|f({\bf x})\right|\displaystyle\frac{\left|g({\bf x})-g^{NN}({\bf
x})\right|}{\left|g({\bf x})g^{NN}({\bf
x})\right|}+\displaystyle\frac{\left|f({\bf x})-f^{NN}({\bf
x})\right|}{\left|g^{NN}({\bf
x})\right|}+C\Lambda(n_{width})^{-m/2}.\end{array}$ (80)

Because of (70), we know

$\begin{array}[]{lllllllllll}\left|g^{NN}({\bf
x})\right|\geq\displaystyle\frac{B}{2}.\end{array}$ (81)

Therefore,

$\begin{array}[]{lllllllllll}\left|h({\bf x})-h^{NN}({\bf
x})\right|\leq\displaystyle\frac{2A}{B^{2}}e_{2}+\displaystyle\frac{2}{B}e_{1}+C\Lambda(n_{width})^{-m/2}.\end{array}$
(82)

$\blacklozenge$

##  5 Ordinary differential equations

In the following, we say that a function is $C^{k}$ if all derivatives of
order less than or equal to $k$ are continuous in the domain. Consider a
system of ordinary differential equations (ODEs)

$\begin{array}[]{lllllllllll}\dot{\bf x}={\bf f}({\bf x}),&{\bf
x}\in\mathbb{R}^{d},{\bf f}({\bf x})\in\mathbb{R}^{d},t\in[0,T].\end{array}$
(83)

Without loss of generality, ${\bf f}$ in (83) does not explicitly depend on
$t$. If the right-hand side of the ODE is a function of $(t,x)$, one can add a
new state variable to convert the equation to a time-invariant one. Let
${\bm{\phi}}(t;{\bf x}_{0})$ represent the solution of (83) satisfying ${\bf
x}(0)={\bf x}_{0}$. In this section, we study the complexity of deep neural
networks in the approximation of the function ${\bm{\phi}}(T;\cdot):{\bf
x}\rightarrow{\bm{\phi}}(T;{\bf x})$. We assume that ${\bf f}$, the right-hand
side of (83), is a compositional function that satisfies A1. After
integration, the compositional structure of ${\bm{\phi}}(t;{\bf x})$ becomes
unknown.

The solution of an ODE can be approximated using the Euler method. Let
$ELR:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ represent the operator of the
Euler method, i.e.,

$\begin{array}[]{lllllllllll}ELR({\bf x})={\bf x}+h{\bf f}({\bf
x}).\end{array}$ (84)

Let $K>0$ be a positive integer and $h=T/K$. Then

$\begin{array}[]{lllllllllll}{\bm{\phi}}(T;{\bf x})\\\
\approx\overbrace{ELR\circ\cdots ELR\circ ELR}^{K}({\bf x})\\\
=(ELR(\cdot))^{K}({\bf x}).\end{array}$ (85)

As a compositional function, $ELR$ has a DAG, whose framework is shown in
Figure 18. The first box on the left represents the layer of input nodes. The
blue box in the middle contains all nodes in ${\cal V}^{\bf f}\setminus{\cal
V}^{\bf f}_{I}$ and their edges. The box on the right consists of output
nodes, which are all linear nodes. Applying Definition 4, $(ELR(\cdot))^{K}$
is a compositional function with an induced DAG.

Figure 18: DAG structure of an Euler iteration

###### Theorem 4

Consider the ODE (83) in which $({\bf f},{\cal G}^{\bf f},{\cal L}^{\bf f})$
is a compositional function satisfying A1. Its features are defined in
Definition 7. Assume that all nodes in ${\cal G}^{\bf f}$ are $C^{1}$. Suppose
$D^{\bf f}$ is a closed set such that ${\bm{\phi}}(t;{\bf x})\in[-R,R]^{d}$
whenever ${\bf x}\in D^{\bf f}$ and $t\in[0,T]$. Let $1\leq p\leq\infty$ be a
real number.

  1. 1.

There is a constant $C$ so that, for any integer $n_{width}>0$, there exists a
deep neural network,
${\bm{\phi}}^{NN}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$, satisfying

$\begin{array}[]{lllllllllll}\left\lVert{\bm{\phi}}(T;{\bf
x})-{\bm{\phi}}^{NN}({\bf x})\right\rVert_{p}\leq C(n_{width})^{-1/r^{\bf
f}_{max}},&{\bf x}\in D^{\bf f}.\end{array}$ (86)

  2. 2.

Let $\alpha\in\mathbb{R}$ be the constant so that a Lipschitz constant of
$ELR$ has the form $(1+h\alpha)$. The constant, $C$, in (86) satisfies

$\begin{array}[]{lllllllllll}C=C_{1}\left(\max\\{e^{\alpha
T},1\\}\right)TL_{max}^{\bf f}\Lambda^{\bf f}\left|{\cal V}^{\bf
f}_{G}\right|+Ae^{BT}T,\\\ A=\displaystyle\max_{{\bf
x}\in[-R,R]^{d}}\\{\left\lVert{\bf f}({\bf x})\right\rVert_{p}\\},\\\
B=\displaystyle\max_{{\bf
x}\in[-R,R]^{d}}\left\\{\left\lVert\frac{\partial{\bf f}}{\partial{\bf
x}}({\bf x})\right\rVert_{p}\right\\},\end{array}$ (87)

where $C_{1}$ is a constant determined by
$\\{d_{i,j},m_{i,j};\;f_{i,j}\in{\cal V}^{\bf f}_{G}\\}$.

  3. 3.

The complexity of ${\bm{\phi}}^{NN}$ is bounded by

$\begin{array}[]{lllllllllll}n\leq\left((n_{width})^{1/r^{\bf
f}_{max}}+1\right)n_{width}\left|{\cal V}^{\bf f}_{G}\right|.\end{array}$ (88)

###### Remark 6

The error upper bound in (86)-(87) increases at a polynomial rate with respect
to the features of ${\bf f}$. It also depends on the terms $e^{\alpha T}$ and
$e^{BT}$. If the Euler method is stable [9], then $\alpha<0$. The value of
$e^{\alpha T}$ is always bounded. For a stable system, the error estimation
using $e^{BT}$ is conservative. In this case the error does not increase
exponentially with $T$ if a stable Euler method is applied.

Proof of Theorem 4. For any integer $n_{width}>0$, from Theorem 2, there
exists a deep neural network approximation of ${\bf f}$ satisfying

$\begin{array}[]{lllllllllll}\left\lVert{\bf f}({\bf x})-{\bf f}^{NN}({\bf
x})\right\rVert_{p}\leq C_{1}L^{\bf f}_{max}\Lambda^{\bf f}\left|{\cal V}^{\bf
f}_{G}\right|(n_{width})^{-1/r^{\bf f}_{max}},\end{array}$ (89)

for some constant $C_{1}$ determined by $d_{i,j}$ and $m_{i,j}$. The
complexity of the neural network is bounded by $n_{width}\left|{\cal V}^{\bf
f}_{G}\right|$. Let $ELR^{NN}$ be the neural network obtained by substituting
${\bf f}^{NN}$ for $f$. Then,

$\begin{array}[]{lllllllllll}\left\lVert ELR({\bf x})-ELR^{NN}({\bf
x})\right\rVert_{p},\\\ =h\left\lVert{\bf f}({\bf x})-{\bf f}^{NN}({\bf
x})\right\rVert_{p},\\\ \leq hC_{1}L^{\bf f}_{max}\Lambda^{\bf f}\left|{\cal
V}^{\bf f}_{G}\right|(n_{width})^{-1/r^{\bf f}_{max}}.\end{array}$ (90)

Define

$\begin{array}[]{lllllllllll}{\bm{\phi}}^{NN}=(ELR^{NN}(\cdot))^{K}.\end{array}$
(91)

Applying Proposition 4, we have

$\begin{array}[]{lllllllllll}\left\lVert(ELR(\cdot))^{K}({\bf
x})-\phi^{NN}({\bf x})\right\rVert_{p}\\\
\leq\displaystyle\frac{(1+h\alpha)^{K}-1}{(1+h\alpha)-1}hC_{1}L^{\bf
f}_{max}\Lambda^{\bf f}\left|{\cal V}^{\bf f}_{G}\right|(n_{width})^{-1/r^{\bf
f}_{max}}\\\
\leq\left((1+h\alpha)^{K-1}+(1+h\alpha)^{K-2}+\cdots+1\right)hC_{1}L^{\bf
f}_{max}\Lambda^{\bf f}\left|{\cal V}^{\bf f}_{G}\right|(n_{width})^{-1/r^{\bf
f}_{max}}\\\ \leq
K\left(\max\\{(1+\frac{T}{K}\alpha)^{K-1},1\\}\right)\displaystyle\frac{T}{K}C_{1}L^{\bf
f}_{max}\Lambda^{\bf f}\left|{\cal V}^{\bf f}_{G}\right|(n_{width})^{-1/r^{\bf
f}_{max}}\\\ \leq C_{1}\left(\max\\{e^{\alpha T},1\\}\right)TL_{max}^{\bf
f}\Lambda^{\bf f}\left|{\cal V}^{\bf f}_{G}\right|(n_{width})^{-1/r^{\bf
f}_{max}}.\end{array}$ (92)

On the other hand, it is well known (see, for instance, [9]) that the global
error of the Euler method satisfies

$\begin{array}[]{lllllllllll}\left\lVert{\bm{\phi}}(T;{\bf x})-ELR^{K}({\bf
x})\right\rVert_{p}\leq Ae^{BT}\displaystyle\frac{T}{K},&{\bf x}\in D^{\bf
f}.\end{array}$ (93)

From Proposition 5 and the inequalities (92) and (93), we have

$\begin{array}[]{lllllllllll}\left\lVert{\bm{\phi}}(T;{\bf
x})-{\bm{\phi}}^{NN}({\bf x})\right\rVert_{p}\leq C_{1}\left(\max\\{e^{\alpha
T},1\\}\right)TL_{max}^{\bf f}\Lambda^{\bf f}\left|{\cal V}^{\bf
f}_{G}\right|(n_{width})^{-1/r^{\bf f}_{max}}+Ae^{BT}TK^{-1},&{\bf x}\in
D^{\bf f}.\end{array}$ (94)

Substituting $K$ by $K={\rm ceiling}((n_{width})^{1/r^{\bf f}_{max}})$, where
the value of ${\rm ceiling}(z)$ is the smallest integer that is greater than
or equal to $z$, we achieve the inequalities in (86)-(87) because

$\begin{array}[]{lllllllllll}z\leq{\rm ceiling}(z)\leq z+1,&\mbox{for all
}z\geq 0.\end{array}$ (95)

The calculation of the complexity is straightforward. There are a total of $K$
iterations in the Euler approximation. In each ${\cal G}^{ELR}$, there is one
copy of ${\bf f}$, which is substituted by ${\bf f}^{NN}$, a neural network
whose complexity is $n_{width}\left|{\cal V}^{\bf f}_{G}\right|$. Thus, the
total number of neurons in ${\bm{\phi}}^{NN}$ is $Kn_{width}\left|{\cal
V}^{\bf f}_{G}\right|$, which implies (88) because $K\leq(n_{width})^{1/r^{\bf
f}_{max}}+1$. $\blacklozenge$

###### Example 6

Consider Lorenz-96 system [17],

$\displaystyle\dot{\bf x}$ $\displaystyle=$ $\displaystyle{\bf f}({\bf x}),$
(96)

where the vector field ${\bf f}$ is the compositional function (44) in Example
4. For a suitable choice of the constant $F$, system (96) is chaotic; thus
trajectories are bounded. Choose a sufficiently large $R$ such that ${\bf
x}(t)\in[-R,R]^{d}$ for all $t\in[0,T]$. By Theorem 4 and the features of
${\bf f}$ given in (47), for any integers $n_{width}>0$ and $m\geq 2$, there
exists a deep neural network,
${\bm{\phi}}^{NN}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$, satisfying

$\begin{array}[]{lllllllllll}\left\lVert{\bm{\phi}}(T;{\bf
x})-{\bm{\phi}}^{NN}({\bf x})\right\rVert_{\infty}\leq
C(n_{width})^{-m/2},\end{array}$ (97)

where

$\begin{array}[]{lllllllllll}C=C_{1}Td(1+2R+4R^{2})\max\\{e^{\alpha
T},1\\}\mbox{max}\\{(2R)^{m},1\\}+Ae^{BT}T,\\\ A=\displaystyle\max_{{\bf
x}\in[-R,R]^{d}}\\{\left\lVert{\bf f}({\bf x})\right\rVert_{\infty}\\}\leq
2R^{2}+R+F,\\\ B=\displaystyle\max_{{\bf
x}\in[-R,R]^{d}}\left\\{\left\lVert\frac{\partial{\bf f}}{\partial{\bf
x}}({\bf x})\right\rVert_{\infty}\right\\}\leq 1+4R,\\\ \alpha\leq B,\\\
C_{1}:\mbox{a constant determined by}\ $m$.\end{array}$ (98)

Moreover, the complexity of ${\bm{\phi}}^{NN}$ is bounded by

$\begin{array}[]{lllllllllll}n\leq
d\left((n_{width})^{m/2}+1\right)n_{width}.\end{array}$ (99)

##  6 Optimal control

Let $D$ be a bounded and closed set in $\mathbb{R}^{d}$. Let $V({\bf x},{\bf
u}):D\times\mathbb{R}^{q}\rightarrow\mathbb{R}$ be a cost function, where
${\bf x}$ is the state and ${\bf u}$ is the control input. Suppose that $V$ is
$C^{2}$. Let $H({\bf x},{\bf u})$ represent the Hessian of $V$ with respect to
${\bf u}$, i.e.

$\begin{array}[]{lllllllllll}H({\bf x},{\bf
u})=\displaystyle\frac{\partial^{2}V}{\partial{\bf u}^{2}}.\end{array}$ (100)

If $H({\bf x},{\bf u})$ is positive definite, then $V$ is a convex function
for every fixed ${\bf x}$. Consider the problem of optimization

$\begin{array}[]{lllllllllll}\displaystyle\min_{\bf u}V({\bf x},{\bf
u}).\end{array}$ (101)

Given any ${\bf x}\in D$, (101) has a unique solution. The optimal control is
denoted by ${\bf u}^{\ast}({\bf x})$. The minimum cost is called the value
function,

$\begin{array}[]{lllllllllll}V^{\ast}({\bf x})=V({\bf x},{\bf u}^{\ast}({\bf
x})).\end{array}$ (102)

Because of the convexity and the smoothness of $V$, it can be proved that
${\bf u}^{\ast}({\bf x})$ is continuous and the set of control inputs,

$\begin{array}[]{lllllllllll}\\{{\bf u}^{\ast}({\bf x});\;{\bf x}\in
D\\},\end{array}$ (103)

is bounded. Its diameter is denoted by

$\begin{array}[]{lllllllllll}\gamma=\displaystyle\max_{{\bf x}\in
D}\\{u^{\ast}(x)\\}.\end{array}$ (104)

Let ${\bf u}_{0}\in\mathbb{R}^{m}$ be any fixed point satisfying

$\begin{array}[]{lllllllllll}\left\lVert{\bf u}_{0}-{\bf u}^{\ast}({\bf
x})\right\rVert_{2}\leq\gamma,&{\bf x}\in D.\end{array}$ (105)

In the following, we apply an iterative algorithm starting from ${\bf u}_{0}$
in the searching for ${\bf u}^{\ast}({\bf x})$. It is a fact that will become
clear later that the following set is invariant under the searching process:

$\begin{array}[]{lllllllllll}{\cal U}=\\{{\bf
u}\in\mathbb{R}^{m};\;\left\lVert{\bf u}-{\bf u}_{0}\right\rVert_{2}\leq
2\gamma\\}.\end{array}$ (106)

In the following, we prove an error upper bound for the approximation of
$u^{\ast}$ using neural network.

###### Theorem 5

Suppose $V({\bf x},{\bf u}):D\times{\cal
U}\subset\mathbb{R}^{d}\times\mathbb{R}^{q}\rightarrow\mathbb{R}$ is a $C^{2}$
function. Assume that $H({\bf x},{\bf u})$ is positive definite in
$D\times{\cal U}$. Let $\lambda_{min}>0$ and $\lambda_{max}>0$ be the lower
and upper bounds of the eigenvalues of $H({\bf x},{\bf u})$ in $D\times{\cal
U}$. Suppose $V^{NN}$ is a neural network satisfying

$\begin{array}[]{lllllllllll}\left|V({\bf x},{\bf u})-V^{NN}({\bf x},{\bf
u})\right|\leq e_{1},&({\bf x},{\bf u})\in D\times{\cal U},\end{array}$ (107)

for some $e_{1}>0$.

  1. 1.

Given any integer $K>0$ and real number $h>0$, there exists a deep neural
network, ${\bf u}^{\ast NN}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{q}$, that
approximates ${\bf u}^{\ast}$ with the following error upper bound

$\begin{array}[]{lllllllllll}\left\lVert{\bf u}^{\ast NN}({\bf x})-{\bf
u}^{\ast}({\bf x})\right\rVert_{2}\leq\gamma
L^{K}+C_{1}\sqrt{q}Kh+2\sqrt{q}Kh^{-1}e_{1},&{\bf x}\in D,\end{array}$ (108)

where $\gamma$ is the diameter of the set (103),
$L=1-\lambda_{min}/\max\\{1,2\lambda_{max}\\}$, and

$\begin{array}[]{lllllllllll}C_{1}=\displaystyle\max_{{\bf x}\in D,{\bf
u}\in{\cal U}}\left\\{\displaystyle\frac{\partial^{2}V}{\partial
u_{j}^{2}}({\bf x},{\bf u})\right\\},&1\leq j\leq q.\end{array}$ (109)

  2. 2.

Let $n_{1}$ be the complexity of $V^{NN}$. The complexity of ${\bf u}^{\ast
NN}$ satisfies

$\begin{array}[]{lllllllllll}n\leq 2n_{1}qK.\end{array}$ (110)

Proof. Define a function

$\begin{array}[]{lllllllllll}{\bm{\psi}}({\bf x},{\bf u})={\bf
u}-\beta\displaystyle\frac{\partial V}{\partial{\bf u}}({\bf x},{\bf
u}),\end{array}$ (111)

where $\beta>0$ is chosen so that the matrix norm satisfies

$\begin{array}[]{lllllllllll}\left\lVert
I-\beta\displaystyle\frac{\partial^{2}V}{\partial{\bf
u}^{2}}\right\rVert_{2}\leq L<1,&{\bf x}\in D,{\bf u}\in{\cal U},\end{array}$
(112)

for some constant $L$. This is always possible because ${\cal U}$ is bounded
and $H({\bf x},{\bf u})$ is positive definite and continuous. For instance,
one can chose

$\begin{array}[]{lllllllllll}\beta=\displaystyle\frac{1}{\max\\{1,2\lambda_{max}\\}},\end{array}$
(113)

In this case, we can prove that

$\begin{array}[]{lllllllllll}L=1-\displaystyle\frac{\lambda_{min}}{\max\\{1,2\lambda_{max}\\}}\end{array}$
(114)

satisfies (112). By the contraction mapping theorem, for every ${\bf x}\in D$,
there is a fixed point ${\bf u}^{\ast}({\bf x})$ such that

$\begin{array}[]{lllllllllll}{\bm{\psi}}({\bf x},{\bf u}^{\ast}({\bf x}))={\bf
u}^{\ast}({\bf x}).\end{array}$ (115)

By the definition of ${\bm{\psi}}$ in (111), this implies that

$\begin{array}[]{lllllllllll}\displaystyle\frac{\partial V}{\partial{\bf
u}}({\bf x},{\bf u}^{\ast}({\bf x}))=0,\end{array}$ (116)

i.e., the fixed point is the optimal control. From Proposition 2, for any
integer $K>0$, we have

$\begin{array}[]{lllllllllll}\left|\left({\bm{\psi}}({\bf
x},\cdot)\right)^{K}({\bf u}_{0})-{\bf u}^{\ast}({\bf x})\right|\\\
=\left|\left({\bm{\psi}}({\bf x},\cdot)\right)^{K}({\bf
u}_{0})-\left({\bm{\psi}}({\bf x},\cdot)\right)^{K}({\bf u}^{\ast}({\bf
x}))\right|\\\ \leq L^{K}\left\lVert{\bf u}_{0}-{\bf u}^{\ast}({\bf
x})\right\rVert_{2}\\\ \leq\gamma L^{K}.\end{array}$ (117)

This implies that $\left({\bm{\psi}}({\bf x},\cdot)\right)^{K}({\bf
u}_{0})\in{\cal U}$. Let ${\bm{\psi}}^{NN}({\bf x},{\bf u})$ be a deep neural
network approximation (to be constructed) of ${\bm{\psi}}$ with an error bound

$\begin{array}[]{lllllllllll}\left\lVert{\bm{\psi}}({\bf x},{\bf
u})-{\bm{\psi}}^{NN}({\bf x},{\bf u})\right\rVert_{2}\leq e_{2}.\end{array}$
(118)

From Proposition 4,

$\begin{array}[]{lllllllllll}\left\lVert\left({\bm{\psi}}({\bf
x},\cdot)\right)^{K}({\bf u}_{0})-\left({\bm{\psi}}^{NN}({\bf
x},\cdot)\right)^{K}({\bf u}_{0})\right\rVert_{2}\\\
\leq\displaystyle\frac{L^{K}-1}{L-1}e_{2}.\end{array}$ (119)

The inequalities (117) and (119) and Proposition 5 imply

$\begin{array}[]{lllllllllll}\left|\left({\bm{\psi}}^{NN}({\bf
x},\cdot)\right)^{K}({\bf u}_{0})-{\bf u}^{\ast}({\bf x})\right|\\\ \leq\gamma
L^{K}+\displaystyle\frac{L^{K}-1}{L-1}e_{2}.\end{array}$ (120)

In the next, we construct ${\bm{\psi}}^{NN}$ and derive $e_{2}$. Let $h>0$ be
a step size for finite difference. Then

$\begin{array}[]{lllllllllll}\left|V_{u_{j}}-\displaystyle\frac{1}{h}\left(V(\cdots
u_{j}+h\cdots)-V(\cdots u_{j}\cdots)\right)\right|\leq C_{1}h,&1\leq j\leq
q,\end{array}$ (121)

where

$\begin{array}[]{lllllllllll}C_{1}=\displaystyle\max_{x\in D,u\in{\cal
U}}\left\\{\displaystyle\frac{\partial^{2}V}{\partial u_{j}^{2}}({\bf x},{\bf
u})\right\\},&1\leq j\leq q.\end{array}$ (122)

Define

$\begin{array}[]{lllllllllll}\tilde{\bm{\psi}}({\bf x},{\bf u})={\bf
u}-\beta\left[\begin{array}[]{ccc}\displaystyle\frac{1}{h}\left(V(\cdots
u_{1}+h\cdots)-V(\cdots u_{1}\cdots)\right)\\\ \vdots\\\
\displaystyle\frac{1}{h}\left(V(\cdots u_{j}+h\cdots)-V(\cdots
u_{j}\cdots)\right).\\\ \vdots\end{array}\right]\end{array}$ (123)

Then

$\begin{array}[]{lllllllllll}\left\lVert{\bm{\psi}}({\bf x},{\bf
u})-\tilde{\bm{\psi}}({\bf x},{\bf u})\right\rVert_{2}\leq\beta
C_{1}\sqrt{q}h.\end{array}$ (124)

By assumption, $V^{NN}$ is a deep neural network that approximates $V$
satisfying

$\begin{array}[]{lllllllllll}\left|V({\bf x},{\bf u})-V^{NN}({\bf x},{\bf
u})\right|\leq e_{1}.\end{array}$ (125)

We define ${\bm{\psi}}^{NN}$ by substituting $V^{NN}$ for $V$ in
$\tilde{\bm{\psi}}$. Then

$\begin{array}[]{lllllllllll}\left\lVert\tilde{\bm{\psi}}({\bf x},{\bf
u})-{\bm{\psi}}^{NN}({\bf x},{\bf u})\right\rVert_{2}\leq
2\displaystyle\frac{\beta}{h}\sqrt{q}e_{1}.\end{array}$ (126)

From Proposition 5, (124) and (126) imply

$\begin{array}[]{lllllllllll}\left\lVert{\bm{\psi}}({\bf x},{\bf
u})-{\bm{\psi}}^{NN}({\bf x},{\bf u})\right\rVert_{2}\\\ \leq\beta
C_{1}\sqrt{q}h+2\displaystyle\frac{\beta}{h}\sqrt{q}e_{1}.\end{array}$ (127)

Using the right side of the above inequality as $e_{2}$, (120) implies

$\begin{array}[]{lllllllllll}\left\lVert\left({\bm{\psi}}^{NN}({\bf
x},\cdot)\right)^{K}({\bf u}_{0})-{\bf u}^{\ast}({\bf x})\right\rVert_{p}\\\
\leq\gamma L^{K}+\displaystyle\frac{L^{K}-1}{L-1}\left(\beta
C_{1}\sqrt{q}h+2\displaystyle\frac{\beta}{h}\sqrt{q}e_{1}\right)\\\ \leq\gamma
L^{K}+K\left(\beta
C_{1}\sqrt{q}h+2\displaystyle\frac{\beta}{h}\sqrt{q}e_{1}\right),&(\mbox{because
}L<1)\\\ \leq\gamma L^{K}+C_{1}\sqrt{q}Kh+2\sqrt{q}Kh^{-1}e_{1},\\\
\end{array}$ (128)

The parameter $\beta$ is removed from the inequality because $\beta\leq 1$. If
we define

$\begin{array}[]{lllllllllll}{\bf u}^{\ast NN}({\bf
x}):=\left({\bm{\psi}}^{NN}({\bf x},\cdot)\right)^{K},\end{array}$ (129)

then (128) is equivalent to (108). From the structure of $\tilde{\bm{\psi}}$,
we know that the complexity of ${\bf u}^{\ast NN}$ is bounded by

$\begin{array}[]{lllllllllll}2n_{1}qK.\end{array}$ (130)

$\blacklozenge$

Consider a control system

$\begin{array}[]{lllllllllll}\dot{\bf x}={\bf f}({\bf x},{\bf u}),&{\bf x}\in
D\subset\mathbb{R}^{d},{\bf u}\in\mathbb{R}^{q},t\in[0,T],\end{array}$ (131)

where $D\subset\mathbb{R}^{d}$ is a bounded closed set. We assume a zero-order
hold (ZOH) control input function. Specifically, given any positive integer
$N_{t}>0$. Let ${\it\Delta}t=T/N_{t}$ and $t_{k}=k{\it\Delta}t$ for $0\leq
k\leq N_{t}$. Then the control input ${\bf u}(t)$ is a step function that
takes a constant value in each time interval $[t_{k-1},t_{k}]$. Let
${\bm{\phi}}(t;{\bf u}(\cdot),{\bf x}_{0})$ be the trajectory of the control
system (131) with the initial condition ${\bf x}(0)={\bf x}_{0}$ and a step
function ${\bf u}(t)$ as the control input. For a fixed ${\it\Delta}t$, we can
treat ${\bf u}(t)$ as a long vector $U\in\mathbb{R}^{qN_{t}}$, where
$U=\left[\begin{array}[]{rrrrrrrrrrrrrrrrrrrr}{\bf u}_{1}^{T}&{\bf
u}_{2}^{T}&\cdots&{\bf u}_{N_{t}}^{T}\end{array}\right]^{T}$ and ${\bf u}_{k}$
is the value of ${\bf u}(t)$, $t\in[t_{k-1},t_{k}]$. Define

$\begin{array}[]{lllllllllll}\begin{aligned} \Phi({\bf
x},U)&={\bm{\phi}}(T;{\bf u}(\cdot),{\bf x})\\\
&={\bm{\phi}}({\it\Delta}t;{\bf
u}_{N_{t}},\cdot)\circ{\bm{\phi}}({\it\Delta}t;{\bf
u}_{N_{t}-1},\cdot)\circ\cdots\circ{\bm{\phi}}({\it\Delta}t;{\bf u}_{1},{\bf
x}),&{\bf x}\in D.\end{aligned}\end{array}$ (132)

If $f({\bf x},{\bf u})$ is $C^{2}$ in $({\bf x},{\bf u})$, then $\Phi({\bf
x},U)$ is a $C^{2}$ function of $({\bf x},U)$. Let
$\Psi:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be a $C^{2}$ function. Define the
cost function as follows:

$\begin{array}[]{lllllllllll}J({\bf x},U)=\Psi\circ\Phi({\bf
x},U).\end{array}$ (133)

The problem of ZOH optimal control is

$\begin{array}[]{lllllllllll}\displaystyle\min_{U\in\mathbb{R}^{qN_{t}}}J({\bf
x},U).\end{array}$ (134)

Given any ${\bf x}\in D$, let $U^{\ast}({\bf x})$ represent the optimal
control. Let ${\cal U}\subset\mathbb{R}^{qN_{t}}$ be the set defined in (106)
where ${\bf u}$ is replaced by $U$. Suppose ${\bf f}({\bf x},{\bf u})$ in
(131) is defined for all ${\bf x}\in[-R,R]^{d}$ where $R$ is large enough so
that

$\begin{array}[]{lllllllllll}{\bm{\phi}}({\it\Delta}t;{\bf
u}_{k},\cdot)\circ{\bm{\phi}}({\it\Delta}t;{\bf
u}_{k-1},\cdot)\circ\cdots\circ{\bm{\phi}}({\it\Delta}t;{\bf u}_{1},{\bf
x})\in[-R,R]^{d},&1\leq k\leq N_{t},\end{array}$ (135)

for all $U\in{\cal U}$ and ${\bf x}\in D$. For the simplicity of derivation in
the following theorem, we assume ${\it\Delta}t\leq 2$.

###### Theorem 6

Suppose that ${\bf f}$ in the control system (131) and $\Psi$ in the cost
function (133) are both compositional functions that satisfy A1. Assume that
all nodes in ${\cal G}^{\bf f}$ and ${\cal G}^{\Psi}$ are $C^{2}$. Assume that
the Hession of $J({\bf x},U)$ with respect to $U$ is positive definite for all
$({\bf x},U)\in D\times{\cal U}$. Let $r_{max}=\max\\{r^{\bf
f}_{max},r^{\Psi}_{max}\\}$ and $\gamma$ be the diameter of ${\cal U}$. Then,
for any $\epsilon>0$, there exists a deep neural network, $U^{\ast NN}$ that
approximates $U^{\ast}$. The estimation error is bounded by

$\begin{array}[]{lllllllllll}\left\lVert U^{\ast NN}({\bf x})-U^{\ast}({\bf
x})\right\rVert_{2}\leq 3\epsilon,&{\bf x}\in D.\end{array}$ (136)

The complexity of $U^{\ast NN}$ is bounded by

$\begin{array}[]{lllllllllll}n\leq C\left(q(\left|{\cal V}^{\bf
f}_{G}\right|+\left|{\cal
V}^{\Psi}_{G}\right|)\right)^{(r_{max}+1+r_{max}/r^{\bf
f}_{max})}\epsilon^{-(4r_{max}+1+4r_{max}/r^{\bf f}_{max})}\end{array}$ (137)

for some constant $C>0$.

###### Remark 7

The inequality (137) is a simplified version that contains only three
explicitly presented parameters, $q$, ${\cal V}^{\bf f}_{G}$ and ${\cal
V}^{\Psi}_{G}$. For fixed ${\it\Delta}t\leq 2$, the constant $C$ in (137)
depends on $N_{t}$, $d_{i,j}^{\bf f}$, $d_{i,j}^{\Psi}$ $m_{i,j}^{\bf f}$,
$m_{i,j}^{\Psi}$, $L^{\bf f}_{max}$, $L^{\Psi}_{max}$, $\Lambda^{\bf
f}_{max}$, $\Lambda^{\Psi}_{max}$, the Lipschitz constants of ${\bf f}$,
$\Psi$ and ${\bm{\phi}}({\it\Delta}t;\cdot,\cdot)$ with respect to ${\bf x}$
for $({\bf x},{\bf u})\in D\times{\cal U}$, the norms of ${\bf f}$ and its
Jacobian, the eigenvalues and diagonal entries of the Hession matrix of
$J({\bf x},U)$, and the diameter of ${\cal U}$. We avoid showing an explicit
expression of $C$ as a function of these parameters because such a formula
would be too long. However, following the proof, an algebraic expression of
the complexity upper bound in terms of all these parameters can be derived in
detail if needed.

Proof. Suppose we can find a deep neural network, $J^{NN}({\bf x},U)$ (to be
found later), that approximates $J({\bf x},U)$ with an error upper bound
$e_{1}$, i.e.,

$\begin{array}[]{lllllllllll}\left|J^{NN}({\bf x},U)-J({\bf x},U)\right|\leq
e_{1},&{\bf x}\in D,U\in{\cal U}.\end{array}$ (138)

From Theorem 5, there is a deep neural network, $U^{\ast NN}$, that
approximates the optimal control $U^{\ast}$ with an error upper bound

$\begin{array}[]{lllllllllll}\left\lVert U^{\ast NN}({\bf x})-U^{\ast}({\bf
x})\right\rVert_{2}\leq\gamma
L^{K}+C_{1}\sqrt{qN_{t}}Kh+2\sqrt{qN_{t}}Kh^{-1}e_{1},&{\bf x}\in
D,\end{array}$ (139)

where $0<L<1$ is a constant determined by the eigenvalues of the Hession of
$J({\bf x},U)$, $\gamma$ is the diameter of the set $\\{U^{\ast}({\bf x}),{\bf
x}\in D\\}$ and $C_{1}$ depends on the diagonal of the Hession of $J({\bf
x},U)$. Given any $\epsilon>0$. For the first term to be bounded by
$\epsilon$, we need $\gamma L^{K}\leq\epsilon$. This is obvious if
$\epsilon\geq\gamma$, because $L<1$. If $\epsilon<\gamma$, $\gamma
L^{K}=\epsilon$ implies

$\begin{array}[]{lllllllllll}K=\displaystyle\frac{\ln\displaystyle\frac{\gamma}{\epsilon}}{\ln\displaystyle\frac{1}{L}}\leq\left(\ln\displaystyle\frac{1}{L}\right)^{-1}\gamma\displaystyle\frac{1}{\epsilon}\end{array}$
(140)

We can choose

$\begin{array}[]{lllllllllll}K=\bar{C}_{1}\epsilon^{-1}\end{array}$ (141)

for some constant $\bar{C}_{1}>0$ that is determined by $\gamma$ and the
eigenvalues of the Hessian of $J({\bf x},U)$. For the second term in (139) to
be bounded by $\epsilon$, we have

$\begin{array}[]{lllllllllll}C_{1}\sqrt{qN_{t}}Kh=C_{1}\bar{C}_{1}\sqrt{qN_{t}}\epsilon^{-1}h\leq\epsilon.\end{array}$
(142)

We choose

$\begin{array}[]{lllllllllll}h=\displaystyle\frac{\bar{C}_{2}}{\sqrt{qN_{t}}}\epsilon^{2}\end{array}$
(143)

for $\bar{C}_{2}=\displaystyle\frac{1}{C_{1}\bar{C}_{1}}$. For the third term
in (139) to be less than or equal to $\epsilon$, we have

$\begin{array}[]{lllllllllll}2\sqrt{qN_{t}}Kh^{-1}e_{1}=2\sqrt{qN_{t}}\bar{C}_{1}\epsilon^{-1}\displaystyle\frac{\sqrt{qN_{t}}}{\bar{C}_{2}}\epsilon^{-2}e_{1}\leq\epsilon,\end{array}$
(144)

or

$\begin{array}[]{lllllllllll}e_{1}\leq\displaystyle\frac{\bar{C}_{3}}{qN_{t}}\epsilon^{4},\end{array}$
(145)

where $\bar{C}_{3}=\displaystyle\frac{1}{2C_{1}\bar{C}_{1}^{2}}$. To
summarize, we proved that the existence of $J^{NN}$ satisfying (138) and (145)
implies

$\begin{array}[]{lllllllllll}\left\lVert U^{\ast NN}({\bf x})-U^{\ast}({\bf
x})\right\rVert_{2}\leq 3\epsilon,&{\bf x}\in D\end{array}$ (146)

Now, we need to prove the existence of a $J^{NN}$ whose estimation error,
$e_{1}$, satisfies (145). Suppose we have deep neural networks that
approximates $\Psi(\cdot)$ and ${\bm{\phi}}({\it\Delta}t;\cdot,\cdot)$. Let
$J^{NN}$ be the deep neural network obtained by substituting functions in
(132)-(133) by $\Psi^{NN}(\cdot)$ and
${\bm{\phi}}^{NN}({\it\Delta}t;\cdot,\cdot)$. From Proposition 4, the
estimation error, $e_{1}$, of $J^{NN}$ is bounded by

$\begin{array}[]{lllllllllll}e_{1}\leq\bar{C}_{4}\displaystyle\max_{{\bf
x}\in[-R,R]^{d},{\bf u}\in{\cal U}}\left\lVert{\bm{\phi}}({\it\Delta}t;{\bf
u},{\bf x})-{\bm{\phi}}^{NN}({\it\Delta}t;{\bf u},{\bf
x})\right\rVert_{2}+\displaystyle\max_{{\bf
z}\in[-R,R]^{d}}\left\lVert\Psi({\bf z})-\Psi^{NN}({\bf
z})\right\rVert_{2},\end{array}$ (147)

where $\bar{C}_{4}$ depends on $N_{t}$, and the Lipschitz constants of
${\bm{\phi}}({\it\Delta}t,\cdot,\cdot)$ and $\Psi$ with respect to ${\bf x}$.
From Theorem 2 and Theorem 4, we can find $\Psi^{NN}(\cdot)$ and
${\bm{\phi}}^{NN}({\it\Delta}t;\cdot,\cdot)$ so that

$\begin{array}[]{lllllllllll}e_{1}\leq\bar{C}_{5}\left|{\cal
V}^{\Psi}_{G}\right|(n_{width})^{-1/r^{\Psi}_{max}}+\bar{C}_{6}\left|{\cal
V}^{\bf f}_{G}\right|{\it\Delta}t(n_{width})^{-1/r^{\bf
f}_{max}}\leq\bar{C}_{7}\left(\left|{\cal V}^{\Psi}_{G}\right|+\left|{\cal
V}^{\bf f}_{G}\right|{\it\Delta}t\right)(n_{width})^{-1/r_{max}},\end{array}$
(148)

where $\bar{C}_{7}$ depends on $\bar{C}_{4}$, $d_{i,j}^{\bf f}$,
$d_{i,j}^{\Psi}$ $m_{i,j}^{\bf f}$, $m_{i,j}^{\Psi}$, $L^{\bf f}_{max}$,
$L^{\Psi}_{max}$, $\Lambda^{\bf f}_{max}$, $\Lambda^{\Psi}_{max}$ and the
norms of ${\bf f}$ and its Jacobian. It also depends on
$e^{\alpha{\it\Delta}t}$ (see (87)). However, for a fixed ${\it\Delta}t$, this
term has an upper bounded determined by the norm of the Jacobian of ${\bf f}$.
To satisfy (145), (148) implies that we can choose

$\begin{array}[]{lllllllllll}n_{width}=\bar{C}_{8}q^{r_{max}}\left(\left|{\cal
V}^{\Psi}_{G}\right|+\left|{\cal V}^{\bf
f}_{G}\right|{\it\Delta}t\right)^{r_{max}}\epsilon^{-4r_{max}},\end{array}$
(149)

where $\bar{C}_{8}=(N_{t}\bar{C}_{7}/\bar{C}_{3})^{r_{max}}$. From Theorem 2,
Theorem 4 and (149), the complexity of $J^{NN}$, denoted by $n_{1}$, satisfies

$\begin{array}[]{lllllllllll}n_{1}\leq N_{t}((n_{width})^{1/r^{\bf
f}_{max}}+1)n_{width}\left|{\cal V}^{\bf f}_{G}\right|+n_{width}\left|{\cal
V}^{\Psi}_{G}\right|\\\ \leq(n_{width})^{1+1/r^{\bf
f}_{max}}\left(2N_{t}\left|{\cal V}^{\bf f}_{G}\right|+\left|{\cal
V}^{\Psi}_{G}\right|\right)\\\ \leq\bar{C}_{9}q^{r_{max}(1+1/r^{\bf
f}_{max})}\left(\left|{\cal V}^{\Psi}_{G}\right|+\left|{\cal V}^{\bf
f}_{G}\right|{\it\Delta}t\right)^{r_{max}(1+1/r^{\bf
f}_{max})}\left(2N_{t}\left|{\cal V}^{\bf f}_{G}\right|+\left|{\cal
V}^{\Psi}_{G}\right|\right)\epsilon^{-4r_{max}(1+1/r^{\bf f}_{max})}\\\
\leq\displaystyle\frac{\bar{C}_{9}}{2N_{t}}q^{r_{max}(1+1/r^{\bf
f}_{max})}\left(\left|{\cal V}^{\Psi}_{G}\right|+\left|{\cal V}^{\bf
f}_{G}\right|\right)^{r_{max}(1+1/r^{\bf
f}_{max})+1}\epsilon^{-4r_{max}(1+1/r^{\bf f}_{max})},\end{array}$ (150)

where $\bar{C}_{9}=\bar{C}_{8}^{1+1/r^{\bf f}_{max}}$. From (110) in Theorem
5, the complexity of $U^{\ast NN}$ is bounded by

$\begin{array}[]{lllllllllll}n\leq 2n_{1}qN_{t}K\\\ \leq
2\displaystyle\frac{\bar{C}_{9}}{2N_{t}}q^{r_{max}(1+1/r^{\bf
f}_{max})}\left(\left|{\cal V}^{\bf f}_{G}\right|+\left|{\cal
V}^{\Psi}_{G}\right|\right)^{r_{max}(1+1/r^{\bf
f}_{max})+1}\epsilon^{-4r_{max}(1+1/r^{\bf
f}_{max})}qN_{t}\bar{C}_{1}\epsilon^{-1}\\\ \leq Cq^{(r_{max}+1+r_{max}/r^{\bf
f}_{max})}\left(\left|{\cal V}^{\bf f}_{G}\right|+\left|{\cal
V}^{\Psi}_{G}\right|\right)^{(r_{max}+1+r_{max}/r^{\bf
f}_{max})}\epsilon^{-(4r_{max}+1+4r_{max}/r^{\bf f}_{max})}\end{array}$ (151)

where $C=\bar{C}_{1}\bar{C}_{9}$.

##  7 Conclusions

In this paper, we introduce new concepts and develop an algebraic framework
for compositional functions. In addition to functions defined in
$\mathbb{R}^{d}$, iterative numerical algorithms and dynamical systems fall
into the category of compositional functions as well. The algebraic framework
forms a unified theoretical foundation that supports the study of neural
networks with applications to a variety of problems including differential
equations, optimization, and optimal control. It is proved that the error
upper bound of approximations using neural networks is determined by a set of
key features of compositional functions. In the approximation of functions,
differential equations and optimal control, the complexity of neural networks
is bounded by a polynomial function of the key features and error tolerance.
The results could also shed light on the reason why using neural network
approximations may help to avoid the curse of dimensionality. As shown in
examples, increasing the dimension of a system may not increase the value of
the key features.

The study in this paper raises more questions than answers. All neural
networks used in the proofs of theorems have layered DAGs that are similar to
the DAG of the function being approximated. What is the underlying connection
between the shallow neural networks that approximate individual nodes and the
neural network that approximates the overall function? How can this connection
help to generate initial guess of parameters for neural network training?
Instead of $C^{1}$ functions, to what extent one can apply the idea in this
paper to a larger family of functions to include $C^{0}$ or even discontinuous
functions? This is important because optimal control problems with constraints
are likely to have $C^{0}$ or discontinuous feedbacks. The DAG associated with
a given function is not unique. What types of DAGs are advantageous for more
accurate approximation with less complexity? In general, many problems of
nonlinear control such as finding Lyapunov functions, designing output
regulators, $H_{\infty}$ control and differential game do not have tractable
numerical solutions if the dimension of state space is high. Finding
compositional function representations of these problems may lead to
innovative and practical solutions based on deep learning.

## References

  * [1] P. M. Anderson and A. A. Fouad. Power Systems Control and Stability, IEEE Press, 1994.
  * [2] A. R. Barron, Universal approximation bounds for superpositions of a sigmoidal function, IEEE Trans. on Information Theory, Vol. 39 (3), pp. 930-945, 1993.
  * [3] A. R. Barron and J. M. Klusowski, Approximation and estimation for high-dimensional deep learning networks. arXiv:1809.03090, 2018.
  * [4] C. Chiu and J. Zhan, An evolutionary approach to compact DAG neural network optimization, IEEE Access, Vol. 7, pp. 178331-178341, 2019.
  * [5] W. E, C. Ma, S. Wojtowytsch and L. Wu, Towards a mathematical understanding of neural network-based machine learning: what we know and what we don’t, arXiv:2009.10713v3, 2020.
  * [6] W. E and S. Wojtowytsch, On the Banach spaces associated with multi-layer ReLU networks: function representation, approximation theory and gradient descent dynamics, arXiv:2007.15623v1, 2020.
  * [7] P. Giesl, B. Hamzi, M. Rasmussen and K. Webster. Approximation of Lyapunov functions from noisy data, Journal of Computational Dynamics, Vol. 7(1), pp 57-81, 2020.
  * [8] L. Grüne, Overcoming the curse of dimensionality for approximating Lyapunov functions with deep neural networks uder a small-gain condition, arXiv:2001.08423v3, 2020.
  * [9] E. Hairer, S. P. Nørsett, G. Wanner, Solving Ordinary Differential Equations I: Nonstiff Problems, second edition, Springer, 1993.
  * [10] B. Hamzi and H. Owhadi. Learning dynamical systems from data: a simple cross-validation perspective, arXiv.org/abs/2007.05074, 2020.
  * [11] J. Han, A. Jentzen and W. E. Solving high-dimensional partial differential equations using deep learning, Proceedings of the National Academy of Sciences, 115(34):8505–8510, 2018.
  * [12] J. Han and W. E. Deep learning approximation for stochastic control problems, arXiv:1611.07422v1, 2016.
  * [13] P. C. Kainen, V. K$\mathring{\rm u}$rková, M. Sanguineti, Approximating multivariable functions by feedforward neural nets. In: M. Bianchini, M. Maggini, L. Jain (eds) Hanbook on Neural Information Processing. Intelligent Systems Reference Library, Vol 49, pp143-181, Springer, 2013.
  * [14] W. Kang, Q. Gong and T. Nakamura-Zimmerer, Algorithms of data development for deep learning and feedback design, arXiv:1912.00492v2, 2020.
  * [15] A. N. Kolmogorov, On the representation of continuous functions of many variables by superposition of continuous functions of one variable and addition, In Doklady Akademii Nauk, Vol. 114, No. 5, pp. 953-956, Russian Academy of Sciences, 1957.
  * [16] V. Kůrková, Kolmogorov’s theorem and multilayer neural networks, Neural networks, Vol. 5, No. 3, pp. 501-506, 1992.
  * [17] E. Lorenz, Predictability – A problem partly solved, Seminar on Predictability, Vol. I, ECMWF, 1996.
  * [18] H. N. Mhaskar, Neural networks for optimal approximation of smooth and analytic functions, Neural Computation, Vol. 8, No. 1, pp. 164-177, 1996.
  * [19] H. N. Mhaskar and T. Poggio, Deep vs. shallow networks: an approximation theory perspective, arXiv: 1608.03287v1, 2016.
  * [20] H. N. Mhaskar and T. Poggio, Function approximation by deep networks, arXiv:1905.12882v2, 2019.
  * [21] T. Nakamura-Zimmerer, Q. Gong and W. Kang, Adaptive deep learning for high dimensional Hamilton-Jacobi-Bellman equations, arXiv:1907.05317, 2019.
  * [22] T. Nakamura-Zimmerer, Q. Gong and W. Kang, QRnet: optimal regulator design with LQR-augmented neural networks, IEEE Control Systems Letters, Vol. 5, No. 4, pp.1303-1308, 2020.
  * [23] T. Poggio, H. Mhaskar, L. Rosasco, B. Miranda, Q. Liao, Why and when can deep - but not shallow - networks avoid the curse of dimensionality: a review, arXiv:1611.00740v5, 2017.
  * [24] J. Qi, K. Sun, and W. Kang, Optimal PMU placement for power system dynamic state estimation by using empirical observability Gramian, IEEE Trans. Power Systems, Vol. 30, No. 4, pp. 2041-2054, 2015.
  * [25] M. Raissi, P. Perdikaris, and G. E. Karniadakis, Physics-informed neural networks: a deep learing framework for solving forward and inverse problems involving nonlinear partial differential equations. J. of Computational Physics, 378:686–707, 2019.