# Quasi-Duality of Width and Depth of Neural Networks

Feng-Lei Fan1 Contact<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Rongjie
Lai2 Contact<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Ge Wang1 Contact:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract \vskip7.22743pt

Here we report that the width and depth of a neural network are quasi-dual to
each other; i.e., they are intrinsically connected and can be to a good degree
converted from one to the other. First, inspired by the De Morgan law, we
formulate a transformation from a general ReLU network to a wide network and a
deep network respectively without compromising the function of the original
network, thereby elaborating a quasi-duality of the width and depth. Then, we
estimate the width and depth of a network to represent a partially separable
function, and reveal an interchangeability between the width and depth.
Additionally, effects of width and depth on optimization and generalization
are also discussed.

##  1 Introduction

Recently, deep learning [b1, b2] has become the mainstream approach of machine
learning and achieved the state-of-the-art performance in many important tasks
[b3, b4, b5, b6]. One of the key reasons that accounts for the successes of
deep learning is the increased depth, which allows a hierarchical
representation of features. There are a number of papers dedicated to
explaining why deep networks are better than shallow ones. Encouraging
progresses have been made along this direction. The idea to show the
superiority of deep networks is basically to find a special family of
functions that are very hard to be approximated by a shallow network but easy
to be approximated by a deep network, or that a deep network can express more
complicated functions than a wide network using some complexity measure [b7,
b8, b9, b10, b11, b12, montufar2014number, b14]. For example, in [b11] a
special class of radial functions was constructed so that a one-hidden-layer
network needs to use an exponential number of neurons to do a good
approximation, but a two-hidden-layer network just needs a polynomial number
of neurons. With the number of linear regions as the complexity measure,
Montufar et al. [montufar2014number] showed that the number of linear regions
grows exponentially with the depth of a network but only polynomially with the
width of a network. In [b14], a topological measure was utilized to
characterize the complexity of functions. It was shown that deep networks can
represent functions of a much higher complexity than what the shallow
counterparts can. Although both theoretical insights and real-world
applications suggest that deep networks are better than shallow ones, the
width effects of networks are also increasingly recognized.

In the last eighties, a one-hidden-layer network with sufficiently many
neurons was shown to have a universal approximation ability [b15, b16].
Clearly, either width and depth can enable a sufficient representation
ability. In recent years, the term "wide/broad learning" was coined to
complement deep learning. In Cheng et al. [b17], a wide network and a deep
network were conjugated to realize the memorization (wide network) and
generalization (deep network) in a recommender. Challenged by the long
training time and large numbers of parameters of deep networks, Chen et al.
[b18] proposed to use a broad random vector functional-link neural network for
broad learning. Zagoruyho and Komodakis [b19] designed a novel architecture in
which the depth of a residual network is decreased while the width of a
residual network is increased, producing a far better performance than that of
commonly used thin and deep networks. Intuitively speaking, a wide network and
a deep network should be complementary. In this study, we demonstrate via
analysis and simulation that the width and depth of neural networks are
actually quasi-dual from two perspectives: partially separable representation
and modularized network configuration. The former is constructive, while the
latter is general. Given its practical importance, this study is focused on
modularized network configuration.

In the first perspective, we study the conversion between the width and depth
of a neural network in light of the duality offered by the De Morgan law:

$A_{1}\lor A_{2}\cdots\lor A_{n}=\neg\Big{(}(\neg A_{1})\land(\neg
A_{2})\cdots\land(\neg A_{n})\Big{)},$ (1)

where $A_{i}$ is a propositional rule, and such rules are disjoint. A neural
network can be interpreted as a rule-based system in terms of a collection of
propositional rules by splitting the representation of a neural network into
many decision hypercubes: IF $(input\in[a_{i},b_{i}]^{m})$, THEN ($input$
belongs to some class). We can illustrate that a deep network is to realize a
logic union of propositional rules (the left hand side of the De Morgan law)
and such a network is equivalent to a wide network that realizes the negation
of the logic intersection of those rules after negation (the right hand side).
Furthermore, each rule is a local function supported over a decision region.
In this paper, we abuse $A_{i}$ as a rule or a function interchangeably, and
then $A_{i}\lor A_{j}=A_{i}+A_{j},i\neq j$. We partition the set
$\\{1,2,\cdots,n\\}$ into two groups of disjoint subsets $S_{1},\cdots,S_{P}$
and $T_{1},\cdots,T_{Q}$ satisfying $S_{1}\cup\cdots\cup S_{P}\cup
T_{1}\cup\cdots\cup T_{Q}=\\{1,2,\cdots,n\\}$, then we can rewrite the De
Morgan law as

$\displaystyle\ \ \ \ A_{1}\lor A_{2}\cdots\lor A_{n}$ (2)
$\displaystyle=\sum_{p=1}^{P}\Big{(}\bigvee_{\alpha\in
S_{p}}A_{\alpha}\Big{)}+\sum_{q=1}^{Q}\Big{(}\bigvee_{\beta\in
T_{q}}A_{\beta}\Big{)}$
$\displaystyle=\sum_{p=1}^{P}\neg\Big{(}\bigwedge_{\alpha\in S_{p}}(\neg
A_{\alpha})\Big{)}+\sum_{q=1}^{Q}\Big{(}\bigvee_{\beta\in
T_{q}}A_{\beta}\Big{)}$ $\displaystyle=\neg\Big{(}(\neg A_{1})\land(\neg
A_{2})\cdots\land(\neg A_{n})\Big{)}.$

To represent $\sum_{p=1}^{P}\neg\Big{(}\bigwedge_{\alpha\in S_{p}}(\neg
A_{\alpha})\Big{)}+\sum_{q=1}^{Q}\Big{(}\bigvee_{\beta\in
T_{q}}A_{\beta}\Big{)}$, the $P$ wide sub-networks and the $Q$ deep sub-
networks should be combined together, which demonstrates that a wide network
and a deep network can be converted step by step, hence are actually
equivalent to one another in the view of Boolean algebra. Therefore, by re-
expressing De Morgan law, we can extend the network duality to the network
equivalency.

Furthermore, we observe the practical rules should be based on simplices
instead of hypercubes because a general ReLU network partitions the space into
polytopes. By enabling the transformation of an arbitrary ReLU network to a
wide network and a deep network, we can elaborate a quasi-duality of the width
and depth of neural networks for the rules over simplices, which is more
general and efficient than that for the rules over hypercubes.

In the second aspect, we correlate the width and depth of a network to the
structure of a function to be approximated. The class of partially separable
multivariate functions [b20] allows that every continuous $n$-variable
function $f$ on $[0,1]^{n}$ can be represented in the $L_{1}$ sense:

$\int_{{(x_{1},\cdots,x_{n})\in[0,1]^{n}}}|f(x_{1},\cdots,x_{n})-\sum_{l=1}^{L}\prod_{i=1}^{n}\phi_{li}(x_{i})|<\epsilon.$
(3)

where $\epsilon$ is an arbitrarily small positive number, $\phi_{li}$ is a
continuous function, and $L$ is the number of products.

Previously, our group designed the quadratic neuron that replaces the inner
product in a conventional neuron with a quadratic function. The resultant
quadratic neuron is more expressive than the conventional neuron. In a
nutshell, each continuous function $\phi_{li}$ can be approximated by a
polynomial of some degree. Based on the Algebraic Fundamental Theorem [b21],
each polynomial can be factorized as the product of quadratic terms, which can
be appropriately represented by quadratic neurons. As a consequence, in such a
quadratic representation scheme, the width and depth of a network structure
must reflect the complexity of
$\sum_{l=1}^{L}\prod_{i=1}^{n}\phi_{li}(x_{i})$.

In summary, our main contribution is the establishment of the width-depth
quasi-duality of neural networks from two complementary angles. To put our
contributions in perspective, we would like to mention relevant studies.
Kawaguchi et al. [b22] analyzed the effect of width and depth on the quality
of local minima. They showed that the quality of local minima improves toward
the global minima as depth and width becomes larger. Daniely et al. [b23] shed
light on the duality between neural networks and compositional kernel Hilbert
spaces using an acyclic graph that can succinctly describe neural networks and
compositional kernels in a unified framework. From the physical point of view,
Georgiev [b24] discussed the duality of observables (for example, image
pixels) and observations in machine learning. In addition, the importance of
width was implicated in light of the neural tangent kernel (NTK)
[jacot2018neural], and we discuss the width and depth of neural networks as
related to NTK in the Supplementary Information. To our best knowledge, this
work is the first that reveals the width-depth quasi-duality of neural
networks.

##  2 Perspective I: Modularized Network Configuration

As an important direction for interpretable/explainable neural networks [b30,
b31], rules can be extracted from an artificial neural network [b32, b33,
b34], i.e., using decompositional [b32] and pedagogical methods [b32].
Pedagogical methods decode a set of rules that imitate the input-output
relationship of a network. These rules do not necessarily correspond to the
parameters of the network. One common type of rules are propositional in the
IF-THEN format, where the preconditions are provided as a set of hypercubes
with respect to some input:

IF $input\in[a_{i},b_{i}]^{m}$, THEN $input$ belongs to some class.

The rule-based system suggests the linkage between the rule-based inference
and the neural inference. Such a link goes even further for some special kind
of networks. It is known that a radial-basis-function network is equivalent to
a fuzzy Takagi-Sugeno rule system under mild modifications [b35]. Therefore,
it is rationale to consider a neural network in terms of propositional rules.
Furthermore, we know that the De Morgan law holds true for disjoint
propositional rules. Mathematically, the De Morgan law is formulated as

$A_{1}\lor A_{2}\cdots\lor A_{n}=\neg\Big{(}(\neg A_{1})\land(\neg
A_{2})\cdots\land(\neg A_{n})\Big{)},$ (4)

where $A_{i}$ is a rule, and $\neg A_{i}$ is its negation. The De Morgan law
gives a duality in the sense of binary logic that the operations $\lor$ and
$\land$ are dual, which means that for any propositional rule system described
by $A_{1}\lor A_{2}\cdots\lor A_{n}$, there exists an equivalent dual
propositional rule system $\neg\Big{(}(\neg A_{1})\land(\neg
A_{2})\cdots\land(\neg A_{n})\Big{)}$. We point out that the duality of the
depth and width of a network is reminiscent of the duality in (4).
Specifically, we can always construct a deep network that implements the logic
union of propositional rules and an equivalent wide network that implements
the negation of the logic intersection of propositional rules after negation.
Formally, we have the definition for duality and $\delta$-duality.

######  Definition 1.

We call a wide network $\mathbf{N}_{1}:\Omega\rightarrow\mathbb{R}$ is dual to
a deep network $\mathbf{N}_{2}:\Omega\rightarrow\mathbb{R}$, if
$\mathbf{N}_{1}(\mathbf{x})=\mathbf{N}_{2}(\mathbf{x}),\forall x\in\Omega$. We
call a wide network $\mathbf{N}_{1}$ is $\delta$-dual to a deep network
$\mathbf{N}_{2}$, if for any $\delta>0$,
$\mathfrak{m}(\\{\mathbf{x}\in\Omega~{}|~{}\mathbf{N}_{1}(\mathbf{x})\neq\mathbf{N}_{2}(\mathbf{x})\\}<\delta$,
where $\mathfrak{m}$ is a measurement defined on $\Omega$.

Then, we have the following formal statement for the duality on rules over
hypercubes in light of the De Morgan law. We put the proof and constructions
for multivariate rules in Supplementary Information.

######  Theorem 1 (De Morgan Duality).

Given a disjoint rule system $\\{A_{i}\\}_{i=1}^{n}$, where each rule is
characterized by an indicator function $g_{i}(\mathbf{x})$ over a hypercube
$\Gamma_{i}=[a_{1i},b_{1i}]\times\cdots\times[a_{Di},b_{Di}]\in[0,1]^{D}$:

$g_{i}(\mathbf{x})=\left\\{\begin{array}[]{cc}1,&\textbf{if}\quad\mathbf{x}\in\Gamma_{i}\\\
0,&\textbf{if}\quad\mathbf{x}\in\Gamma_{i}^{c},\end{array}\right.$

fulfilling the De Morgan law

$A_{1}\lor A_{2}\cdots\lor A_{n}=\neg\Big{(}(\neg A_{1})\land(\neg
A_{2})\cdots\land(\neg A_{n})\Big{)},$ (5)

we can construct a wide network $\mathbf{H}_{1}(\mathbf{x})$ to represent the
right hand side of (5) and a deep network $\mathbf{H}_{2}(\mathbf{x})$ to
represent the left hand side of (5), such that for any $\epsilon>0$,

$\mathfrak{m}\Big{(}\\{\mathbf{x}~{}|\mathbf{H}_{1}(\mathbf{x})\\}\neq\mathbf{H}_{2}(\mathbf{x})\\}\Big{)}<\epsilon,$
(6)

where $\mathfrak{m}$ is a measurement in $[0,1]^{D}$.

Figure 1: De Morgan duality. A deep network to implement $A_{1}\lor
A_{2}\cdots\lor A_{n}$ using a trapezoid function and a wide version to
implement $\neg\Big{(}(\neg A_{1})\land(\neg A_{2})\cdots\land(\neg
A_{n})\Big{)}$ using the trap-like function. $(\cdot)^{+}$ denotes ReLU.

Here we show our construction for a single-variable binary classification
problem. Suppose that $A_{i}$ is a rule defined as

IF $(x\in[a_{i},b_{i}])$, THEN class is $1$.

Without loss of generality, any two rules are disjoint, which means that any
two intervals do not overlap with each other. As shown on the left side of
Figure 1, the $i^{th}$ network block (the green box) with three layers can
represent the following function:

$\begin{cases}1-\frac{a_{1}-x}{\delta}&x\in[a_{i}-\delta,a_{i}]\\\
1&x\in[a_{i},b_{i}]\\\ 1-\frac{x-b_{i}}{\delta}&x\in[b_{i},b_{i}+\delta]\\\
\end{cases},$ (7)

which gives a good approximation to $A_{i}$ since $\delta$ can be made
arbitrarily small. The output of the $i^{th}$ block is $A_{1}\lor
A_{2}\cdots\lor A_{i}$. As the network goes deeper, more blocks are stacked
together to include more propositional rules over different intervals. In this
process, these rules are integrated to represent $A_{1}\lor A_{2}\cdots\lor
A_{n}$.

On the other hand, we can use a wide network to construct $\neg\Big{(}(\neg
A_{1})\land(\neg A_{2})\cdots\land(\neg A_{n})\Big{)}$. As shown on the right
side of Figure 1, the $i^{th}$ block (the blue box) that represents $\neg
A_{i}$ can be defined as

$\begin{cases}1&x\in[-\infty,a_{i}-\delta]\\\
1-\frac{x-a_{i}}{\delta}&x\in[a_{i}-\delta,a_{i}]\\\ 0&x\in[a_{i},b_{i}]\\\
1-\frac{b_{i}-x}{\delta}&x\in[b_{i},b_{i}+\delta]\\\
1&x\in[b_{i}+\delta,\infty]\\\ \end{cases},$ (8)

Concurrently, the $n$ blocks can represent $\neg A_{1},\cdots,\neg A_{n}$
respectively. After all $\neg A_{i}$ rules are prepared, with the output
neuron we perform the logic intersection and negation. To this end, a
summation is conducted of all the inputs before the thresholding operation.
After thresholding, a negation is conducted. The threshold is set to $n-1$ for
$n$ propositional rules. Specifically, we have

$\displaystyle\neg\Big{(}(\neg A_{1})\land(\neg A_{2})\cdots\land(\neg
A_{n})\Big{)}$ (9) $\displaystyle=1-((\neg A_{1})+(\neg A_{2})+\cdots+(\neg
A_{n})-(n-1)).$

Figure 2: By re-expressing the De Morgan law, a family of equivalent network
architectures comprising of a deep network, a wide network, and others between
them are evaluated for breast cancer analysis in the example.

Re-expressing the De Morgan law: Let us further examine $A_{1}\lor
A_{2}\cdots\lor A_{n}$. We partition the set $\\{1,2,\cdots,n\\}$ into two
groups of disjoint subsets $S_{1},\cdots,S_{P}$ and $T_{1},\cdots,T_{Q}$
satisfying $S_{1}\cup\cdots\cup S_{P}\cup T_{1}\cup\cdots\cup
T_{Q}=\\{1,2,\cdots,n\\}$, then we can re-express the De Morgan law as

$\displaystyle\ \ \ \ A_{1}\lor A_{2}\cdots\lor A_{n}$ (10)
$\displaystyle=\sum_{p=1}^{P}\Big{(}\bigvee_{\alpha\in
S_{p}}A_{\alpha}\Big{)}+\sum_{q=1}^{Q}\Big{(}\bigvee_{\beta\in
T_{q}}A_{\beta}\Big{)}$
$\displaystyle=\sum_{p=1}^{P}\neg\Big{(}\bigwedge_{\alpha\in S_{p}}(\neg
A_{\alpha})\Big{)}+\sum_{q=1}^{Q}\Big{(}\bigvee_{\beta\in
T_{q}}A_{\beta}\Big{)}$ $\displaystyle=\neg\Big{(}(\neg A_{1})\land(\neg
A_{2})\cdots\land(\neg A_{n})\Big{)},$

(10) suggests the step-wise continuum of mutually equivalent networks, which
comprises not only a deep network and a wide network shown in Figure 1 but
also the transitional networks between them. In order to express
$\sum_{p=1}^{P}\neg\Big{(}\bigwedge_{\alpha\in S_{p}}(\neg
A_{\alpha})\Big{)}+\sum_{q=1}^{Q}\Big{(}\bigvee_{\beta\in
T_{q}}A_{\beta}\Big{)}$ , a generic network is constructed with $n$ blocks,
each block representing either $\neg{A_{\alpha}}$ or $A_{\beta}$ to form
neural networks in various combinations of width and depth settings governed
by the re-expressed De Morgan law.

Table 1: Equivalency of different architectures. Architecture | Mean | Standard Deviation
---|---|---
I | 0.9264 | 0.0069
II | 0.9293 | 0.0073
III | 0.9300 | 0.0081
IV | 0.9285 | 0.0079
V | 0.9192 | 0.0117
VI | 0.9280 | 0.0074
VII | 0.9237 | 0.0103
VIII | 0.9267 | 0.0101

To illustrate the above scheme, the eight network architectures were
constructed, including a deep network, a wide network and others between them
as shown in Figure 2. In reference to Figure 1, each green box contains four
layers with three neurons in each layer while each blue box contains three
layers with two neurons per layer. The breast cancer Wisconsin dataset was
selected as an example to perform our experiment, covering 30 attributes
reflecting two pathological features categories: "Benign" and "Malignant". In
our demonstration, we only used five attributes (radius, texture, perimeter,
area, smoothness) to show the equivalency of networks. We randomly initialized
all the parameters of each network configurations 20 times. The mean
classification accuracy and the corresponding standard deviation of each
network are tabulated in Table 1. The takeaway from Table 1 is that the
performance difference between any two networks is no more than 0.0102, which
means that eight networks performed rather comparably. We did the t-test for
experimental results from any pair of the networks, and the lowest p-value
0.0517 is from the results of networks II and V, which is not sufficient to
reject that the networks II and V are equivalent. More detailed discussions
are in the Supplementary Information. Such similarity suggests the existence
of equivalent networks. In this regard, duality between a wide network and a
deep network becomes a special case of a family of equivalent networks in the
light of Boolean algebra.

ReLU Duality: This part describes the main contribution of our paper. In the
light of the De Morgan law, an overall binary judgement process allows the
conversion of the width and depth of a logic workflow consisting of elementary
gates or rules. Suppose that the input domain is bounded, it is easy to show
that given sufficiently many rules over hypercubes, the union of these rules
can solve any binary classification problem. However, a ReLU network generally
partitions the space into many polytopes [chu2018exact]. It is inefficient and
unpractical to utilize hypercubes to represent a polytope. In other words, it
is computationally expensive to use rules that are based on hypercubes. In
contrast, a number of simplices can form a polytope efficiently
[ehrenborg2007perles]. Therefore, a more appropriate rule should be in the
following format:

IF $input\in\ a\ simplex$, THEN $input$ belongs to some class.

Along this direction, we formulate the transformation from an arbitrary ReLU
network to a wide network and a deep network by constructing the network-based
building block to represent a linear function over a simplex, integrating such
building blocks to represent any piecewise linear function, thereby
elaborating the general ReLU duality of the width and depth. Then, the De
Morgan duality is a special case of the ReLU duality, since a rule is
equivalent to an indicator function, which is a special case of a piecewise
linear function. In the same spirit, the De Morgan law for rules over
hypercubes can be generalized into that for rules over simplices. Please note
that the transformation of a univariate network is rather different from that
of a multivariate network. The former is strictly precise and symmetric for
the wide and deep networks, whereas the latter is precise in the measure sense
and only approximately symmetric in terms of network structures. This is why
we term such a duality as a quasi-duality.

######  Definition 2.

Denote the length of one route between a neuron and the input as the number of
affine operations. We define that two neurons are in the same layer if they
have the routes sharing the same length. Then, the width is defined as the
maximum number of neurons in a layer, whereas the depth is defined as the
length of the longest route in the network.

######  Theorem 2 (ReLU Duality of Univariate Networks).

Given any ReLU network $f:[-B,~{}B]\rightarrow\mathbb{R}$ with one dimensional
input and output variables. There is a wide ReLU network
$\mathbf{H}_{1}:[-B,~{}B]\rightarrow\mathbb{R}$ and a deep ReLU network
$\mathbf{H}_{2}:[-B,~{}B]\rightarrow\mathbb{R}$, such that
$f(x)=\mathbf{H}_{1}(x)=\mathbf{H}_{2}(x),\forall x\in[-B,~{}B]$.

######  Theorem 3 (ReLU Duality of Multivariate Networks, which is our main
result).

Suppose that the representation of an arbitrary ReLU network is
$h:[-B,~{}B]^{D}\to\mathbb{R}$, for any $\delta>0$, there exist a wide network
$\mathbf{H}_{1}$ of width $\mathcal{O}\left[D(D+1)(2^{D}-1)M\right]$ and depth
$D+1$ as well as a deep network $\mathbf{H}_{2}$ of width $(D+1)D^{2}$ and
depth $\mathcal{O}\left[(D+2)M\right]$, where $M$ is the minimum number of
simplices to seamlessly cover the polytopes to support $h$, satisfying

$\displaystyle\mathfrak{m}\Big{(}\mathbf{x}~{}|~{}h(\mathbf{x})\neq\mathbf{H}_{1}(\mathbf{x})\\}\Big{)}<\delta$
(11)
$\displaystyle\mathfrak{m}\Big{(}\mathbf{x}~{}|~{}h(\mathbf{x})\neq\mathbf{H}_{2}(\mathbf{x})\\}\Big{)}<\delta,$

where $\mathfrak{m}(\cdot)$ is the standard measure in $[-B,~{}B]^{D}$.

For improving readability and highlighting our main contribution, we split the
proof into the two-dimensional case (easy to understand) and the general case,
and then put the proof of Theorem 3 in the two-dimensional case and the
general case in the Appendix and Supplementary Information respectively. The
key idea behind the proof is that since a number of simplices constitute a
polytope [ehrenborg2007perles], if we can construct either a wide network or a
deep network to represent the corresponding function over each and every
simplex, then we can aggregate the results into deep or wide networks in
series or parallel respectively to represent the original network well. The
way to represent a linear function over a simplex is to construct high-
dimensional fan-shaped functions that are compressed in fan-shaped domains to
use these constructs to eliminate non-zero functional values outside the
simplex of interest.

Remark 2: In our work, we have utilized the fact that a piecewise linear
function over polytopes can be represented by discontinuous piecewise linear
functions that are linear over simplices respectively. In contrast, there is a
global way to represent piecewise linear functions [wang2005generalization].
Specifically, for every piecewise linear function
$f:\mathbb{R}^{n}\to\mathbb{R}$, there exists a finite group of linear
functions $k_{1},\cdots,k_{m}$ and subsets
$T_{1},\cdots,T_{P}\subseteq\\{1,\cdots,m\\}$ such that
$f=\sum_{p=1}^{P}s_{p}(\max_{i\in T_{p}}k_{i})$, where
$s_{p}\in\\{-1,+1\\},p=1,\cdots,P$. It is noted that due to its unboundedness,
the global representation of a piecewise linear function is problematic in
representing a function over polytopes that make a non-convex region, which is
nevertheless typical for manifold learning.

######  Theorem 4 (Generalized De Morgan Duality).

Without loss of generality, we assume multivariate cases. For a disjoint rule
system $A_{1}\lor A_{2}\cdots\lor A_{n}$, where each rule $A_{i}$ is
characterized by an indicator function $g_{i}(\mathbf{x})$ over a simplex
$S_{i}$ in a bounded domain:

$g_{i}(\mathbf{x})=\left\\{\begin{array}[]{cc}1,&\textbf{if}\quad\mathbf{x}\in
S_{i}\\\ 0,&\textbf{if}\quad\mathbf{x}\in S_{i}^{c}.\end{array}\right.$

We can construct a wide network $\mathbf{H}_{1}(\mathbf{x})$ and a deep
network $\mathbf{H}_{2}(\mathbf{x})$ to represent $A_{1}\lor A_{2}\cdots\lor
A_{n}$ such that for any $\delta>0$,

$\mathfrak{m}\Big{(}\\{\mathbf{x}~{}|\mathbf{H}_{1}(\mathbf{x})\\}\neq\mathbf{H}_{2}(\mathbf{x})\\}\Big{)}<\delta,$
(12)

which means that $\mathbf{H}_{1}(\mathbf{x})$ and $\mathbf{H}_{2}(\mathbf{x})$
are $\delta$-dual to each other.

###### Proof.

The key is to regard the rule system $A_{1}\lor A_{2}\cdots\lor A_{n}$ as a
function defined on simplices. The holistic function represented by $A_{1}\lor
A_{2}\cdots\lor A_{n}$ is $\sum_{i}^{n}g_{i}(\mathbf{x})$. Evidently,
$\sum_{i}^{n}g_{i}(\mathbf{x})$ can be transformed to a wide network and a
deep network according to Theorem 3. Therefore, applying the construction
techniques used in the proof of Theorem 3 will lead to that for any
$\delta/2>0$,

$\displaystyle\mathfrak{m}\Big{(}\mathbf{x}~{}|~{}h(\mathbf{x})\neq\mathbf{H}_{1}(\mathbf{x})\\}\Big{)}<\delta/2$
(13)
$\displaystyle\mathfrak{m}\Big{(}\mathbf{x}~{}|~{}h(\mathbf{x})\neq\mathbf{H}_{2}(\mathbf{x})\\}\Big{)}<\delta/2.$

That is,

$\mathfrak{m}\Big{(}\\{\mathbf{x}~{}|\mathbf{H}_{1}(\mathbf{x})\\}\neq\mathbf{H}_{2}(\mathbf{x})\\}\Big{)}<\delta,$
(14)

which verifies the correctness of Theorem 4. ∎

Remark 3: The De Morgan duality and the generalized De Morgan duality can be
summarized respectively as

$\displaystyle\mathbf{H}_{2}(\mathbf{x})$ $\displaystyle\simeq A_{1}\lor
A_{2}\cdots\lor A_{n}$ (15) $\displaystyle=\neg\Big{(}(\neg A_{1})\land(\neg
A_{2})\cdots\land(\neg A_{n})\Big{)}\simeq\mathbf{H}_{1}(\mathbf{x}),$

when the rules are based on hypercubes, and

$\mathbf{H}_{2}(\mathbf{x})\simeq A_{1}\lor A_{2}\cdots\lor
A_{n}\simeq\mathbf{H}_{1}(\mathbf{x}),$ (16)

when rules are based on simplices. It is seen that the De Morgan duality and
the generalized De Morgan duality are deeply related but cast differently in
terms of what rules are implemented by equivalent networks, being wide or
deep. Overall, the generalized De Morgan quasi-duality is more practical and
efficient because of the employment of simplices. Considering that hypercubes
are usually made very small to enable a universal approximation, the
difference between their efficiencies can be huge.

##  3 Perspective II: Partially Separable Presentation

Let us first introduce necessary preliminaries.

Quadratic Neuron [b2, b25, b26]: The operation integrating $n$ input variables
to a quadratic/second-order neuron before being nonlinearly processed is
expressed as

$\displaystyle h(\textbf{x})$
$\displaystyle=(\sum_{i=1}^{n}w_{ir}x_{i}+b_{r})(\sum_{i=1}^{n}w_{ig}x_{i}+b_{g})+\sum_{i=1}^{n}w_{ib}x_{i}^{2}+c$
(17)
$\displaystyle=(\textbf{w}_{r}\textbf{x}^{T}+b_{r})(\textbf{w}_{g}\textbf{x}^{T}+b_{g})+\textbf{w}_{b}(\textbf{x}^{2})^{T}+c,$

where $\bf x$ denotes the input vector, $\bf w_{r},\bf w_{g},\bf w_{b}$ are
vectors of the same dimensionality as that of $\bf x$, and $b_{r},b_{g},c$ are
biases. Our quadratic function definition only utilizes $3n$ parameters, which
is sparser than the general second-order representation which requires
$\frac{n(n+1)}{2}$ parameters. In this paper, we will use quadratic networks
to refer networks using quadratic neurons.

Algebraic Structure: Any univariate polynomial of degree $N$ can be perfectly
computed by a quadratic ReLU network with the depth of $\log_{2}(N)$ and width
of no more than $N$ [fan2020universal].

Partially Separable Representation: Approximating a multivariate function
$f(x_{1},x_{2},\cdots,x_{n})$ by a set of functions of fewer variables is a
basic problem in approximation theory [b20]. Despite that some function $f$ is
directly separable in the form of

$f(x_{1},x_{2},\cdots,x_{n})=\phi_{1}(x_{1})\phi_{2}(x_{2})\cdots\phi_{n}(x_{n}),$
(18)

a more general formulation to express a multivariate $f$ is

$f(x_{1},x_{2},\cdots,x_{n})=\sum_{l=1}^{L}\prod_{i}^{n}\phi_{li}(x_{i}).$
(19)

If $L$ is permitted to be sufficiently large, then such a model is rather
universal. For bivariate functions, an inspiring theorem has been proved
[b20]: Let $\\{u_{n}\\}_{n\in\mathcal{N}}$ and $\\{v_{n}\\}_{n\in\mathcal{N}}$
are orthornomal bases of $L^{2}(\textbf{X})$ and $L^{2}(\textbf{Y})$
respectively, then $\\{u_{m}v_{n}\\}_{(m,n)\in\mathcal{N}^{2}}$ is an
orthornomal basis of $L^{2}(\textbf{X}\times\textbf{Y})$.

To approximate a general multivariate function, we relax the restrictive
equality to the approximation in the $L_{1}$ sense and assume that, for every
continuous $n$-variable function $f(x_{1},\cdots,x_{n})$ on $[0,1]^{n}$, given
any positive number $\epsilon$, there exists a group of $\phi_{li}$,
satisfying:

$\int_{{(x_{1},\cdots,x_{n})\in[0,1]^{n}}}|f(x_{1},\cdots,x_{n})-\sum_{l=1}^{L}\prod_{i=1}^{n}\phi_{li}(x_{i})|<\epsilon.$
(20)

Because $f(x_{1},\cdots,x_{n})$ is continuous in a closed space,
$f(x_{1},\cdots,x_{n})$ is bounded, and $f(x_{1},\cdots,x_{n})$ is Lebesgue-
integrable. we can construct a generic separable representation as
$\sum_{l=1}^{L}f(a_{l1},a_{l2},\cdots,a_{ln})h(x_{1}-a_{l1})h(x_{2}-a_{l2})\cdots
h(x_{n}-a_{ln})$, where $h(x_{i}-a_{li})$ is expressed with an adjustable
parameter $\delta$ as

$\begin{cases}1-\frac{a_{li}-\delta-
x_{i}}{\delta}&x_{i}\in[a_{li}-2\delta,a_{li}-\delta]\\\
1&x_{i}\in[a_{li}-\delta,a_{li}+\delta]\\\
1-\frac{x_{i}-a_{li}-\delta}{\delta}&x_{i}\in[a_{li}+\delta,a_{li}+2\delta]\\\
\end{cases}.$ (21)

$\prod_{i=1}^{n}h(x_{i}-a_{li})$ forms a $n$-dimension trapezoidal shape which
is nearly a unit cube, and $L$ depends on the sampling rate. It can be seen
that the space $[0,1]^{n}$ is partitioned into $L$ hypercubes, and $a_{li}$ is
the $i^{th}$ coordinate of the $l^{th}$ hypercube. By making the partition
increasingly denser, sampling more $a_{li}$ at $x_{i}$, and reducing $\delta$,
$\sum_{l=1}^{L}f(a_{l1},a_{l2},\cdots,a_{ln})h(x_{1}-a_{l1})h(x_{2}-a_{l2})\cdots
h(x_{n}-a_{ln})$ can approach $f(x_{1},\cdots,x_{n})$ well in the $L_{1}$
sense. Furthermore, since a quadratic network can represent a univariate
polynomial and a multiplication operation, the quadratic networks using the
partially separable representation should allow an universal approximation of
any continuous multivariable function according to Weierstrass theorem.

Figure 3: Use of a quadratic network to represent a partially separable
representation. Suppose that the polynomial $P_{li}$ is of degree $N_{li}$,
the width and depth of the quadratic network to approximate $P_{li}$ are
$N_{li}$ and $\log_{2}(N_{li})$ respectively.

Now, let us analyze the complexity of the aforementioned representation
scheme. Figure 3 shows that such a universal approximator can be either wide
or deep. Suppose that the polynomial $P_{li}$ is of degree $N_{li}$, then the
representation of each $P_{li}$ can be done with a network of width
$\sum_{l=1}^{L}\sum_{i=1}^{n}N_{li}$ and depth
$\max_{l,i}\\{\log_{2}(N_{li})\\}$. Next, the multiplication demands an
additional network of width $Ln$ and depth $\log_{2}(n)$. Therefore, the
overall quadratic network architecture will be of width
$\max\\{\sum_{l=1}^{L}\sum_{i=1}^{n}N_{li},Ln\\}$ and depth
$\max_{l,i}\\{\log_{2}(N_{li})\\}+\log_{2}(n)$. Because the depth scales with
a log function, which changes slowly when the dimensionality of the input is
large. For simplicity, we take an approximation for depth
$\max_{l,i}\\{\log_{2}(N_{li})\\}+\log_{2}(n)=\log_{2}(\max_{l,i}\\{N_{li}\\})+\log_{2}(n)\approx\alpha\log_{2}\sum_{l=1}^{L}\sum_{i=1}^{n}N_{li}+\log_{2}(n)$,
where $\alpha$ is a positive constant. Let
$\sum_{l=1}^{L}\sum_{i=1}^{n}N_{li}=N^{\Sigma}$, which describes the overall
complexity of the function to be expressed, then the formulas to compute the
width and depth are simplified as follows:

$\displaystyle Width=\max\\{N^{\Sigma},Ln\\}$ (22) $\displaystyle Depth=\alpha
log_{2}(N^{\Sigma})+log_{2}(n)$

One interesting point from (22) is that the lower bounds for depth and width
to realize a partially separable representation are also suggested. As shown
in Figure 4, we plot the width and depth as $N^{\Sigma}$ changes. There are
two highlights in Figure 4. The first is that the width is generally larger
than the depth, which is different from the superficial impression on deep
learning. The second is that, as the $N^{\Sigma}$ goes up, the width/depth
ratio is accordingly increased.

Table 2: Descriptions of different building blocks. Modules | Degree | Operation | Width | Depth
---|---|---|---|---
$P_{li}$ | $N_{li}$ | Express $\phi_{li}$ | $N_{li}$ | $\log_{2}(N_{li})$
$\Pi$ | $-$ | Express $\Phi_{i}$ | $n$ | $\log_{2}(n)$
Figure 4: Width and depth versus $N^{\Sigma}$ changes ($L=4$, $n=5$, and
$\alpha=1$ without loss of generality) assuming the partially separable
representation.

Remark 1: Through the complexity analysis, we realize that the width and depth
of a network depend on the structure or complexity of the function to be
approximated. In other words, they are controlled by the nature of a specific
task. As the task becomes complicated, the width and depth must increase
accordingly, and the combination of the width and depth is not unique (more
details below). It is worthwhile mentioning that the partially separable
representation is not the only vehicle either for functional approximation.
For example, we have the Kolmogorov-Arnold representation theorem [b29]: Every
continuous $n$-variable function on $[0,1]^{n}$ can be represented in the
following form:

$f(x_{1},...,x_{n})=\sum_{i=1}^{2n+1}\Phi_{i}(\sum_{j=1}^{n}\phi_{ij}(x_{j})),$
(23)

where $\phi_{ij}$ and $\Phi_{i}$ are continuous univariate functions; and we
also have piecewise polynomial representation as used in
[telgarsky2016benefits]. In the Supplementary Information, we justify the
suitability of the partially separable representation by comparing it with
Kolmogorov-Arnold representation and the piecewise polynomial representation.

##  4 Discussions

Continued Fraction: Mathematically, a continued fraction representation of a
general polynomial can be expressed as [b40]:

$\sum_{i=0}^{n}a_{i}x^{i}=\cfrac{b_{0}}{1-\cfrac{b_{1}x}{1+b_{1}x-\cfrac{b_{2}x}{1+b_{2}x-\cfrac{b_{3}x}{1-\cdots}}}},$
(24)

where $a_{i},b_{i}$ are related by $b_{0}=a_{0}$, $b_{i}=a_{i}/a_{i-1},i>1$.
By performing the polynomial factorization of the left side of (24), we have

$\displaystyle
C\prod_{i}^{l_{1}}(x-x_{i})\prod_{j}^{l_{2}}(x^{2}+p_{j}x+q_{j})$ (25)
$\displaystyle=\cfrac{b_{0}}{1-\cfrac{b_{1}x}{1+b_{1}x-\cfrac{b_{2}x}{1+b_{2}x-\cfrac{b_{3}x}{1-\cdots}}}},$

where $x_{i}$ is the root of the polynomial, $p_{i},q_{i}$ are constants, and
$l_{1}+2l_{2}=n$. Note that $x_{i},p_{i},q_{i}$ and $b_{i}$ are also related
since $x_{i},p_{i},q_{i}$ are related with $a_{i}$. We can construct a wide
quadratic network to express the factorization representation (left side of
(25)) and a deep network according to
$f_{l+1}(x)=\frac{b_{l}x}{1+b_{l}x-f_{l}(x)}$ or $f_{1}=\frac{b_{0}}{1-f_{0}}$
to express the continued representation (right side of (25)). In the view of
(25), the constructed wide quadratic network is clearly linked to the
associated deep network.

Equivalent Networks: In a broader sense, our quasi-duality studies demonstrate
that there are mutually equivalent networks in a practical sense (in
principle, as accurately as needed. Such an equivalency between two networks
implies that given any input, two networks produce essentially the same
output. The network equivalency is useful in many ways, for example, in
network optimization. Although deep networks manifest superb power, their
applications can be constrained, for example, when the application is time-
critical. In that case, we can convert the deep network to a wide counterpart
that can be executed at a high speed. A main goal of network optimization is
to derive a compact network that maintain a high performance of a complicated
network, through quantization [b41], pruning [b42], distillation [b43],
binarification [b44], low-rank approximation [b45], etc. We envision that the
duality of a deep network and a wide network suggests a new direction of
network optimization in a task-specific fashion. Ideally, a wide network is
able to replace the well-trained deep network without compromising the
performance. Since the processing steps of the wide network are paralleled,
the wide network can be trained on a computing cluster with many machines,
which facilitates the fast training. because of its parallel nature, the
inference time of the equivalent wide network is shorter than its deep
counterpart.

Effects of Width on Optimization, Generalization and VC dimension: In the
Supplementary Information, we illustrate the importance of width on
optimization in the context of over-paramterization, kernel ridge regression,
and NTK, and then report our findings that the existing generalization bounds
and VC dimension results somehow suggest the width and depth duality for a
given complexity of networks.

##  5 Conclusion

In conclusion, we have presented the quasi-duality between the depth and width
of neural networks from two perspectives: modularized network configuration
and partially separable representation, and deepened our understanding of
network equivalency. Most importantly, we have established the general ReLU
quasi-duality by enabling the transformation from an arbitrary ReLU network to
a wide network and a deep network. Clearly, more efforts are need to realize
the great potential of this quasi-duality/equivalency theory in basic research
and for real-world applications.

##  6 Appendix. Proof of Theorem 3 (2D)

######  Proposition 1.

Suppose that $f(\mathbf{x})$ is a function represented by a ReLU network, then
$f$ is a piecewise linear function that splits the space into polytopes, where
each polytope can be seamlessly filled with a number of simplices.

###### Proof.

Because of the affine transform and the piecewise linear function ReLU,
$f(\mathbf{x})$ will partition the space into polytopes, each of which is
defined by a linear function. A feedforward ReLU network partitions the space
into convex polytopes [chu2018exact], whereas a ReLU network with shortcuts
may create non-convex polytopes. Nevertheless, those non-convex polytopes are
de facto obtained by convex polytopes because a ReLU network with shortcuts
can be taken as the combination of several branches of feedforward networks.
Clearly, the polytopes by $f(\mathbf{x})$ can be seamlessly filled with a
number of simplices. ∎

Figure 5: Quasi-duality analysis in 2D case. (a1) The building block that
expresses a fan-shaped function $F(\mathbf{x})$, which is of depth=2 and
width=2. (a2) The function $F(\mathbf{x})$ represented by (a1) splits the
space into four polytopes, two of which $\Omega_{1},\Omega_{2}$ are non-zero.
As $\mu$ increases, the support of $F(\mathbf{x})$ converges to the fan-shaped
domain $\Omega_{1}$. (b1) The structure of the wide network to represent $f$
over $S$, where two neurons denote $f$ over $[-B,B]^{2}$ and nine fan-shaped
functions handle the polytopes outside $S$. (b2) The polytopes outside $S$
comprise of three fan-shaped domains, on which $f$ can be cancelled by three
linearly independent fan-shaped functions. (c1) The structure of the deep
network to represent $f$ over $S$, where six building blocks represent three
linearly independent functions over $S$, and then these functions are
aggregated to represent $f$ over $S$. (c2) Allowing using more layers, a
linear function over $S$ can be obtained.

Regarding the transformation of an arbitrary multivariate network, the
situation is more complicated than in the case of univariate networks.
Nevertheless, we are able to establish the $\delta$-duality, which is a
slightly relaxed result. Before we prove Theorem 3, we need to have the
following lemma.

######  Definition 3 (Simplicial complex).

A $D$-simplex $S$ is a $D$-dimensional convex hull provided by convex
combinations of $D+1$ affinely independent vectors
$\\{\mathbf{v}_{i}\\}_{i=0}^{D}\subset\mathbb{R}^{D}$. In other words,
$\displaystyle S=\left\\{\sum_{i=0}^{D}\xi_{i}\mathbf{v}_{i}~{}|~{}\xi_{i}\geq
0,\sum_{i=0}^{D}\xi_{i}=1\right\\}$. The convex hull of any subset of
$\\{\mathbf{v}_{i}\\}_{i=0}^{D}$ is called a face of $S$. A simplicial complex
$\displaystyle\mathcal{S}=\bigcup_{\alpha}S_{\alpha}$ is composed of a set of
simplices $\\{S_{\alpha}\\}$ satisfying: 1) every face of a simplex from
$\mathcal{S}$ is also in $\mathcal{S}$; 2) the non-empty intersection of any
two simplices $\displaystyle S_{1},S_{2}\in\mathcal{S}$ is a face of both
$S_{1}$ and $S_{2}$.

######  Lemma 5.

Given a $D$-simplex $\displaystyle
S=\left\\{\sum_{i=0}^{D}\xi_{i}\mathbf{v}_{i}\in\mathbb{R}^{D}~{}|~{}\xi_{i}\geq
0,\sum_{i=0}^{D}\xi_{i}=1\right\\}\subset[-B,~{}B]^{D}$, and a piece-wise
linear function $f:[-B,~{}B]^{D}\rightarrow\mathbb{R}$ supported on $S$
expressed as

$f(\mathbf{x})=\left\\{\begin{array}[]{cc}\sum_{i=0}^{D}\xi_{i}f(\mathbf{v}_{i}),&\textbf{if}\quad\mathbf{x}=\sum_{i=0}^{D}\xi_{i}\mathbf{v}_{i}\in
S\\\ 0,&\textbf{if}\quad\mathbf{x}\in S^{c}\end{array}\right.$

Then, for any $\delta>0$, there exist both a wide network $\mathbf{N}_{1}$ of
width $D(D+1)(2^{D}-1)+2$ and depth $D+1$ and a deep network $\mathbf{N}_{2}$
of width $(D+1)D^{2}$ and depth $D+2$, satisfying

$\displaystyle\mathfrak{m}\Big{(}\\{\mathbf{x}~{}|~{}f(\mathbf{x})\neq\mathbf{N}_{1}(\mathbf{x})\\}\Big{)}<\delta$
(26)
$\displaystyle\mathfrak{m}\Big{(}\\{\mathbf{x}~{}|~{}f(\mathbf{x})\neq\mathbf{N}_{2}(\mathbf{x})\\}\Big{)}<\delta.$

###### Proof.

($\mathbf{D=2}$) If we write
$V=(\mathbf{v}_{1}-\mathbf{v}_{0},\mathbf{v}_{2}-\mathbf{v}_{0})$, then $V$ is
invertible and
$S=\left\\{\mathbf{v}_{0}+V\mathbf{x}~{}|~{}\mathbf{x}\in\Delta\right\\}$
where $\Delta=\left\\{\mathbf{x}\in\mathbb{R}^{2}~{}|~{}\mathbf{x}\geq
0,\mathbf{1}^{\top}\mathbf{x}\leq 1\right\\}$ is a template simplex in
$\mathbb{R}^{2}$. It is clear that the following one-to-one affine mapping
between $S$ and $\Delta$ exists, which is

$T:S\rightarrow\Delta,\mathbf{p}\mapsto
T(\mathbf{p})=V^{-1}(\mathbf{p}-\mathbf{v}_{0}).$ (27)

Therefore, we only need to prove the statement in the special case where
$S=\Delta$.

Given a linear function $\ell(\mathbf{x})=c_{1}x_{1}+c_{2}x_{2}+c_{3}$, we
write $\ell^{-}=\\{\mathbf{x}\in\mathbb{R}^{2}~{}|~{}\ell(\mathbf{x})<0\\}$
and $\ell^{+}=\\{\mathbf{x}\in\mathbb{R}^{2}~{}|~{}\ell(\mathbf{x})\geq 0\\}$.
$S$ is enclosed by three lines provided by $\ell_{1}(\mathbf{x})=x_{1}$,
$\ell_{2}(\mathbf{x})=x_{2}$, and $\ell_{3}(\mathbf{x})=-x_{1}-x_{2}+1$. We
write three vertices of $S$ as
$\mathbf{v}_{0}=(0,0),\mathbf{v}_{1}=(1,0),\mathbf{v}_{2}=(0,1)$. Then,
$f:[-B,~{}B]^{2}\rightarrow\mathbb{R}$ supported on $S$ is expressed as
follows:

$f(\mathbf{x})=\left\\{\begin{array}[]{cc}\mathbf{a}^{\top}\mathbf{x}+b,&\textbf{if}\quad\mathbf{x}\in
S\\\ 0,&\ \textbf{if}\quad\mathbf{x}\in S^{c}\end{array}\right.$ (28)

where
$\mathbf{a}=(f(\mathbf{v}_{1})-f(\mathbf{v}_{0}),f(\mathbf{v}_{2})-f(\mathbf{v}_{0})),b=f(\mathbf{v}_{0})$.
Our goal is to approximate the given piecewise linear function $f$ over $S$ so
that we need to cancel $f$ outside its domain. We first index the polytopes
separated by three lines $\ell_{1}(\mathbf{x})=0,\ell_{2}(\mathbf{x})=0$, and
$\ell_{3}(\mathbf{x})=0$ as
$\mathcal{A}^{(\chi_{1},\chi_{2},\chi_{3})}=\ell_{1}^{\chi_{1}}\cap\ell_{2}^{\chi_{2}}\cap\ell_{3}^{\chi_{3}},\chi_{i}\in\\{+,-\\},i=1,2,3$.
It is clear that $S=\mathcal{A}^{(+,+,+)}$. In addition, we use $\vee$ to
exclude a component. For instance,
$\mathcal{A}^{(\chi_{1},\vee,\chi_{3})}=\ell_{1}^{\chi_{1}}\cap\ell_{3}^{\chi_{3}}$.
It can be easily verified that
$\mathcal{A}^{(\chi_{1},\vee,\chi_{3})}=\mathcal{A}^{(\chi_{1},+,\chi_{3})}\cup\mathcal{A}^{(\chi_{1},-,\chi_{3})}$.

An essential building block expressed by a network in Figure 5(a1) is an
approximate fan-shaped function:

$F(\mathbf{x})=\sigma\circ(h_{1}(\mathbf{x})-\mu\sigma\circ
h_{2}(\mathbf{x})),$ (29)

where $h_{1}(\mathbf{x})=p_{1}^{(1)}x_{1}+p_{2}^{(1)}x_{2}+r^{(1)}$ and
$h_{2}(\mathbf{x})=p_{1}^{(2)}x_{1}+p_{2}^{(2)}x_{2}+r^{(2)}$ are provided by
two linearly independent vectors
$\\{(p_{1}^{(1)},p_{2}^{(1)}),(p_{1}^{(2)},p_{2}^{(2)})\\}$, and $\mu$ is a
positive controlling factor. Please note that (29) is a ReLU network of
depth=2 and width=2 according to our definition. As illustrated in Figure
5(a2), the piecelinear domains of $F(\mathbf{x})$ contain three boundaries and
four polytopes (two of which only allow zero value of $F$). For convenience,
let us write $\Omega_{1}=h_{1}^{+}\cap h^{-}_{2}$ and $\Omega_{2}=(h_{1}-\mu
h_{2})^{-}\cap h^{+}_{2}$. There are three properties of $F(\mathbf{x})$.
First, the common edge shared by $\Omega_{1}$ and $\Omega_{2}$ is
$h_{2}(\mathbf{x})=0$. Second, the size of $\Omega_{2}$ is adjustable by
controlling $\mu$. Note that $h_{1}(\mathbf{x})-\mu h_{2}(\mathbf{x})=0$ can
move very close to $h_{2}(\mathbf{x})=0$ as $\mu\rightarrow\infty$, which
makes $\Omega_{2}$ negligible. In the limiting case, the support of
$F(\mathbf{x})$ converges to the fan-shaped domain $\Omega_{1}$. Because
$h_{1}(\mathbf{x})-\mu h_{2}(\mathbf{x})=0$ is almost parallel to
$h_{2}(\mathbf{x})=0$ when $\mu$ is big enough, we approximate the area of
$\Omega_{2}$ as the product of the length of $h_{2}(\mathbf{x})=0$ within
$[-B,B]^{2}$ and the distance between two lines, which yields
$|\Omega_{2}|\leq{2\sqrt{2}B}/\mu$. Third, the function $F$ over the fan-
shaped area $\Omega_{1}$ is $h_{1}$.

Representing $f$ with a wide network: The discontinuity of $f$ in (65) is a
major challenge of representing the function using a ReLU network. To tackle
this issue, we start from a linear function
$\tilde{f}(\mathbf{x})=\mathbf{a}^{\top}\mathbf{x}+b,\forall\mathbf{x}\in\mathbb{R}^{2}$,
which can be represented by two neurons
$\sigma\circ\tilde{f}-\sigma\circ(-\tilde{f})$. The key idea is to eliminate
$f$ over all polytopes outside $S$. In other words, $\tilde{f}$ over three
fan-shaped polytopes $\mathcal{A}^{(\vee,-,+)},\mathcal{A}^{(-,+,\vee)}$, and
$\mathcal{A}^{(+,\vee,-)}$ should be cancelled.

Let us take the polytope $\mathcal{A}^{(+,\vee,-)}$ as an example. Note that
$\mathcal{A}^{(+,\vee,-)}$ has two boundaries $\ell_{1}(\mathbf{x})=0$ and
$\ell_{3}(\mathbf{x})=0$ as illustrated in Figure 5(b2). We choose a
sufficiently large positive number $\mu$ to construct the three fan-shaped
functions:

$\displaystyle
F_{1}^{(+,\vee,-)}(x_{1},x_{2})=\sigma(x_{1}-\mu\sigma(-x_{1}-x_{2}+1))$ (30)
$\displaystyle F_{2}^{(+,\vee,-)}(x_{1},x_{2})=\sigma(x_{1}-\eta
x_{2}-\mu\sigma(-x_{1}-x_{2}+1))$ $\displaystyle
F_{3}^{(+,\vee,-)}(x_{1},x_{2})=\sigma(x_{1}-\eta-\mu\sigma(-x_{1}-x_{2}+1)),$

where the positive number $\eta$ is chosen to be small enough such that the
lines $x_{1}-\eta x_{2}=0$ and $x_{1}-\eta=0$ are very close to $x_{1}=0$,
then $\mathfrak{m}((x_{1})^{+}\cap(x_{1}-\eta x_{2})^{-})<2\sqrt{2}B\eta$ and
$\mathfrak{m}((x_{1})^{+}\cap(x_{1}-\eta)^{-})<2\sqrt{2}B\eta$. According to
the aforementioned properties of fan-shaped functions, we approximately have

$\displaystyle F_{1}^{(+,\vee,-)}(\mathbf{x})$
$\displaystyle=x_{1},\quad\quad\quad\quad\forall\mathbf{x}\in\mathcal{A}^{(+,\vee,-)}$
(31) $\displaystyle F_{2}^{(+,\vee,-)}(\mathbf{x})$ $\displaystyle=x_{1}-\eta
x_{2},\quad\forall\mathbf{x}\in\mathcal{A}^{(+,\vee,-)}\backslash\Big{(}(x_{1})^{+}\cap(x_{1}-\eta
x_{2})^{-}\Big{)}$ $\displaystyle F_{3}^{(+,\vee,-)}(\mathbf{x})$
$\displaystyle=x_{1}-\eta,\quad\quad\forall\mathbf{x}\in\mathcal{A}^{(+,\vee,-)}\backslash\Big{(}(x_{1})^{+}\cap(x_{1}-\eta)^{-}\Big{)}.$

Let us find $\omega_{1}^{*},\omega_{2}^{*},\omega_{3}^{*}$ by solving

$\begin{bmatrix}1&1&1\\\ 0&-\eta&0\\\
0&0&-\eta\end{bmatrix}\begin{bmatrix}\omega_{1}\\\ \omega_{2}\\\
\omega_{3}\end{bmatrix}=-\begin{bmatrix}a_{1}\\\ a_{2}\\\ b\end{bmatrix}.$
(32)

Then, the new function
$F^{(+,\vee,-)}(\mathbf{x})=\omega_{1}^{*}F_{1}^{(+,\vee,-)}(\mathbf{x})+\omega_{2}^{*}F_{2}^{(+,\vee,-)}(\mathbf{x})+\omega_{3}^{*}F_{3}^{(+,\vee,-)}(\mathbf{x})$
satisfies

$\displaystyle\mathfrak{m}\Big{(}\\{\mathbf{x}\in~{}\mathcal{A}^{(+,\vee,-)}|~{}\tilde{f}(\mathbf{x})+F^{(+,\vee,-)}(\mathbf{x})\neq
0\\}\Big{)}$ (33) $\displaystyle<2\sqrt{2}B(2\eta+3/\mu).$

Similarly, we can construct $F^{(\vee,-,+)}$ and $F^{(-,+,\vee)}$ to eliminate
$\tilde{f}$ on $\mathcal{A}^{(\vee,-,+)}$ and $\mathcal{A}^{(-,+,\vee)}$
respectively. Finally, these fan-shaped functions are aggregated to form the
following ReLU network $\mathbf{N}_{1}$ (illustrated in Figure 5(b1)):

$\displaystyle\mathbf{N}_{1}(\mathbf{x})=$
$\displaystyle\sigma\circ(\tilde{f}(\mathbf{x}))-\sigma\circ(-\tilde{f}(\mathbf{x}))$
(34)
$\displaystyle+F^{(\vee,-,+)}(\mathbf{x})+F^{(+,\vee,-)}(\mathbf{x})+F^{(-,+,\vee)}(\mathbf{x}),$

where the width and depth of the network are $2+3\times 3\times 2=20$ and 3
respectively. In addition, due to the 9 fan-shaped functions being utilized
and the effect of the $\eta$, the total area of the regions suffering from
errors is no more than

$2\sqrt{2}B(6\eta+9/\mu).$ (35)

Therefore, for any $\delta>0$, as long as we choose $\eta$ and $\mu$
satisfying

$0<\eta,1/\mu<\frac{\delta}{2\sqrt{2}B(6+9)}=\frac{\delta}{30\sqrt{2}B},$ (36)

the constructed wide network $\mathbf{N}_{1}$ will have

$\mathfrak{m}\left(\\{\mathbf{x}\in\mathbb{R}^{2}~{}|~{}f(\mathbf{x})\neq\mathbf{N}_{1}(\mathbf{x})\\}\right)<\delta.$
(37)

Representing $f$ with a deep network: Allowing more layers in a network
provides an alternate way to represent $f$. The fan-shaped functions remain to
be used. The whole pipeline can be divided into two steps: (1) build a
function over $S$; and (2) represent $f$ over $S$ by slightly moving one
boundary of $S$ to create linear independent bases.

(1) Let $F(x_{1},x_{2})=\sigma\circ(x_{1}-\mu\sigma\circ(-x_{2}))$ and
$F^{{}^{\prime}}(x_{1},x_{2})=\sigma\circ(x_{1}-\nu
x_{2}-\mu\sigma\circ(-x_{2}))$, both of which are approximately enclosed by
boundaries $x_{1}=0$ and $x_{2}=0$. Therefore, the fan-shaped regions of
$F(x_{1},x_{2})$ and $F^{{}^{\prime}}(x_{1},x_{2})$ almost overlap as $\nu$ is
small. The negative sign for $x_{2}$ is to make sure that the fan-shaped
region is $S$. To obtain the third boundary $\ell_{3}(\mathbf{x})=0$ for
building the simplex $S$, we stack one more layer with only one neuron to
separate the fan-shaped region of $F(x_{1},x_{2})$ with the boundary
$-x_{1}-x_{2}+1=0$ as follows:

$\mathbf{N}_{2}^{1}(\mathbf{x})=(\gamma_{1}^{*}F(\mathbf{x})+\gamma_{2}^{*}F^{\prime}(\mathbf{x})+\gamma_{3}^{*})^{+},$
(38)

where $(\gamma_{1}^{*},\gamma_{2}^{*},\gamma_{3}^{*})$ are roots of the
following system of equations:

$\begin{cases}\gamma_{1}+\gamma_{2}=-1&\\\ -\nu\gamma_{2}=-1&\\\
\gamma_{3}=1.\end{cases}$ (39)

Thus, $\mathbf{N}_{2}^{1}(x_{1},x_{2})$ will represent the function
$-x_{1}-x_{2}+1$ over $S$ and zero in the rest area. The depth and width of
$\mathbf{N}_{2}^{1}(x_{1},x_{2})$ are 3 and 4 respectively. Similarly, due to
the employment of the two fan-shaped functions and the effect of $\nu$, the
area of the region with errors is estimated as

$2\sqrt{2}B\left(\nu+2/\mu\right).$ (40)

(2) To acquire $f$ over $S$, similarly we need three linear independent
functions as linear independent bases. We modify $\ell_{3}$ slightly to get
$\ell_{3}^{{}^{\prime}}=\ell_{3}-\tau^{\prime}x_{1}$ and
$\ell_{3}^{{}^{\prime\prime}}=\ell_{3}-\tau^{\prime\prime}x_{2}$. Repeating
the procedure described in (1), for $\ell_{3}^{{}^{\prime}}$ we construct the
network $\mathbf{N}_{2}^{2}(x_{1},x_{2})$ that is
$\ell_{3}-\tau^{\prime}x_{1}$ over
$\ell_{1}^{+}\cap\ell_{2}^{+}\cap(\ell_{3}^{{}^{\prime}})^{+}$, while for
$\ell_{3}^{{}^{\prime\prime}}$ we construct the network
$\mathbf{N}_{2}^{3}(x_{1},x_{2})$ that is $\ell_{3}-\tau^{\prime}x_{1}$ over
$\ell_{1}^{+}\cap\ell_{2}^{+}\cap(\ell_{3}^{{}^{\prime\prime}})^{+}$. We set
positive numbers $\tau^{\prime}$ and $\tau^{\prime\prime}$ small enough to
have two triangular domains
$\ell_{1}^{+}\cap\ell_{2}^{+}\cap(\ell_{3}^{{}^{\prime}})^{+}$ and
$\ell_{1}^{+}\cap\ell_{2}^{+}\cap(\ell_{3}^{{}^{\prime\prime}})^{+}$ almost
identical with $S$. In addition, let $\tau^{\prime}$ and $\tau^{\prime\prime}$
satisfy

$\begin{bmatrix}-1&-1-\tau^{\prime}&-1\\\ -1&-1&-1-\tau^{\prime\prime}\\\
1&1&1\end{bmatrix}\begin{bmatrix}\rho_{1}^{*}\\\ \rho_{2}^{*}\\\
\rho_{3}^{*}\end{bmatrix}=\begin{bmatrix}a_{1}\\\ a_{2}\\\ b\end{bmatrix},$
(41)

where $\rho_{1}^{*},\rho_{2}^{*},\rho_{3}^{*}$ are solutions. As a
consequence, the deep network (illustrated in Figure 5 (c1)):

$\mathbf{N}_{2}(\mathbf{x})=\rho_{1}^{*}\mathbf{N}_{2}^{1}(\mathbf{x})+\rho_{2}^{*}\mathbf{N}_{2}^{2}(\mathbf{x})+\rho_{3}^{*}\mathbf{N}_{2}^{3}(\mathbf{x})$
(42)

produces $f$ on $S$. The depth and width of the network are 4 and 12
respectively. Similarly, the area of the region with errors is bounded above
by

$2\sqrt{2}B\left(3\nu+\tau^{\prime}+\tau^{\prime\prime}+6/\mu)\right).$ (43)

Therefore, for any $\delta>0$, if we choose

$0<\nu,\tau^{\prime},\tau^{\prime\prime},1/\mu<\frac{\delta}{2\sqrt{2}B(3+2+6)}=\frac{\delta}{22\sqrt{2}B}$
(44)

then the constructed deep network $\mathbf{N}_{2}$ will satisfy

$\mathfrak{m}\left(\\{\mathbf{x}\in\mathbb{R}^{2}|f(\mathbf{x})\neq\mathbf{N}_{2}(\mathbf{x})\\}\right)<\delta.$
(45)

∎

#### Proof of Theorem 3, D=2

According to Proposition 2, the network $h$ is piecewise linear and splits the
space into polytopes. It is feasible to employ a number of simplices to fill
the polytopes defined by $h$ [ehrenborg2007perles]. Given that $M$ is the
number of required simplices, by aggregating the wide network
$\mathbf{N}_{1}(x_{1},x_{2})$ concurrently and stacking the deep network
$\mathbf{N}_{2}(x_{1},x_{2})$ longitudinally, we have the following wide and
deep networks respectively:

$\displaystyle\mathbf{H}_{1}(\mathbf{x})=\sum_{m=1}^{M}\mathbf{N}_{1}^{(m)}(x_{1},x_{2})$
(46)
$\displaystyle\mathbf{H}_{2}(\mathbf{x})=\mathbf{\tilde{N}}_{2}^{(M)}(x_{1},x_{2},\cdot\cdot,\mathbf{\tilde{N}}_{2}^{(2)}(x_{1},x_{2},\mathbf{N}_{2}^{(1)}(x_{1},x_{2}))\cdot\cdot)),$

where $\mathbf{N}_{1}^{(m)}(x_{1},x_{2})$ represents the linear function over
the $m^{th}$ simplex,
$\mathbf{\tilde{N}}_{2}^{(m)}(x_{1},x_{2},t)=\mathbf{N}_{2}^{(m)}(x_{1},x_{2})+t$,
and $\mathbf{N}_{2}^{(m)}(x_{1},x_{2})$ represents the linear function also
over the $m^{th}$ simplex. Therefore, the constructed wide network
$\mathbf{H}_{1}(\mathbf{x})$ is of width $\mathcal{O}(20M)$ and depth $3$,
while the constructed deep network $\mathbf{H}_{2}(\mathbf{x})$ is of depth
$\mathcal{O}(4M)$ and width $12$. In [montufar2014number], the number of
polytopes characterized by a feed-forward network is no more than $2^{n}$,
where $n$ is the number of neurons in the network. It is clear that the width
$\mathcal{O}(20M)$ of the wide network dominates, and the depth
$\mathcal{O}(4M)$ of the deep network dominates. $\square$

##  7 Supplementary Information

### Width and Depth as Related to Neural Tangent Kernel (NTK)

1\. Review the prior works on NTK: NTK sheds light on the power of a network
when the width of this network goes to infinity. Previous results have
suggested a link between the neural network and the Gaussian distribution when
the network width increases infinitely. In [neal1996priors, lee2017deep,
matthews2018gaussian, novak2018bayesian, arora2019exact], the Gaussian process
is shown in the two-layer networks, the deep networks, and the convolutional
networks. Weakly-trained networks [arora2019exact] refer to the networks where
only the top layer is trained after other layers are randomly initialized. Let
$f(\bm{\theta},x)\in\mathbb{R}$ denote the output of the network on input $x$
where $\bm{\theta}$ denotes the parameters of the network, and $\bm{\theta}$
is an initialization over $\bm{\Theta}$. In the above context, training the
top layer with the $l_{2}$ penalty reduces to the kernel regression:

$ker^{(F)}(x,x^{\prime})=\underset{\bm{\theta}\sim\bm{\Theta}}{\mathbb{E}}\langle
f(\bm{\theta},x),f(\bm{\theta},x^{\prime})\rangle,$ (47)

where $(F)$ denotes the functional space. On the other hand, an infinite wide
network is considered as an over-parameterized network, with the motivation to
explain the fact that why over-paramterized networks scale. There were
extensive studies on this topic [du2018gradient, allen2019learning,
cao2019generalization]. Notably, these studies indicate that the training
renders relatively small changes when the network is sufficiently wide. Such a
concentration behavior is justified by NTK in terms of the Gaussian process.
The NTK is defined as the following:

$ker^{(\partial)}(x,x^{\prime})=\underset{\bm{\theta}\sim\bm{\Theta}}{\mathbb{E}}\langle\frac{\partial
f(\bm{\theta},x)}{\partial\bm{\theta}},\frac{\partial
f(\bm{\theta},x^{\prime})}{\partial\bm{\theta}}\rangle$ (48)

where $(\partial)$ denotes the gradient space. Along this line, K. Huang et
al. [huang2020deep] compared the NTK of the ResNet and the deep chain-like
network, and found that the NTK of the chain-like network converges to a non-
informative kernel as the depth goes to infinity, while the counterpart of
ResNet does not. S. S. Du et al. [du2019width] showed that the width provably
matters in networks using the piecewise linear activation.

2\. Theoretical results: Now, we define a one-hidden-layer network and a one-
neuron-wide network in Figure 6. Let $x\in\mathbb{R}$ and each neuron without
the bias term in the wide network contributes equally, then the function
expressed by this wide network is

$f^{(w)}(x)=\frac{1}{N}\sum_{i=1}^{N}\sigma(a_{i}x),$ (49)

where $N$ is the number of neurons or width, $\sigma$ is the ReLU function,
and $(w)$ signifies that the network is wide.

In contrast, the deep network has shortcuts which are used to aggregate the
yields of all the hidden neurons as well as the input into the output neuron.
Such a topology was extensively studied in [fan2018universal]. We also assume
that each intermediate neuron contributes equally. But for the input neuron,
we set its weight to $-1$, and later we will show why this setup is important.
The representation of the deep network is recursively defined as

$\displaystyle f_{0}(x)=x$ (50) $\displaystyle
f_{i+1}=\sigma(a_{i}f_{i}(x)),i\geq 0$ $\displaystyle
f^{(d)}(x)=\frac{1}{N}\sum_{i=1}^{N}f_{i}(x)-x.$

It is seen that the number of parameters is the same for the wide and deep
networks, which implies that they are symmetric in terms of not only structure
but also complexity. As observed in [neal1996priors], $f^{(w)}(x)$ tends to
give identical and independent distribution (i.i.d.) Gaussian distributions in
the infinite-width limit. In symmetry, here we show that $f^{(d)}$ will also
behave as an i.i.d. Gaussian process in the infinite-depth limit.

Figure 6: In the univariate input situation, both increasing the width of the
wide network with the structure (a) and increasing the depth of the deep
network with the structure (b) can lead to the Gaussian process behavior.

######  Theorem 6.

For a ReLU network defined by (50), where each parameter $a_{i}$ is
initialized with $\mathcal{N}(0,1)$ and $x\geq 0$, as $N\to\infty$, the output
function $f^{(d)}(x)$ tends to be an i.i.d. Gaussian distribution.

###### Proof.

First, we show $\mathbb{E}[f_{k}(x)]=x,k\geq 1$ with mathematical induction.
$f_{0}(x)=x$ holds true. While if $\mathbb{E}[f_{i}(x)]=x$, apply the law of
total expectation $\mathbb{E}[X]=\mathbb{E}[\mathbb{E}[X|Y]]$, we have

$\begin{split}\mathbb{E}[f_{i+1}(x)]&=\mathbb{E}[\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\sigma(a_{i}f_{i}(x))\exp(-\frac{a_{i}^{2}}{2})da_{i}]\\\
&=\mathbb{E}[\frac{1}{\sqrt{2\pi}}\int_{a_{i}f_{i}(x)>0}a_{i}f_{i}(x)\exp(-\frac{a_{i}^{2}}{2})da_{i}]\\\
&=\mathbb{E}[f_{i}(x)\frac{1}{\sqrt{2\pi}}\int_{0}^{+\infty}a_{i}\exp(-\frac{a_{i}^{2}}{2})da_{i}]\\\
&=\mathbb{E}[f_{i}(x)]\ \ \ \ \ \mbox{(note:
$\frac{1}{\sqrt{2\pi}}\int_{0}^{+\infty}a_{i}\exp(-\frac{a_{i}^{2}}{2})da_{i}=\frac{1}{\sqrt{2\pi}}\int_{0}^{+\infty}\exp(-\frac{a_{i}^{2}}{2})d\frac{a_{i}^{2}}{2}=1$)
}\\\ &=x.\end{split}$ (51)

Second, we inspect the structure of $f^{(d)}(x)$,
$f^{(d)}(x)=\frac{1}{N}\sum_{i=1}^{N}f_{i}(x)-x$. Because the mean of each
term in $\frac{1}{N}\sum_{i=1}^{N}f_{i}(x)$ is identical, plus the variance of
each term is trivially bounded, $\frac{1}{N}\sum_{i=1}^{N}f_{i}(x)$ follows
the central limit theorem. As $N\to\infty$,
$\frac{1}{N}\sum_{i=1}^{N}f_{i}(x)$ will be Gaussian distributed with the mean
$x$. By the constant shift $-x$, $f^{(d)}(x)$ will be Gaussian distributed
with the mean $0$ for any $x$ (Here is the reason why we need to assign $-1$
as the weight to the input).

Third, based on the above fact, for any finite collection of $f^{(d)}(x)$:
$\\{f^{(d)}(x^{(1)}),...,f^{(d)}(x^{(Q)})\\}$, where $Q$ is the length, as the
network goes very deep, $\frac{1}{q}\sum_{q=1}^{Q}f^{(d)}(x^{(q)})$ is also
Gaussian distributed, which means that the collection of
$\\{f^{(d)}(x^{(1)}),...,f^{(d)}(x^{(Q)})\\}$ will have a joint multivariate
Gaussian distribution, which is exactly the definition of a Gaussian process.
∎

### Properties of the Partially Separable Representation

Let us compare the properties of the partially separable representation with
those of the piecewise polynomial representation and the Kolmogorov–Arnold
representation in terms of universality, finiteness, decomposability and
smoothness. As a result, the partially separable representation is well
justified.

1\. Universality: The representation should have a sufficient ability to
express the functions. A piecewise polynomial representation is capable of
representing any continuous function in a local way. The Kolmogorov–Arnold
representation theorem states that every multivariate continuous function can
be represented as a combination of continuous univariate functions, which
solves a generalized Hilbert thirteen problem. Therefore, the
Kolmogorov–Arnold representation also possesses universality. As far as the
partially separable representation is concerned, its universality in the
$L_{1}$ distance is analyzed in the above Taylor expansion analysis. In
summary, these three representation classes are all powerful enough to express
continuous functions.

2\. Finiteness: The multivariate Taylor expansion can approximate a general
continuous function $f\in\mathcal{F}^{n,k}$ with a finite number of terms.
Although the proof in the manuscript devises a specific strategy of obtaining
a partially separable representation, the partially separable representation
actually allows a variety of constructions in addition to the Taylor
expansion. There is no fundamental reason that the partially separable
representation will necessarily have exponentially many terms in a majority of
practical tasks after reasonable assumptions are incorporated.

3\. Decomposability: Decomposability is to decode the functionality of the
model in terms of its building units, i.e., cells, layers, blocks, and so on.
A plethora of engineering examples, such as software development and optical
system design, have shown that modularized analysis is effective.
Particularly, modularizing a neural network is advantageous for the model
interpretability. For example, X. Chen et al. [chen2016infogan] developed
InfoGAN to enhance decomposability of features learned by GAN
[goodfellow2014generative], where InfoGAN maximizes the mutual information
between the latent code and the observations, encouraging the use of noise to
encode the semantic concept. Since the partially separable representation is
more decomposable than its counterparts, the network constructed in reference
to the partially separable representation is easily interpretable. For
instance, such a network has simpler partial derivatives that can simplify
interpretability analysis. [lipton2018mythos].

4\. Smoothness: A useful representation should be as smooth as possible such
that the approximation can suppress high-frequency oscillations and be robust
to noise. In the last eighties, Girosi and Poggio claimed that the use of the
Kolmogorov-Arnold representation is doomed because the inner functions and the
outer functions are highly non-smooth [girosi1989representation]. In the
piecewise polynomial representation, the situation gets better since at least
over each interval the representation is smooth. As far as the partially
separable representation is concerned, because the expression is greatly
relaxed (from the exact computation to approximate representation), it is
feasible to make each element smooth as $L$ goes large, and extract meaningful
structures underlying big data.

Table 3: Comparison of the three functional representations, where "✓" means "yes", "X" means "no", and "–" means "mediocre". Representation | Universality | Finiteness | Decomposability | Smoothness
---|---|---|---|---
Piecewise Polynomial | ✓ | X | X | –
Kolmogorov-Arnold | ✓ | ✓ | – | X
Partially Separable | ✓ | – | ✓ | ✓

In summary, we compare the three representation schemes in terms of
universality, finiteness, decomposability and smoothness in Table 3. Clearly,
the partially separable representation is suitable for machine learning tasks.

### Bounds for the Partially Separable Representation

The main idea of our demonstration is to use the Taylor’s expansion and
estimate the remainder, leading to a realization of the partially separable
representation. Based on such a realization, we obtain an upper bound of the
needed width and depth for the partially separable representation. Let
$\partial^{\bm{\alpha}}f(\mathbf{x})=\frac{\partial^{\alpha_{1}}}{\partial
x_{1}}\frac{\partial^{\alpha_{2}}}{\partial
x_{2}}\cdots\frac{\partial^{\alpha_{n}}}{\partial x_{n}}f(\mathbf{x})$,
$\bm{\alpha}!=\prod_{i=1}^{n}\alpha_{i}!$, and
$\mathbf{x}^{\bm{\alpha}}=x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}$, for
the function class $\mathcal{F}^{n,k}=\\{f\in
C^{k+1}([0,~{}1]^{n})~{}|~{}\|\partial^{\bm{\alpha}}f\|_{\infty}\leq
M,\quad\forall|\bm{\alpha}|\leq k\\}$, the following theorem holds.

######  Theorem 7.

For any $f\in\mathcal{F}^{n,k}$, if $\mathbf{x}\in[0,1]^{n}$, there exists a
quadratic network $\mathcal{Q}(\mathbf{x})$ with the width no more than
$k{n+k\choose n}$ and the depth no more than $\log_{2}{(kn)}$ to represent $f$
in the partially separable representation, satisfying that

$\sup_{\mathbf{x}\in[0,1]^{n}}|f(\mathbf{x})-\mathcal{Q}(\mathbf{x})|\leq\frac{M}{(k+1)!}n^{k+1}.$
(52)

###### Proof.

Let $f\in\mathcal{F}^{n,k}$, if $\mathbf{x}\in[0,1]^{n}$, then based on
classical multivariate calculus [widder1989advanced],

$f(\mathbf{x})=\sum_{|\bm{\alpha}|\leq
k}\frac{\partial^{\bm{\alpha}}}{\bm{\alpha}!}f(\bm{0})\mathbf{x}^{\bm{\alpha}}+R_{\mathbf{x},k}(\mathbf{x}),$
(53)

where $R_{\mathbf{x},k}(\mathbf{x})$ is the remainder term. For any
$\mathbf{x}\in[0,1]^{n}$, we have

$R_{\mathbf{x},k}(\mathbf{x})\leq\frac{M}{(k+1)!}(|x_{1}|+|x_{2}|+\cdots+|x_{n}|)^{k+1}\leq\frac{M}{(k+1)!}n^{k+1}.$
(54)

It is observed from Eqs. 53 and 54 that, given $f\in\mathcal{F}^{n,k}$, the
Taylor expansion forms a partially separable representation
$\sum_{|\bm{\alpha}|\leq
k}\frac{\partial^{\bm{\alpha}}}{\bm{\alpha}!}f(\bm{0})\mathbf{x}^{\bm{\alpha}}$
with ${n+k\choose n}$ products, and the error is no more than
$\frac{M}{(k+1)!}n^{k+1}$. Along this line, we apply the quadratic network to
express $\sum_{|\bm{\alpha}|\leq
k}\frac{\partial^{\bm{\alpha}}}{\bm{\alpha}!}f(\bm{0})\bm{x}^{\bm{\alpha}}$.
Any univariate polynomial of degree $N$ can be computed by a quadratic network
using the ReLU function with the depth of $\log_{2}(N)$ and the width of $N$.
To approximate a general term
$\frac{\partial^{\bm{\alpha}}}{\bm{\alpha}!}f(\bm{0})\bm{x}^{\bm{\alpha}}=\frac{\partial^{\bm{\alpha}}}{\bm{\alpha}!}f(\bm{0})x_{1}^{\alpha_{1}}\cdots
x_{n}^{\alpha_{n}}$, the depth of the quadratic network is no more than
$\log_{2}({\max\\{\alpha_{1},\cdots,\alpha_{n}\\}})\leq\log_{2}{k}$, and the
width is no more than $\sum_{i=1}^{n}\alpha_{i}=k$. In addition, the depth of
a network that is used to express the product of $n$ terms is $\log_{2}{n}$.
Therefore, the depth is no more than $\log_{2}{k}+\log_{2}{n}=\log_{2}{(kn)}$.
In contrast, the width is no more than $k{n+k\choose n}$, considering that
there are ${n+k\choose n}$ terms in $\sum_{|\bm{\alpha}|\leq
k}\frac{\partial^{\bm{\alpha}}}{\bm{\alpha}!}f(\bm{x})\bm{x}^{\bm{\alpha}}$. ∎

### Proof of De Morgan Duality

###### Proof.

As illustrated in Figures 7 and 8, we provide the scheme to construct a wide
network $\mathbf{H}_{1}(\mathbf{x})$ and a deep network
$\mathbf{H}_{2}(\mathbf{x})$ respectively in light of the De Morgan law based
on hypercubes in a high-dimensional space, which is an extension for the
univariate results in our initial submission. To represent the rule $A_{i}$
that is equivalent to $g_{i}(\mathbf{x})$, a trapezoid function is built in
the deep network, whereas a trap-like function is constructed to represent
$\neg A_{i}$ that is equivalent to $1-g_{i}(\mathbf{x})$. In our construction,
for each hypercube the measures of
$\\{\mathbf{x}\in\Gamma_{i}|\mathbf{H}_{1}(\mathbf{x})\neq
g_{i}(\mathbf{x})\\}$ and
$\\{\mathbf{x}\in\Gamma_{i}|\mathbf{H}_{2}(\mathbf{x})\neq
g_{i}(\mathbf{x})\\}$ are no more than $vol(\Gamma_{i})(1-2\delta)^{n}$, where
$vol(\Gamma_{i})$ is the volume of a hypercube $\Gamma_{i}$. Therefore, the
total measure of errors for all the hypercubes is less than
$\sum_{i}^{n}vol(\Gamma_{i})(1-2\delta)^{n}=(1-2\delta)^{n}\sum_{i}^{n}vol(\Gamma_{i})<(1-2\delta)^{n}$.
As a result, let $\delta<(1-(\epsilon/2)^{1/n})/2$, we have

$\displaystyle\mathfrak{m}\Big{(}\\{\mathbf{x}~{}|\mathbf{H}_{1}(\mathbf{x})\\}\neq\sum_{i=1}^{n}g_{i}(\mathbf{x})\\}\Big{)}<\epsilon/2$
(55)
$\displaystyle\mathfrak{m}\Big{(}\\{\mathbf{x}~{}|\mathbf{H}_{2}(\mathbf{x})\\}\neq\sum_{i=1}^{n}g_{i}(\mathbf{x})\\}\Big{)}<\epsilon/2,$

which lead to

$\mathfrak{m}\Big{(}\\{\mathbf{x}~{}|\mathbf{H}_{1}(\mathbf{x})\\}\neq\mathbf{H}_{2}(\mathbf{x})\\}\Big{)}<\epsilon.$
(56)

∎

Figure 7: A deep network to realize the logic union of propositional rules in
a high-dimensional space. Each propositional rule is associated with a
hypercubic indicator function.  Figure 8: A wide network to realize the
negation of the logic intersection of the negation of propositional rules in a
high-dimensional space. The negation of each propositional rule is associated
with a trap-like indicator function.

### Experiments in Perspective I

The code for our second experiment was also uploaded on our GitHub repository
https://github.com/FengleiFan/Duality. This experiment consists of two parts:
while the first part is a direct construction, the second is to show the
network equivalency numerically.

Wisconsin Breast Cancer Dataset: This database is on UCI Machine Learning
Repository, and can be also found in the SciPy library. In this dataset, ten
real-valued features are calculated for each cell nucleus: a) radius (mean
distance from center to points on the perimeter), b) texture (standard
deviation of gray-scale values), c) perimeter, d) area, e) smoothness (local
variation in radius lengths), f) compactness ($perimeter^{2}/area-1.0)$, g)
concavity (severity of concave portions of the contour), h) concave points
(number of concave portions of the contour), i) symmetry, j) fractal dimension
("coastline approximation" - 1). The mean, standard error and "worst" or
largest (mean of the three largest values) of these features were computed for
each image, resulting in 30 features. In total, 569 samples are included in
this dataset, where 357 samples are benign while 212 samples are malignant.

Network Training: The eight network architectures in the abstracted view were
constructed, including a deep network, a wide network and others between them,
as shown in Figure 9. Each green box contains four layers with three neurons
per layer while each blue box contains three layers with two neurons per
layer. Taking the network IV be an example, Figure 10 shows its exact
topological structure. From the breast cancer Wisconsin dataset, we only used
five attributes (radius, texture, perimeter, area, smoothness) to show the
equivalency of networks. The reason behind is that if we utilize all the
attributes for classification, the problem is much easier, but it is tricky to
discriminate if the similar performance metrics are due to the network
equivalency or the saturation effect. The cross-entropy loss was utilized for
a classification task, which is mathematically formulated as
$-\sum_{i}(y_{i}\log\hat{y_{i}}+(1-y_{i})\log(1-\hat{y_{i}})$, where $y_{i}$
is the ground truth label and $\hat{y_{i}}$ is the predicted digit. We
randomly initialized all the parameters of each network configurations 20
times using the Gaussian distribution with mean of 0 and variance of 0.8. The
network was optimized using Adam algorithm with a batch size of 569 for each
iteration. The total number of iteration was set to 100,000 with the learning
rate=0.0001 on an Intel CORE i7 CPU, being consistent to what we did in the
first experiment.

Figure 9: Network architectures comprising of a deep network, a wide network
and others between them used in the breast cancer detection example. Figure
10: Structural details of the network IV. Each green box contains four layers
with three neurons per layer while each blue box contains three layers with
two neurons per layer.

Evaluation: The classification accuracy of the eight networks are summarized
in Table 4. According to the computation for the data, the mean performance
difference between any two networks is no more than 0.0102, which suggests
that the eight networks perform similarly. For rigor, we conducted the
independent samples t-test, and the obtained p-values between results of any
two networks are shown in Table 5. The null hypothesis is that data in two
groups are from populations with equal means, without assuming that the
populations also have equal variances. The lowest p-value 0.0517 is from the
results of networks II and V, which is not sufficient to reject that the
networks II and V behave differently. For the most of p-values, they are much
larger than what suffices not to reject the null hypothesis. Such similarities
suggest the existence of equivalent networks. In this regard, duality between
a wide network and a deep network becomes a special case of a family of
equivalent networks in the light of Boolean algebra.

Table 4: The classification accuracy of the eight networks in 20 random initializations. | I | II | III | IV | V | VI | VII | VIII
---|---|---|---|---|---|---|---|---
1 | 0.920914 | 0.931459 | 0.926186 | 0.936731 | 0.919156 | 0.920914 | 0.931459 | 0.945518
2 | 0.920914 | 0.940246 | 0.927944 | 0.922671 | 0.920914 | 0.927944 | 0.920914 | 0.945518
3 | 0.938489 | 0.922671 | 0.920914 | 0.922671 | 0.922671 | 0.922671 | 0.912127 | 0.919156
4 | 0.920914 | 0.936731 | 0.920914 | 0.933216 | 0.920914 | 0.929701 | 0.920914 | 0.917399
5 | 0.926186 | 0.922671 | 0.936731 | 0.945518 | 0.917399 | 0.926186 | 0.931459 | 0.920914
6 | 0.919156 | 0.922671 | 0.929701 | 0.924429 | 0.922671 | 0.927944 | 0.926186 | 0.949033
7 | 0.926186 | 0.924429 | 0.926186 | 0.920914 | 0.938489 | 0.924429 | 0.922671 | 0.920914
8 | 0.942003 | 0.920914 | 0.920914 | 0.936731 | 0.922671 | 0.920914 | 0.903339 | 0.933216
9 | 0.922671 | 0.927944 | 0.929701 | 0.922671 | 0.927944 | 0.920914 | 0.906854 | 0.938489
10 | 0.920914 | 0.931459 | 0.929701 | 0.933216 | 0.931459 | 0.934974 | 0.924429 | 0.926186
11 | 0.922671 | 0.920914 | 0.940246 | 0.926186 | 0.922671 | 0.926186 | 0.927944 | 0.927944
12 | 0.929701 | 0.933216 | 0.922671 | 0.922671 | 0.908611 | 0.938489 | 0.940246 | 0.920914
13 | 0.920914 | 0.936731 | 0.927944 | 0.919156 | 0.945518 | 0.917399 | 0.927944 | 0.920914
14 | 0.922671 | 0.920914 | 0.934974 | 0.940246 | 0.933216 | 0.922671 | 0.936731 | 0.917399
15 | 0.929701 | 0.936731 | 0.919156 | 0.934974 | 0.920913 | 0.943761 | 0.919156 | 0.919156
16 | 0.920914 | 0.936731 | 0.936731 | 0.924429 | 0.919156 | 0.927944 | 0.933216 | 0.919156
17 | 0.927944 | 0.920914 | 0.922671 | 0.926186 | 0.926186 | 0.920914 | 0.906854 | 0.924429
18 | 0.922671 | 0.922671 | 0.931459 | 0.919156 | 0.929701 | 0.942003 | 0.922671 | 0.920914
19 | 0.938489 | 0.933216 | 0.922671 | 0.936731 | 0.910369 | 0.931459 | 0.936731 | 0.920914
20 | 0.933216 | 0.942003 | 0.922671 | 0.920914 | 0.922671 | 0.933216 | 0.922671 | 0.926186
Table 5: The p-values between experimental results of all the paired networks. | I | II | III | IV | V | VI | VII | VIII
---|---|---|---|---|---|---|---|---
I |  | 0.2048 | 0.5823 | 0.3734 | 0.3790 | 0.4633 | 0.3483 | 0.8984
II |  |  | 0.4168 | 0.7448 | 0.0517 | 0.6003 | 0.0588 | 0.3679
III |  |  |  | 0.6684 | 0.1676 | 0.8073 | 0.1692 | 0.7668
IV |  |  |  |  | 0.1083 | 0.8568 | 0.1113 | 0.5440
V |  |  |  |  |  | 0.1364 | 0.8847 | 0.3967
VI |  |  |  |  |  |  | 0.1381 | 0.6405
VII |  |  |  |  |  |  |  | 0.3607

### Transformation of an Arbitrary Network

######  Definition 4.

We call a wide network $\mathbf{N}_{1}:\Omega\rightarrow\mathbb{R}$ is dual to
a deep network $\mathbf{N}_{2}:\Omega\rightarrow\mathbb{R}$, if
$\mathbf{N}_{1}(\mathbf{x})=\mathbf{N}_{2}(\mathbf{x}),\forall x\in\Omega$. We
call a wide network $\mathbf{N}_{1}$ is $\delta$-dual to a deep network
$\mathbf{N}_{2}$, if for any $\delta>0$,
$\mathfrak{m}(\\{\mathbf{x}\in\Omega~{}|~{}\mathbf{N}_{1}(\mathbf{x})\neq\mathbf{N}_{2}(\mathbf{x})\\}<\delta$,
where $\mathfrak{m}$ is a measurement defined on $\Omega$.

Our study on the above-defined duality is focused on ReLU networks, because
currently they are most popular in deep learning. For convenience, we use
$\sigma(\cdot)=\max\\{\cdot,0\\}$ to denote the ReLU function. We denote the
domain of a network as $\Omega=[-B,B]^{D}$. Now, we investigate how to
transform an arbitrary network to a wide network or a deep network.
Considering that the constructed network consists of shortcuts, it is
necessary to clarify the definition of the width and depth of a neural
network. It is known that every neuron is directly or indirectly wired with
the input through one or more routes.

######  Definition 5.

Denote the length of one route between a neuron and the input as the number of
affine operations. We define that two neurons are in the same layer if they
have the routes sharing the same length. Then, the width is defined as the
maximum number of neurons in a layer, whereas the depth is defined as the
length of the longest route in the network.

######  Proposition 2.

Suppose that $f(\mathbf{x})$ is a function represented by a ReLU network, then
$f$ is a piecewise linear function that splits the space into polytopes, where
each polytope can be seamlessly filled with a number of simplices.

###### Proof.

Because of the affine transform and the piecewise linear function ReLU,
$f(\mathbf{x})$ will partition the space into polytopes, each of which is
defined by a linear function. A feedforward ReLU network partitions the space
into convex polytopes [chu2018exact], whereas a ReLU network with shortcuts
may create non-convex polytopes. Nevertheless, those non-convex polytopes are
de facto obtained by convex polytopes because a network with shortcuts can be
taken as the combination of several branches of feedforward networks. Clearly,
the polytopes by $f(\mathbf{x})$ can be seamlessly filled with a number of
simplices. ∎

######  Theorem 8 (ReLU Duality for Univariate Networks).

Given any ReLU network $f:[-B,~{}B]\rightarrow\mathbb{R}$ with one dimensional
input and output variables. There is a wide ReLU network
$\mathbf{H}_{1}:[-B,~{}B]\rightarrow\mathbb{R}$ and a deep ReLU network
$\mathbf{H}_{2}:[-B,~{}B]\rightarrow\mathbb{R}$, such that
$f(x)=\mathbf{H}_{1}(x)=\mathbf{H}_{2}(x),\forall x\in[-B,~{}B]$.

######  Theorem 9 (ReLU Duality for Multivariate Networks).

Suppose that the representation of an arbitrary ReLU network is
$h:[-B,~{}B]^{D}\to\mathbb{R}$, for any $\delta>0$, there exist both a wide
network $\mathbf{H}_{1}$ of width $\mathcal{O}\left[D(D+1)(2^{D}-1)M\right]$
and depth $D+1$, as well as a deep network $\mathbf{H}_{2}$ of width
$(D+1)D^{2}$ and depth $\mathcal{O}\left[(D+2)M\right]$, where $M$ is the
minimum number of simplices to cover the polytopes to support $h$, satisfying

$\displaystyle\mathfrak{m}\Big{(}\\{\mathbf{x}~{}|~{}h(\mathbf{x})\neq\mathbf{H}_{1}(\mathbf{x})\\}\Big{)}<\delta$
(57)
$\displaystyle\mathfrak{m}\Big{(}\\{\mathbf{x}~{}|~{}h(\mathbf{x})\neq\mathbf{H}_{2}(\mathbf{x})\\}\Big{)}<\delta,$

where $\mathfrak{m}(\cdot)$ is the standard measure in $[-B,~{}B]^{D}$.

Experiment: A 2-6-2-1 network was trained on the moon dataset. When the
training process was finished, the accuracy of the network was 0.94. Then, we
transformed the original network into a wide network ($\mu=80$) and a deep
network ($\mu=5$) using the procedures described in the proof of Theorem 9.
The patterns of outputs of the constructed wide network and deep network are
respectively shown in Figure 11. It is seen that the constructed networks can
approximate the original network well, and some expected artifacts can be
squeezed by further increasing $\mu$ or using a post-processing network that
can identify streaks and remove them.

Figure 11: With the procedure in the proof for Theorem 9, an exemplary 2-6-2-1
network is transformed into a wide network ($\mu=80$) and a deep network
($\mu=5$) respectively.

###### Proof.

(Theorem 8) Since the function represented by a network
$f:[-B,~{}B]\to\mathbb{R}$ is piecewise linear, we express $f(x)$ as

$f(x)=\begin{cases}w^{(0)}(x-x_{0})+f(x_{0}),&x\in[x_{0},x_{1})\\\
w^{(1)}(x-x_{1})+f(x_{1}),&x\in[x_{1},x_{2})\\\
w^{(2)}(x-x_{2})+f(x_{2}),&x\in[x_{2},x_{3})\\\ \ \ \ \ \ \ \ \ \ \ \ \
\vdots\\\ w^{(n)}(x-x_{n})+f(x_{n}),&x\in[x_{n},x_{n+1}],\end{cases}$ (58)

where $-B=x_{0}<x_{1}<x_{2}<\cdots<x_{n}<x_{n+1}=B$, $\displaystyle
w^{(i)}=\frac{f(x_{i+1})-f(x_{i})}{x_{i+1}-x_{i}}$ to guarantee continuity,
and the slopes of neighboring pieces are different; otherwise they can be
fused together.

We first construct a wide network $\mathbf{H}_{1}(x)$ to represent $f$. This
can be constructed straightforwardly as follows:

$\displaystyle\mathbf{H}_{1}(x)=f(x_{0})+\sum_{i=0}^{n}(w^{(i)}-w^{(i-1)})\sigma(x-x_{i}),$
(59)

where specially $w^{(-1)}=0$. This network is of width $n+1$. Now, we verify
this claim. Given $x\in[x_{j},x_{j+1})$, for some $j\geq 0$, we have the
following:

$\displaystyle f(x_{0})+\sum_{i=0}^{n}(w^{(i)}-w^{(i-1)})\sigma(x-x_{i})$ (60)
$\displaystyle=$ $\displaystyle
f(x_{0})+\sum_{i=0}^{j}(w^{(i)}-w^{(i-1)})(x-x_{i})$ $\displaystyle=$
$\displaystyle
f(x_{0})+w^{(j)}x+\sum_{i=0}^{j-1}w^{(i)}(x_{i+1}-x_{i})-w^{(j)}x_{j}$
$\displaystyle=$ $\displaystyle
f(x_{0})+\sum_{i=0}^{j-1}(f(x_{i+1})-f(x_{i}))+w^{(j)}(x-x_{j})$
$\displaystyle=$ $\displaystyle f(x_{j})+w^{(j)}(x-x_{j}).$

Figure 12: Equivalent wide (a) and deep (b) univariate ReLU networks.

Next, we construct an equivalent deep network dual to the above wide network.
Note that (59) is the same as

$\displaystyle
f(x_{0})+\sum_{i=0}^{n}\mathrm{sgn}(w^{(i)}-w^{(i-1)})\sigma\Big{(}|w^{(i)}-w^{(i-1)}|(x-x_{i})\Big{)},$
(61)

where $\mathrm{sgn}(x<0)=-1$ and $\mathrm{sgn}(x>0)=1$. If we write
$R_{i}(x)=\sigma(|w^{(i)}-w^{(i-1)}|(x-x_{i})),i=0,\cdots,n-1$, then it is
clear that the following recursive relation holds:

$R_{i+1}(x)=\sigma\left(|w^{(i+1)}-w^{(i)}|(\frac{1}{|w^{(i)}-w^{(i-1)}|}R_{i}(x)-x_{i+1}+x_{i})\right).$
(62)

Thanks to the recurrent relation, each $R_{i}$ can accurately represent a
small monotonically increasing piece over $[x_{i},x_{i+1}]$. We aggregate the
outputs of those $n+1$ pieces in the output neuron to get the desired deep
network $\mathbf{H}_{2}(x)$:

$\mathbf{H}_{2}(x)=f(x_{0})+\sum_{i=0}^{n}\mathrm{sgn}(w^{(i)}-w^{(i-1)})R_{i}(x),$
(63)

which is the same as $\mathbf{H}_{1}(x)$. To construct $R_{n}(x)$, $n+1$
consecutive neurons are connected in series. Therefore, such a one-neuron-wide
network has $n+2$ layers. We plot two types of neural networks
$\mathbf{H}_{1}(x)$ and $\mathbf{H}_{2}(x)$ in Figure 12. ∎

###### Proof.

(Theorem 9, $\mathbf{D\geq 2}$) If we write
$V=(\mathbf{v}_{1}-\mathbf{v}_{0},\mathbf{v}_{2}-\mathbf{v}_{0},\cdots,\mathbf{v}_{D}-\mathbf{v}_{0})$,
then $V$ is invertible, and
$S=\left\\{\mathbf{v}_{0}+V\mathbf{x}~{}|~{}\mathbf{x}\in\Delta\right\\}$
where $\Delta=\left\\{\mathbf{x}\in\mathbb{R}^{D}~{}|~{}\mathbf{x}\geq
0,\mathbf{1}^{\top}\mathbf{x}\leq 1\right\\}$ is a template simplex in
$\mathbb{R}^{D}$. It is clear that the following one-to-one affine mapping
between $S$ and $\Delta$ exists, which is

$T:S\rightarrow\Delta,\mathbf{p}\mapsto
T(\mathbf{p})=V^{-1}(\mathbf{p}-\mathbf{v}_{0}).$ (64)

Therefore, we only need to prove the statement on the special case that
$S=\Delta$.

For convenience, we use $\sigma(\cdot)=\max\\{\cdot,0\\}$ to denote the ReLU
function. We denote the domain of a network as $\Omega=[-B,B]^{D}$. Given a
linear function
$\ell(\mathbf{x})=c_{1}x_{1}+c_{2}x_{2}+\cdots+c_{n}x_{n}+c_{n+1}$, we write
$\ell^{-}=\\{\mathbf{x}\in\mathbb{R}^{D}~{}|~{}\ell(\mathbf{x})<0\\}$ and
$\ell^{+}=\\{\mathbf{x}\in\mathbb{R}^{D}~{}|~{}\ell(\mathbf{x})\geq 0\\}$. $S$
is enclosed by $D+1$ hyperplanes provided by
$\ell_{i}(\mathbf{x})=x_{i},i=1,\cdots,D$, and
$\ell_{D+1}(\mathbf{x})=-x_{1}-\cdots-x_{D}+1$. We write $D+1$ vertices of $S$
as
$\mathbf{v}_{0}=(0,0,\cdots,0),\mathbf{v}_{1}=(1,0,\cdots,0),\mathbf{v}_{2}=(0,1,\cdots,0),\cdots,\mathbf{v}_{D+1}=(0,\cdots,0,1)$.
Then $f:[-B,~{}B]^{D}\rightarrow\mathbb{R}$ supported on $S$ is provided as

$f(\mathbf{x})=\Big{\\{}\begin{array}[]{cc}\mathbf{a}^{\top}\mathbf{x}+b,&\textbf{if}\quad\mathbf{x}\in
S\\\ 0,&\ \textbf{if}\quad\mathbf{x}\in S^{c}\end{array},$ (65)

where
$\mathbf{a}=(f(\mathbf{v}_{1})-f(\mathbf{v}_{0}),f(\mathbf{v}_{2})-f(\mathbf{v}_{0}),\cdots,f(\mathbf{v}_{D})-f(\mathbf{v}_{0})),b=f(\mathbf{v}_{0})$.
Our goal is to approximate the given piecewise linear function $f$ using ReLU
networks. We first index the polytopes separated by $D+1$ hyperplanes
$\ell_{i}(\mathbf{x})=0,i=1,\cdots,D+1$ as
$\mathcal{A}^{(\chi_{1},\cdots,\chi_{i},\cdots,\chi_{D+1})}=\ell_{1}^{\chi_{1}}\cap\cdots\cap\ell_{i}^{\chi_{i}}\cap\cdots\cap\ell_{D+1}^{\chi_{D+1}},\chi_{i}\in\\{+,-\\},i=1,\cdots,D+1$.
It is clear to see that $S=\mathcal{A}^{(+,+,\cdots,+)}$. In addition, we use
$\vee$ to denote exclusion of certain component. For instance,
$\mathcal{A}^{(\chi_{1},\vee,\chi_{3},\cdots,\chi_{D+1})}=\ell_{1}^{\chi_{1}}\cap\ell_{3}^{\chi_{3}}\cap\cdots\cap\ell_{D+1}^{\chi_{D+1}}$.
It can be easily verified that

$\mathcal{A}^{(\chi_{1},\vee,\chi_{3},\cdots,\chi_{D+1})}=\mathcal{A}^{(\chi_{1},+,\chi_{3},\cdots,\chi_{D+1})}\cup\mathcal{A}^{(\chi_{1},-,\chi_{3},\cdots,\chi_{D+1})}.$
(66)

Please note that $\mathcal{A}^{(-,-,\cdots,-)}=\emptyset$. Thus, $D+1$
hyperplanes create in total $2^{D+1}-1$ polytopes in the $\Omega$.

Now we recursively define an essential building block, a D-dimensional fan-
shaped ReLU network $F_{D}(\mathbf{x})$:

$\begin{cases}F_{1}(\mathbf{x})=h_{1}(\mathbf{x})\\\
F_{j+1}(\mathbf{x})=\sigma\circ(F_{j}(\mathbf{x})-\mu^{j}\sigma\circ
h_{j+1}(\mathbf{x})),\quad j=1,\cdots,D-1,\end{cases}$ (67)

where the set of linear functions
$\\{h_{k}(\mathbf{x})=\mathbf{p}_{k}^{\top}\mathbf{x}+r_{k}\\}_{k=1}^{D}$ are
provided by $D$ linearly independent vectors $\\{\mathbf{p}_{k}\\}_{k=1}^{D}$,
and $\mu$ is a large positive number ($\mu^{j}$ denotes $\mu$ with the power
to $j$). Note that the network $F_{D}$ is of width $D$ and depth $D$. This
network enjoys the following key characteristics: 1) As
$\mu\rightarrow\infty$, the hyperplane $h_{1}-\mu
h_{2}-\cdots-\mu^{j}h_{j+1}=0$ is approximate to the hyperplane $h_{j+1}=0$ as
the term $\mu^{j}h_{j+1}$ dominates. Thus, the support of $F_{D}(\mathbf{x})$
converges to $h_{1}^{+}\cap h_{2}^{-}\cap\cdots\cap h_{D}^{-}$ which is a
$D$-dimensional fan-shaped function. 2) Let $C$ be the maximum area of
hyperplanes in $[-B,~{}B]^{D}$. Because the real boundary $h_{1}-\mu
h_{2}-\cdots-\mu^{j}h_{j+1}=0$ is almost parallel to the ideal boundary
$h_{j+1}=0$, the measure of the imprecise domain caused by $\mu^{j}$ is at
most $C/\mu^{j}$, where $1/\mu^{j}$ is the approximate distance between the
real and ideal boundaries. In total, the measure of the inaccurate region in
building $F_{D}(\mathbf{x})$ is at most $C\sum_{j=1}^{D-1}1/\mu^{j}\leq
C/(\mu-1)$. 3) The function over $D$-dimensional fan-shaped domain is $h_{1}$,
since $(h_{j})^{+}=0,j\geq 2$ over the $D$-dimensional fan-shaped domain.

Representing $f$ with a wide network: Discontinuity of $f$ in (65) is one of
the major challenges of representing it using a ReLU network. To tackle this
issue, we start from a linear function
$\tilde{f}(\mathbf{x})=\mathbf{a}^{\top}\mathbf{x}+b,\forall\mathbf{x}\in\mathbb{R}^{D}$,
which can be represented by two neurons
$\sigma\circ\tilde{f}-\sigma\circ(-\tilde{f})$. The key idea is to eliminate
$f$ over all $2^{D+1}-2$ polytopes outside $S$ using the $D$-dimensional fan-
shaped functions.

Let us use $\mathcal{A}^{(+,+,+,-,\cdots,-)}$ and
$\mathcal{A}^{(+,+,-,-,\cdots,-)}$ to show how to cancel the function
$\tilde{f}$ over the polytopes outside $S$. According to (66),
$\mathcal{A}^{(+,+,+,-,\cdots,-)}$ and $\mathcal{A}^{(+,+,-,-,\cdots,-)}$
satisfy

$\mathcal{A}^{(+,+,\vee,-,\cdots,-)}=\mathcal{A}^{(+,+,+,-,\cdots,-)}\cup\mathcal{A}^{(+,+,-,-,\cdots,-)},$
(68)

where $\mathcal{A}^{(+,+,\vee,-,\cdots,-)}$ is a $D$-dimensional fan-shaped
domain. Without loss of generality, a number $D+1$ of $D$-dimensional fan-
shaped functions over $\mathcal{A}^{(+,+,\vee,-,\cdots,-)}$ are needed as the
group of linear independent bases to cancel $\tilde{f}$ , where the $k^{th}$
fan-shaped function is constructed as

$\begin{cases}&F_{1}^{(k)}=x_{1}-\eta_{k}x_{k}\\\
&F_{2}^{(k)}=\sigma\circ\big{(}F_{1}^{(k)}-\mu\sigma\circ(-x_{2})\big{)}\\\
&F_{3}^{(k)}=\sigma\circ\big{(}F_{2}^{(k)}-\mu^{2}\sigma\circ(x_{4})\big{)}\\\
&F_{4}^{(k)}=\sigma\circ\big{(}F_{3}^{(k)}-\mu^{3}\sigma\circ(x_{5})\big{)}\\\
&\ \ \ \ \vdots\\\
&F_{D}^{(k)}=\sigma\circ\big{(}F_{D-1}^{(k)}-\mu^{D-1}\sigma\circ(-x_{1}-\cdots-
x_{D}+1)\big{)},\end{cases}$ (69)

where we let $x_{D+1}=1$ for consistency, the negative sign for $x_{2}$ is to
make sure that the fan-shaped region
$\ell_{1}^{+}\cap(-\ell_{2})^{-}\cap\ell_{4}^{-}\cap\cdots\cap\ell_{D+1}^{-}$
of $F_{D}^{(k)}$ is $\mathcal{A}^{(+,+,\vee,-,\cdots,-)}$, $\eta_{1}=0$, and
$\eta_{k}=\eta,k=2,...,D+1$ represents a small shift for $x_{1}=0$ such that
$\mathfrak{m}((x_{1})^{+}\cap(x_{1}-\eta_{k}x_{k})^{-})<C\eta_{k}$. The
constructed function over $\mathcal{A}^{(+,+,\vee,-,\cdots,-)}$ is

$F_{D}^{(k)}=x_{1}-\eta_{k}x_{k},k=1,\cdots,D+1,$ (70)

which is approximately over

$\forall\mathbf{x}\in\mathcal{A}^{(+,+,\vee,-,\cdots,-)}\backslash\Big{(}(x_{1})^{+}\cap(x_{1}-\eta_{k}x_{k})^{-})\Big{)}.$
(71)

Let us find $\omega_{1}^{*},\cdots,\omega_{D+1}^{*}$ by solving

$\begin{bmatrix}1&1&1&\cdots&1\\\ 0&-\eta&0&\cdots&0\\\ 0&0&-\eta&\cdots&0\\\
\vdots&&&\vdots&\\\ 0&0&0&\cdots&-\eta\\\
\end{bmatrix}\begin{bmatrix}\omega_{1}\\\ \omega_{2}\\\ \omega_{3}\\\
\vdots\\\ \omega_{D+1}\end{bmatrix}=-\begin{bmatrix}a_{1}\\\ a_{2}\\\ a_{3}\\\
\vdots\\\ b\end{bmatrix},$ (72)

and then the new function
$F^{(+,+,\vee,-,\cdots,-)}(\mathbf{x})=\sum_{k=1}^{D+1}\omega_{k}^{*}F_{D}^{(k)}(\mathbf{x})$
satisfies that

$\mathfrak{m}\Big{(}\\{\mathbf{x}\in\mathcal{A}^{(+,+,\vee,-,\cdots,-)}|~{}\tilde{f}(\mathbf{x})+F^{(+,+,\vee,-,\cdots,-)}(\mathbf{x})\neq
0\\}\Big{)}\leq C(D\eta+\frac{D+1}{\mu-1}).$ (73)

Similarly, we can construct other functions
$\overbrace{F^{(+,-,\vee,-,\cdots,-)}(\mathbf{x}),F^{(+,\vee,-,-,\cdots,-)}(\mathbf{x}),\cdots}^{~{}2^{D}-2\
\ terms}$ to cancel $\tilde{f}$ over other polytopes. Finally, these
$D$-dimenional fan-shaped functions are aggregated to form the following wide
ReLU network $\mathbf{N}_{1}(\mathbf{x})$:

$\mathbf{N}_{1}(\mathbf{x})=\sigma\circ(\tilde{f}(\mathbf{x}))-\sigma\circ(-\tilde{f}(\mathbf{x}))+\overbrace{F^{(+,+,\vee,-,\cdots,-)}(\mathbf{x})+F^{(+,\vee,-,-,\cdots,-)}(\mathbf{x})+\cdots}^{~{}{2^{D}-1}\
\ terms},$ (74)

where the width and depth of the network are $D(D+1)(2^{D}-1)+2$ and $D+1$
respectively. In addition, because there are $2^{D}-1$ polytopes being
cancelled, the total area of the regions suffering from errors is no more than

$(2^{D}-1)C(D\eta+\frac{D+1}{\mu-1}).$ (75)

Therefore, for any $\delta>0$, as long as we choose appropriate $\mu,\eta$
that fulfill

$0<1/{(\mu-1)},\eta<\frac{\delta}{(2^{D}-1)C(D+D+1)}=\frac{\delta}{(2^{D}-1)C(2D+1)},$
(76)

the constructed wide network $\mathbf{N}_{1}(\mathbf{x})$ will have

$\mathfrak{m}\left(\\{\mathbf{x}\in\mathbb{R}^{D}~{}|~{}f(\mathbf{x})\neq\mathbf{N}_{1}(\mathbf{x})\\}\right)<\delta.$
(77)

Representing $f$ with a deep network: Allowing more layers in a network
provides an alternate way to represent $f$. The fan-shaped functions remain to
be used. The whole pipeline can be divided into two steps: (1) build a
function over $S$; and (2) represent $f$ over $S$ by slightly moving one
boundary of $S$ to create linear independent bases.

(1) We construct a number $D$ of $D$-dimensional fan-shaped functions. Without
loss of generality, the $k^{th}$ fan-shaped function is constructed as

$\begin{cases}&F_{1}^{(k)}=x_{1}-\nu_{k}x_{k}\\\
&F_{2}^{(k)}=\sigma\circ\big{(}F_{1}^{(k)}-\mu^{1}\sigma\circ(-x_{2})\big{)}\\\
&\ \ \ \ \vdots\\\
&F_{D}^{(k)}=\sigma\circ\big{(}F_{D-1}^{(k)}-\mu^{D+1}\sigma\circ(-x_{D})\big{)},\end{cases}$
(78)

whose fan-shaped region is approximately
$(\ell_{1}-\nu_{k}x_{k})^{+}\cap(-\ell_{2})^{-}\cap\cdots\cap(-\ell_{D})^{-}=(\ell_{1}-\nu_{k}x_{k})^{+}\cap\ell_{2}^{+}\cap\cdots\cap\ell_{D}^{+}$,
which almost overlaps with
$\mathcal{A}^{(+,\cdots,+,\vee)}=\ell_{1}^{+}\cap\ell_{2}^{+}\cap\cdots\cap\ell_{D}^{+}$
as $\nu_{k}$ becomes sufficiently small. To obtain the last boundary
$\ell_{D+1}(\mathbf{x})=-x_{1}-\cdots-x_{D}+1=0$ so as to construct the
simplex $S$, we stack one more layer with only one neuron as follows:

$\mathbf{N}_{2}^{1}(\mathbf{x})=(\gamma_{1}^{*}F_{D}^{(1)}+\cdots\gamma_{D}^{*}F_{D}^{(D)}+\gamma_{D+1}^{*})^{+},$
(79)

where $\gamma_{1}^{*},\cdots,\gamma_{D+1}^{*}$ are the roots of the following
equation:

$\begin{cases}(1-\nu_{1})\gamma_{1}+\gamma_{2}+\cdots+\gamma_{D}=-1&\\\
-\nu_{2}\gamma_{2}=-1&\\\ \ \ \ \ \ \vdots&\\\ -\nu_{D}\gamma_{D}=-1&\\\
\gamma_{D+1}=1.\end{cases}$ (80)

Thus, $\mathbf{N}_{2}^{1}(\mathbf{x})$ will approximately represent the linear
function $-x_{1}-\cdots-x_{D}+1$ over $S$ and zero elsewhere. The depth and
width of the network are $D+1$ and $D^{2}$ respectively. Similarly, due to the
employment of a number $D$ of $D$-dimensional fan-shaped functions and the
effect of $\nu_{k}$, the area of the region with errors is estimated as

$CD/{(\mu-1)}+C\sum_{k=1}^{D}\nu_{k}.$ (81)

(2) To acquire an arbitrary linear function, similarly we need $D+1$ linear
independent functions as linear independent bases. Other than the one obtained
in step (1), we further modify $\ell_{D+1}$ a little bit $D$ times to get
$\ell_{D+1}^{l}=\ell_{D+1}-\tau_{l}x_{l},l=1,\cdots,D$. Repeating the same
procedure described in step (1), for $\ell_{D+1}^{l}$, we can construct the
network $\mathbf{N}_{2}^{l}(\mathbf{x})$ that is
$\ell_{D+1}^{l}-\tau_{l}x_{l}$ approximately over
$\ell_{1}^{+}\cap\ell_{2}^{+}\cap\cdots\cap(\ell_{D+1}^{l})^{+}$, where
$\tau_{l},l=1,\cdots,D$ is small to render these domains almost identical to
$S$, and $\tau_{l},l=1,\cdots,D$ satisfies that

$\begin{bmatrix}-1-\tau_{1}&-1&-1&\cdots&-1&-1\\\
-1&-1-\tau_{2}&-1&\cdots&-1&-1\\\ \vdots&&&\vdots&\\\
-1&-1&-1&\cdots&-1-\tau_{D}&-1\\\ 1&1&1&\cdots&1&1\\\
\end{bmatrix}\begin{bmatrix}\rho_{1}^{*}\\\ \rho_{2}^{*}\\\ \vdots\\\
\rho_{D}^{*}\\\ \rho_{D+1}^{*}\end{bmatrix}=\begin{bmatrix}a_{1}\\\ a_{2}\\\
\vdots\\\ a_{D}\\\ b\end{bmatrix},$ (82)

where $\rho_{1}^{*},\cdots,\rho_{D+1}^{*}$ are the roots. As a result, the
deep network is built as

$\mathbf{N}_{2}(\mathbf{x})=\rho_{1}^{*}\mathbf{N}_{2}^{1}(\mathbf{x})+\rho_{2}^{*}\mathbf{N}_{2}^{2}(\mathbf{x})+\cdots+\rho_{D+1}^{*}\mathbf{N}_{2}^{D+1}(\mathbf{x}),$
(83)

producing $f$ on $S$. The depth and width of the network are $D+2$ and
$D^{2}(D+1)$ respectively. Similarly, the area of the region with errors is
bounded above by

$CD(D+1)/{(\mu-1)}+C(D+1)\sum_{k=1}^{D}\nu_{k}+C\sum_{l=1}^{D}\tau_{l}.$ (84)

Therefore, for any $\delta>0$, if we choose $\mu,\nu_{k},\tau_{l}$
appropriately such that

$0<1/{(\mu-1)},\nu_{k},\tau_{l}<\frac{\delta}{C(D(D+1)+(D+1)D+D)}=\frac{\delta}{C(2D^{2}+3D)},$
(85)

then the constructed deep network $\mathbf{N}_{2}(\mathbf{x})$ will satisfy

$\mathfrak{m}\left(\\{\mathbf{x}\in\mathbb{R}^{D}|f(\mathbf{x})\neq\mathbf{N}_{2}(\mathbf{x})\\}\right)<\delta.$
(86)

∎

### Effects of Width on Optimization, Generalization and VC dimension

We first illustrate the importance of width on optimization in the context of
over-paramterization, kernel ridge regression, and NTK, and then report our
findings that the existing generalization bounds and VC dimension results
somehow suggest the width and depth duality for a given complexity of
networks.

1\. Optimization: The optimization mechanism is the key to understand the
training process of neural networks [ge2015escaping]. From the view of
optimization, the fact that randomly-initialized first-order methods can find
well-generalizable minima on the training data is quite intriguing. Given the
theme of this paper, we put our endeavor into the importance of width on the
optimization of neural networks in hope to provide insights for practitioners.
We divide the relevant literature into the three categories:

(1) Increase width for over-parameterization: Brutzkus et al. showed that a
wide two-layer network using the hinge loss can generalize well on linearly
separable data with stochastic gradient descent (SGD) [brutzkus2017sgd]. Li
and Liang showed that when data is normalized and fulfills a separability
condition, a two-layer over-parameterized network can learn these data in a
polynomial time [li2018learning]. Allen-Zhu et al. [allen2019learning] showed
that if the width of hidden layers is
$\mathcal{O}\Big{(}n^{30}D^{30}\log^{30}(1/\epsilon)\Big{)}$, where $n$ is the
number of samples, $D$ is the network depth, and $\epsilon$ is an expected
error, then the gradient descent search converges with the error $\epsilon$.
This bound was further reduced to $n^{4}2^{D}$ for the network using non-
linear smooth activation functions such as soft-plus [du2018gradient2]. These
paper established that a pre-specified small training error can be achieved by
gradient descent when the network is very wide. The secret therein is that the
weight matrix is very close to the initialization due to NTK
[jacot2018neural].

(2) Kernel ridge regression: A neural network tends to give a Gaussian process
when the width goes infinitely large. In this situation, only training the top
layer of a network (weak training) will reduce to Kernel ridge regression. In
a classical way, the weak training is to minimize the quadratic loss:

$C(\mathbf{w})=(\mathbf{y-Xw})^{T}(\mathbf{y-Xw})+\lambda||\mathbf{w}||^{2},$
(87)

where $\mathbf{X}=[\mathbf{x}_{1};...;\mathbf{x}_{n}]$ is a collection of data
$\mathbf{x}_{i}\in\mathbb{R}^{1\times d},i=1,...,n$. Taking derivatives with
respect to $\bm{w}$ and equating them to zero gives

$\mathbf{w}=(\mathbf{X}^{T}\mathbf{X}+\lambda\mathbf{I}_{d})^{-1}\mathbf{X}^{T}\mathbf{y}=\mathbf{X}^{T}(\lambda\mathbf{I}_{n}+\mathbf{X}\mathbf{X}^{T})^{-1}\mathbf{y}.$
(88)

Given a new example $x^{*}$, the prediction is

$y^{*}=x^{*}\mathbf{X}^{T}(\lambda\mathbf{I}_{n}+\mathbf{X}\mathbf{X}^{T})^{-1}\mathbf{y}.$
(89)

We replace the data samples with the high-dimensional representations of the
neural network: $\mathbf{x}\to
g_{\mathbf{\theta}}(\mathbf{x})\in\mathbb{R}^{1\times k}$ and let
$\Phi_{g}(\mathbf{X})=[g_{\mathbf{\theta}}(\mathbf{x}_{1});...;g_{\mathbf{\theta}}(\mathbf{x}_{n})]$.
By a similar derivation, we have

$y^{*}=g_{\theta}(x^{*})\Phi_{g}(\mathbf{X})^{T}(\lambda\mathbf{I}_{n}+\Phi_{g}(\mathbf{X})\Phi_{g}(\mathbf{X})^{T})^{-1}\mathbf{y}$
(90)

When the width is very large, due to the Gaussian process, the weak training
is reasonable, because $\Phi_{g}(\mathbf{X})$ converges to
$\underset{\bm{\theta}\sim\bm{\Theta}}{\mathbb{E}}[\Phi_{g}(\mathbf{X})]$, and
$\Phi_{g}(\mathbf{X})\Phi_{g}(\mathbf{X})^{T}$ converges to
$\underset{\bm{\theta}\sim\bm{\Theta}}{\mathbb{E}}[\Phi_{g}(\mathbf{X})\Phi_{g}(\mathbf{X})^{T}]$,
which can be approximated by the random initialization.

(3) Neural Tangent Kernel: In the above argument, we have justified the
legitimacy of training the top layer by the large network width. How about
training the entire network? Given the dataset
$\\{(\mathbf{x}_{i},y_{i})\\}_{i=1}^{n}$, we also consider training the
network with the quadratic loss for regression:
$l(\bm{\theta})=\frac{1}{2}\sum_{i=1}^{n}(f_{\bm{\theta}}(\mathbf{x}_{i}))-y_{i})^{2}$.
Consider the gradient descent in an infinitesimally small learning rate, then

$\frac{d\bm{\mathbf{\theta}}(t)}{dt}=-\nabla_{\bm{\mathbf{\theta}}}l(\bm{\theta}(t))=-\sum_{i}^{n}(f_{\bm{\theta}(t)}(\mathbf{x}_{i}))-y_{i})\nabla_{\bm{\mathbf{\theta}}}f_{\bm{\theta}(t)}(\mathbf{x}_{i})$
(91)

Then, we can describe the dynamics of the model output $y({\bm{\theta}})$
given the input $\mathbf{x}_{j}$ as follows:

$\displaystyle\frac{df_{{\bm{\theta}}(t)}(\mathbf{x}_{j})}{dt}$
$\displaystyle=\nabla_{\bm{\mathbf{\theta}}}f_{{\bm{\theta}}(t)}(\mathbf{x}_{j})^{T}\frac{d\bm{\mathbf{\theta}}}{dt}$
(92)
$\displaystyle=-\sum_{i}^{n}(f_{\bm{\theta}(t)}(\mathbf{x}_{i}))-y_{i})\Big{\langle}\nabla_{\bm{\mathbf{\theta}}}f_{{\bm{\theta}}(t)}(\mathbf{x}_{j}),\nabla_{\bm{\mathbf{\theta}}}f_{\bm{\theta}(t)}(\mathbf{x}_{i})\Big{\rangle}$

Let us consider $\bm{u}(t)=(f_{\bm{\theta}(t)}(\mathbf{x}_{i}))_{i=1,...,n}$
for all samples at time $t$ and $\bm{y}=(y_{i})_{i=1,...,n}$ is the output,
(92) can be written in a compact way:

$\frac{d\bm{u}(t)}{dt}=-\mathbf{H}(t)\cdot(\bm{u}(t)-\bm{y}),$ (93)

where the $pq$-entry of $\mathbf{H}(t)$ is

$[\mathbf{H}(t)]_{pq}=\Big{\langle}\nabla_{\bm{\mathbf{\theta}}}f_{{\bm{\theta}}(t)}(\mathbf{x}_{p}),\nabla_{\bm{\mathbf{\theta}}}f_{\bm{\theta}(t)}(\mathbf{x}_{q})\Big{\rangle}.$
(94)

In the width limit, the Gaussian process shows that $\mathbf{H}(t)$ becomes a
constant $\mathbf{H}^{*}$. Therefore,

$\frac{d\bm{u}(t)}{dt}=-\mathbf{H}^{*}\cdot(\bm{u}(t)-\bm{y}),$ (95)

which characterizes the trajectory of the training in the functional space
instead of the parameter space.

Table 6: Representative bounds for chain-like neural networks, where $B_{l,2}$, $B_{l,F}$ and $B_{l,2\to 1}$ to denote the upper bounds of the spectral norm $||\mathbf{W}_{d}||_{2}$, Frobenius norm $||\mathbf{W}_{d}||_{F}$ and $||\mathbf{W}_{d}||_{2,1}$ of the rank-$r$ matrix in $l^{th}$ layer. Generally, $||\mathbf{W}_{d}||_{F}$ and $||\mathbf{W}_{d}||_{2,1}$ is $\sqrt{r}$-times larger than $||\mathbf{W}_{d}||_{2}$, $\gamma$ means the ramp loss function is $1/\gamma$-Lipschitz function, $\Gamma$ is the lower bound for the product of the spectal norm of all the layers and the $m$ is the size of data.  Reference |  Bound |  $||\mathbf{W}_{d}||_{2}=1$
---|---|---
[neyshabur2015norm] |  $\mathcal{O}\Big{(}\frac{2^{L}\cdot\prod_{l=1}^{L}B_{l,F}}{\gamma\sqrt{m}}\Big{)}$ |  $\mathcal{O}\Big{(}\frac{2^{L}\cdot r^{L/2}}{\gamma\sqrt{m}}\Big{)}$
[bartlett2017spectrally] |  $\mathcal{O}\Big{(}\frac{\prod_{l=1}^{L}B_{l,F}\cdot\log(Lp)}{\gamma\sqrt{m}}\big{(}\sum_{l=1}^{L}\frac{B_{l,2\to 1}^{2/3}}{B_{l,2}^{2/3}}\big{)}^{3/2}\Big{)}$ |  $\mathcal{O}\Big{(}\frac{\log(p)\sqrt{L^{3}r}}{\gamma\sqrt{m}}\Big{)}$
[neyshabur2017pac] |  $\mathcal{O}\Big{(}\frac{\prod_{l=1}^{L}B_{l,F}\cdot\log(Lp)}{\gamma\sqrt{m}}\big{(}L^{2}p\sum_{l=1}^{L}\frac{B_{l,F}^{2}}{B_{l,2}^{2}}\big{)}^{1/2}\Big{)}$ |  $\mathcal{O}\Big{(}\frac{\log(Lp)\sqrt{L^{3}pr}}{\gamma\sqrt{m}}\Big{)}$
[golowich2017size] |  $\mathcal{O}\Big{(}\frac{\prod_{l=1}^{L}B_{l,F}}{\gamma}\cdot\min\\{\sqrt{\frac{\log{\frac{1}{\Gamma}}\prod_{l=1}^{L}B_{l,F}}{m^{1/2}}},\sqrt{\frac{D}{m}}\\}\Big{)}$ |  $\mathcal{O}\Big{(}\frac{\sqrt{Lpr}}{\gamma\sqrt{m}}\Big{)}$

2\. Generalization: Analysis of generalization bounds is a powerful tool to
explain the excellent performance of neural networks. Traditional wisdom
suggests that the increased model complexity will cause over-fitting to
training data, which contradicts the fact that deep networks can easily fit
random labels to the data and yet practically generalize well
[zhang2016understanding]. Recently, the generalization theory has gained
increasingly more traction. In reference to Xingguo Li et al. [li2018tighter],
we have summarized the the state-of-the-art generalization bounds in Table 3
and provided their complexities. In Table 6, we bold-face the bounds of
interest which the width and depth dominate. As far as [neyshabur2015norm] is
concerned, due to the exponential dependence on the depth, we will not focus
on it. Instead, we argue that these bold-faced bounds somehow suggest the
width and depth duality under a given complexity. Now, we use
$B_{1}(L,p)=\log(p)\sqrt{L^{3}}$, $B_{2}(L,p)=\log(Lp)\sqrt{L^{3}p}$ and
$B_{3}(L,p)=\sqrt{Lp}$ to denote the bounds of interest. Figure 13 shows the
contours plots of $B_{1}$, $B_{2}$ and $B_{3}$. Along a contour, the width and
depth changes for the fixed bound complexity. In other words, the depth and
width of a neural network are mutually transformable without impacting the
overall generalization ability theoretically.

Figure 13: Contours of $B_{1}$, $B_{2}$ and $B_{3}$, where numbers on the
curves of each sub-figure represent $\log(p)\sqrt{L^{3}}$,
$\log(p)\sqrt{L^{3}}$ and $\sqrt{Lp}$ respectively. Along a contour, the width
and depth changes to give the same bound.

3\. VC Dimension: The duality of depth and width of a network can be
appreciated in reference to VC dimension [b36]. VC dimension is a measure on
the capacity of a hypothesis space that can be learned by a neural network and
other statistical learning models. The definition of VC dimension is based on
the cardinality of the largest set of points that can be "shattered" by a
model. Since VC dimension is originally geared towards binary classification,
let us give the definition of VC dimension in the context of binary
classification.

Given the hypothesis space $\mathcal{H}$ and the data collection
$D=\\{\textbf{x}_{1},\textbf{x}_{2},\cdots,\textbf{x}_{m}\\}$, every
$h\in\mathcal{H}$ labels the instances in $D$, we denote the resultant
labeling as

$h_{|D}=\\{(h(\textbf{x}_{1}),h(\textbf{x}_{2}),\cdot,h(\textbf{x}_{m}))\\},$
(96)

It is seen that, for $m$ instances, the maximum number of possible labeling
schemes is $2^{m}$. If the hypothesis space $\mathcal{H}$ can realize all the
possible labeling schemes on $D$, we say that $D$ can be shattered by
$\mathcal{H}$. VC dimension of $\mathcal{H}$ is the cardinality of the dataset
comprising the maximum number of instances that can be shattered.

The bound of VC dimension of a neural network has been extensively studied in
the past decades. For example, let $W$ be the number of weights and $L$ be the
number of layers, Goldberg and Jerrum [b37] established the upper bound of VC
dimension $\mathcal{O}(W^{2})$ for a network with piecewise polynomial
activation. Furthermore, Bartlett et al. [b38] found that an upper VC
dimension bound is $\mathcal{O}(WL^{2}+WLlog(WL))$ and a lower bound is
$\mathcal{O}(WL)$. Recently, Bartlett et al. [b39] derived a nearly tight VC
dimension bound for ReLU networks:

$c\cdot WLlog(W/L)\leq VCdim(W,L)\leq C\cdot WLlog(W),$ (97)

where $c$ and $C$ are constants.

(97) implies that the above upper and lower bounds for VC dimension of a
neural network are determined by the number of parameters and the number of
layers. As a semi-quantitative estimate, let all the layers have the same
number of neurons, then we have

$\displaystyle VCdim(Width,Depth)\geq c\cdot Width\cdot Depth\cdot log(Width)$
(98) $\displaystyle VCdim(Width,Depth)\leq C\cdot Width\cdot Depth\cdot
log(Width)$

Therefore, increasing either width or depth can boost the hypothesis space of
a neural network. In other words, when it comes to promoting the expressive
power of a network, increasing the width is essentially equivalent to
increasing the depth in the sense of VC dimension, which also implies the
duality of the width and depth of neural networks.