# Rethink Depth Separation with Intra-layer Links

Feng-Lei Fan∗
Department of Mathematics
The Chinese University of Hong Kong
<EMAIL_ADDRESS>
&Ze-Yu Li∗
Department of Mathematics
The Chinese University of Hong Kong
<EMAIL_ADDRESS>
Huan Xiong∗
Institute for Advanced Study in Mathematics
Harbin Institute of Technology
<EMAIL_ADDRESS>
&&&&Tieyong Zeng
Department of Mathematics
The Chinese University of Hong Kong
<EMAIL_ADDRESS>
All authors have an equal contribution, and authors’ names are listed
alphabetically.

###### Abstract

The depth separation theory is nowadays widely accepted as an effective
explanation for the power of depth, which consists of two parts: i) there
exists a function representable by a deep network; ii) such a function cannot
be represented by a shallow network whose width is lower than a threshold.
However, this theory is established for feedforward networks. Few studies, if
not none, considered the depth separation theory in the context of shortcuts
which are the most common network types in solving real-world problems. Here,
we find that adding intra-layer links can modify the depth separation theory.
First, we report that adding intra-layer links can greatly improve a network’s
representation capability through bound estimation, explicit construction, and
functional space analysis. Then, we modify the depth separation theory by
showing that a shallow network with intra-layer links does not need to go as
wide as before to express some hard functions constructed by a deep network.
Such functions include the renowned "sawtooth" functions. Moreover, the saving
of width is up to linear. Our results supplement the existing depth separation
theory by examining its limit in the shortcut domain. Also, the mechanism we
identify can be translated into analyzing the expressivity of popular shortcut
networks such as ResNet and DenseNet, e.g., residual connections empower a
network to represent a sawtooth function efficiently.

##  1 Introduction

Due to the widespread applications of deep networks in many important fields
(LeCun et al., 2015), mathematically understanding the power of deep networks
has been a central problem in deep learning theory (Poggio et al., 2020). The
key issue is figuring out how expressive a deep network is or how increasing
depth promotes the expressivity of a neural network better than increasing
width. In this regard, there have been a plethora of studies on the
expressivity of deep networks, which are collectively referred to as the depth
separation theory Safran et al. (2019); Vardi and Shamir (2020); Gühring et
al. (2020); Vardi et al. (2021); Safran and Lee (2022); Venturi et al. (2022).

A popular idea to demonstrate the expressivity of depth is the complexity
characterization that introduces appropriate complexity measures for functions
represented by neural networks (Pascanu et al., 2013; Montufar et al., 2014;
Telgarsky, 2015; Montúfar, 2017; Serra et al., 2018; Hu and Zhang, 2018; Xiong
et al., 2020; Bianchini and Scarselli, 2014; Raghu et al., 2017; Sanford and
Chatziafratis, 2022; Joshi et al., 2023), and then reports that increasing
depth can greatly boost such a complexity measure. In contrast, a more
concrete way to show the power of depth is to construct functions that can be
expressed by a narrow network of a given depth, but cannot be approximated by
shallower networks, unless its width is sufficiently large (Telgarsky, 2015,
2016; Arora et al., 2016; Eldan and Shamir, 2016; Safran and Shamir, 2017;
Venturi et al., 2021). For example,Eldan and Shamir (2016) constructed a
radial function and used Fourier spectrum analysis to show that a two-hidden-
layer network can represent it with a polynomial number of neurons, but a one-
hidden-layer network needs an exponential number of neurons to achieve the
same level of error. Telgarsky (2015) employed a ReLU network to build a one-
dimensional "sawtooth" function whose number of pieces scales exponentially
over the depth. As such, a deep network can construct a sawtooth function with
many pieces, while a shallow network cannot unless it is very wide. Arora et
al. (2016) derived the upper bound of the maximal number of pieces for a
univariate ReLU network, and used this bound to elaborate the separation
between a deep and a shallow network. In a broad sense, we summarize the
elements of establishing a depth separation theorem as the following: i) there
exists a function representable by a deep network; ii) such a function cannot
be represented by a shallow network whose width is lower than a threshold. The
depth separation theory is nowadays widely accepted as an effective
explanation for the power of depth.

Figure 1: (a) feedforward, (b) residual, and (c) intra-linked (2-neuron
linked). $x$ is a univariate input. In analogy to horizontal residual
connections in ResNet, we take the intra-layer links as vertical residual
connections. Inserting intra-layer links is essentially different from
stacking layers in terms of the mechanism of generating new pieces, the number
of (affine transform, activation) being used, and the functional class.

In the current deep learning research, the dominating network architectures
are often not feedforward but intensively use shortcuts. However, the existing
depth separation theory is established for feedforward networks. Few studies,
if not none, considered the depth separation theory in the shortcut paradigm.
Due to the pervasiveness of shortcuts, examining the depth separation in the
context of shortcuts is critical. Here we are motivated by ResNet, which are
outer links embedded into a network horizontally (Figure 1(b)). The shallow
network with residual connections can have comparable performance with a deep
network, i.e., the insertion of residual connections can save depth. Per
structural symmetry, we embed shortcuts vertically, i.e., intra-linking
neurons within a layer (Figure 1(c)) to force a neuron to take the outputs of
its neighboring neuron. From the perspective of the crossing number Telgarsky
(2016), the non-symmetric structure of intra-layer linked networks can produce
more oscillations than networks without intra-layer links. Thus, intra-layer
links can save width, i.e., without the need to go as wide as before, a
shallow network can express as a complicated function as a deep network could,
which means that the depth separation theory is modified.

Specifically, our roadmap to the modification of depth separation theorems
includes two milestones. 1) Through bound analysis, explicit construction, and
functional space analysis, we substantiate that a network with intra-layer
links can produce much more pieces than a feedforward network, and the gain is
at most exponential, i.e., $(\frac{3}{2})^{k}$, where $k$ is the number of
hidden layers. 2) Since intra-layer links can yield more pieces, they can
modify depth separation theorems by empowering a shallow network to represent
a function constructed by a deep network, even if the width of this shallow
network is lower than the prescribed threshold. The modification is done in
the cases of $k^{2}$ vs 3 (Theorem 4.18), $k^{2}$ vs $k$ (Theorem 4.19, the
famous sawtooth function (Telgarsky, 2015)), and Theorem 4.17. The saving of
width is up to linear.

Although the focus of our draft is the depth separation theory, our result is
also valuable in the following two aspects: First, the identified mechanism of
generating more pieces can be translated into other shortcut networks such as
ResNet and DenseNet, e.g., residual connections can represent a sawtooth
function efficiently. Second, exploring new and powerful network architectures
has been the mainstream research direction in deep learning in the past
decade. To the best of our knowledge, we are the first to consider adding
shortcuts within a layer in a fully-connected network. Our analysis
theoretically suggests that an intra-linked network is more powerful than a
feedforward network. Like the residual connections, we spotlight that the
improvement of representation power by intra-layer links favorably increases
no trainable parameters for a network.

To summarize, our contributions are threefold. 1) We point out the limitation
of the depth separation theory and propose to consider inserting intra-layer
links in shallow networks. 2) We show via bound estimation, explicit
construction, and functional space analysis that intra-layer links can make a
ReLU network produce more pieces. 3) We modify the depth separation result
including the famous Telgarsky (2015)’s theorem by demonstrating that a
shallow network with intra-layer links does not need to go as wide as before
to represent a function constructed by a deep network.

##  2 Related works

A plethora of depth separation studies have shown the superiority of deep
networks over shallow ones from perspectives of complexity analysis and
constructive analysis.

The complexity analysis is to characterize the complexity of the function
represented by a neural network, thereby demonstrating that increasing depth
can greatly maximize such a complexity measure. Currently, one of the most
popular complexity measures is the number of linear regions because it
conforms to the functional structure of the widely-used ReLU networks. For
example, Pascanu et al. (2013); Montufar et al. (2014); Montúfar (2017); Serra
et al. (2018); Hu and Zhang (2018); Hanin and Rolnick (2019) estimated the
bound of the number of linear regions generated by a fully-connected ReLU
network by applying Zaslavsky’s Theorem (Zaslavsky, 1997). Xiong et al. (2020)
offered the first upper and lower bounds of the number of linear regions for
convolutional networks. Other complexity measures include classification
capabilities (Malach and Shalev-Shwartz, 2019), Betti numbers (Bianchini and
Scarselli, 2014), trajectory lengths (Raghu et al., 2017), global curvature
(Poole et al., 2016), and topological entropy (Bu et al., 2020). Please note
that using complexity measures to justify the power of depth demands a tight
bound estimation. Otherwise, it is insufficient to say that shallow networks
cannot be as powerful as deep networks, since deep networks cannot reach the
upper bound.

The construction analysis is to find a family of functions that are hard to
approximate by a shallow network, but can be efficiently approximated by a
deep network. Eldan and Shamir (2016) built a special radial function that is
expressible by a 3-layer neural network with a polynomial number of neurons,
but a 2-layer network can do the same level approximation only with an
exponential number of neurons. Later, Safran and Shamir (2017) extended this
result to a ball function, which is a more natural separation result. Venturi
et al. (2021) generalized the construction of this type to a non-radial
function. Telgarsky (2015, 2016) used an $\mathcal{O}(k^{2})$-layer network to
construct a sawtooth function. Given that such a function has an exponential
number of pieces, it cannot be expressed by an $\mathcal{O}(k)$-layer network,
unless the width is $\mathcal{O}(\exp(k))$. Arora et al. (2016) estimated the
maximal number of pieces a network can produce, and established the size-piece
relation to advance the depth separation results from ($k^{2}$, $k$) to ($k$,
$k^{\prime}$), where $k^{\prime}<k$. Other smart constructions include
polynomials (Rolnick and Tegmark, 2017), functions of a compositional
structure (Poggio et al., 2017), Gaussian mixture models (Jalali et al.,
2019), and so on. Our work also includes the construction, and we use an
intra-linked network to efficiently build a sawtooth function.

##  3 Notation and Definition

Notation 1 (Feedforward networks). For an
$\mathbb{R}^{w_{0}}\rightarrow\mathbb{R}$ ReLU DNN with widths
$w_{1},\ldots,w_{k}$ of $k$ hidden layers, we use
$\mathbf{f}_{0}=\left[f_{0}^{(1)},\ldots,f_{0}^{\left(w_{0}\right)}\right]=\mathbf{x}\in\mathbb{R}^{w_{0}}$
to denote the input of the network. Let
$\mathbf{f}_{i}=\left[f_{i}^{(1)},\ldots,f_{i}^{\left(w_{i}\right)}\right]\in\mathbb{R}^{w_{i}},i=1,\cdots,k,$
be the vector composed of outputs of all neurons in the $i$-th layer. The pre-
activation of the $j$-th neuron in the $i$-th layer and the corresponding
neuron are given by

$g_{i}^{(j)}=\left\langle\mathbf{a}_{i}^{(j)},\mathbf{f}_{i-1}\right\rangle+b_{i}^{(j)}\quad\text{and}\quad
f_{i}^{(j)}=\sigma\left(g_{i}^{(j)}\right),$

respectively, where $\sigma(\cdot)$ is the ReLU activation and
$\mathbf{a}_{i}^{(j)}\in\mathbb{R}^{w_{i-1}},b_{i}^{(j)}\in\mathbb{R}$ are
parameters. The output of this network is
$g_{k+1}=\left\langle\mathbf{a}_{k},\mathbf{f}_{k}\right\rangle+b_{k}$ for
some $\mathbf{a}_{k}\in\mathbb{R}^{w_{k}}$, $b_{k}\in\mathbb{R}$.

Notation 2 (Intra-linked networks) For an
$\mathbb{R}^{w_{0}}\rightarrow\mathbb{R}$ ReLU DNN with widths
$w_{1},\ldots,w_{k}$ of $k$ hidden layers, we now assume that every $n_{i}$
neurons are intra-linked in the $i$-th layer, where $n_{i}$ can divide $w_{i}$
without remainder. Similar to the classical ReLU DNN, we use
$\tilde{\mathbf{f}}_{0}=\mathbf{x}\in\mathbb{R}^{w_{0}}$ and
$\tilde{\mathbf{f}}_{i}=\left[\tilde{\mathbf{f}}_{i}^{(1)},\ldots,\tilde{\mathbf{f}}_{i}^{\left(w_{i}\right)}\right]\in\mathbb{R}^{w_{i}}$
to denote the input and the vectorized outputs of the $i$-th layer. The $j$-th
pre-activation in the $i$-th layer and the output of the network are computed
in the same way as classical feedforward networks. In an intra-linked network,
the $j$ -th, $\ldots$, $(j+n_{i}-1)$-th neurons in the $i$-th layer are
linked, and the $(j+n_{i})$-th, $\cdots$, $(j+2n_{i}-1)$-th neurons in the
$i$-th layer are linked. We prescribe

$\tilde{f}_{i}^{(j)}=\sigma\left(g_{i}^{(j)}\right),\quad\tilde{f}_{i}^{(j+l)}=\sigma\left(g_{i}^{(j+l)}-\tilde{f}_{i}^{(j+l-1)}\right),$

for $l=1,\ldots,n_{i}-1$. Especially, we are interested in the case every 2
neurons are linked in each layer (i.e., $n_{i}=2$) and the case all neurons in
a layer are linked (i.e., $n_{i}=w_{i}$) in this work.

Notation 3 (sawtooth functions and breakpoints) we say a piecewise linear
(PWL) function $g:[a,b]\to\mathbb{R}$ is of "$N$-sawtooth" shape, if
$g(x)=(-1)^{n-1}\left(x-(n-1)\cdot\frac{b-a}{N}\right),$ for
$x\in\left[(n-1)\cdot\frac{b-a}{N},n\cdot\frac{b-a}{N}\right],n\in[N]$. We say
$x_{0}\in\mathbb{R}$ is a breakpoint of a PWL function $g$, if the left hand
and right hand derivative of $g$ at $x_{0}$ are not equal, i.e.,
$g^{\prime}_{+}(x)\neq g^{\prime}_{-}(x)$.

Please note that stacking a layer is essentially different from inserting
intra-layer links in terms of the fundamental mechanism of generating new
pieces, the number of affine transforms being used, and the functional class.

Figure 2: Adding intra-layer links is not equivalent to increasing depth in
terms of the mechanism of generating more pieces, the number of (affine
transform, activation), and function classes.

$\bullet$ As Figure 2 shows, their mechanisms of producing pieces are
fundamentally different. While the mechanism of adding a new layer is the
repetition effect (multiplication), i.e., the function value of the function
being composed is oscillating, and each oscillation can generate more pieces,
which falls into the depth paradigm. The mechanism of intra-layer links is the
gating effect (addition). The neuron being embedded have two activation
states, and each state is leveraged to produce a breakpoint. Two states are
integrated to generate more pieces. Such a mechanism essentially conforms to
the parallelism, which is of width paradigm.

$\bullet$ Adding intra-layer links does not increase the number of affine
transforms and activations. As Figure 2 illustrates, a feedforward network
with two layers involves two times of affine transformation (activation). In
contrast, adding intra-layer links in a fully-connected layer actually exerts
a gating effect. When $\sigma(W_{2}x+b_{2})>0$, the output is
$\sigma((W_{1}+W_{2})x+b_{1}+b_{2})$; when $\sigma(W_{2}x+b_{2})=0$, the
output is $\sigma(W_{1}x+b_{1})$. The number of (affine transform, activation)
is still one for both cases.

$\bullet$ The function classes represented by our intra-linked network and the
deeper feedforward network are not the same, either, and this will make a big
difference. Given the same width, the deeper feedforward network has a larger
function class than a shallow intra-linked network. However, given the same
width and depth, our intra-linked network has more expressive power (i.e.,
number of pieces, VC dimension) than a feedforward network.

Since inserting intra-layer links is different from stacking new layers, we
define the width and depth of intra-linked networks to be the same as the
width and depth of feedforward networks resulting from removing intra-layer
links.

######  Definition 3.1 (Width and depth of feedforward networks (Arora et al.,
2016)).

For any number of hidden layers $k\in\mathbb{N}$, input and output dimensions
$w_{0},w_{k+1}\in\mathbb{N}$, an
$\mathbb{R}^{w_{0}}\rightarrow\mathbb{R}^{w_{k+1}}$ feedforward network is
given by specifying a sequence of $k$ natural numbers
$w_{1},w_{2},\ldots,w_{k}$ representing widths of the hidden layers. The depth
of the network is defined as $k+1$, which is the number of (affine transform,
activation). The width of the network is
$\max\left\\{w_{1},\ldots,w_{k}\right\\}$.

######  Definition 3.2 (Width and depth of intra-linked networks (Fan et al.,
2020)).

Given an intra-linked network $\mathbf{\Pi}$, we delete the intra-layer links
to make the resultant network $\mathbf{\Pi}^{\prime}$ a feedforward network.
Then, we define the width and depth of $\mathbf{\Pi}$ to be the same as the
width and depth of $\mathbf{\Pi}^{\prime}$.

##  4 Rethink the Depth Separation with Intra-layer Links

Since our focus is the network using ReLU activation and related estimation of
the number of pieces, the seminal depth separation theorems closest to us are
the following:

######  Theorem 4.1 (Depth separation $k^{2}$ vs $k$ (Telgarsky, 2015, 2016)).

For a natural number $k\geq 1$, there exists a sawtooth function representable
by an $\mathbb{R}\rightarrow\mathbb{R}$ $(2k^{2}+1)$-layer feedforward ReLU
DNN of width $2$ such that if it is also representable by a $(k+1)$-layer
feedforward ReLU DNN, this $(k+1)$-layer feedforward ReLU DNN should at least
have the width of $2^{k}-1$.

######  Theorem 4.2 (Depth separation $k$ vs $k^{\prime}$ (Arora et al.,
2016)).

For every pair of natural numbers $k\geq 1,w\geq 2$, there exists a function
representable by an $\mathbb{R}\rightarrow\mathbb{R}$ $(k+1)$-layer
feedforward ReLU DNN of width $w$ such that if it is also representable by a
$\left(k^{\prime}+1\right)$-layer feedforward ReLU DNN for any $k^{\prime}\leq
k$, this $\left(k^{\prime}+1\right)$-layer feedforward ReLU DNN has width at
least $\frac{1}{2}w^{\frac{k}{k^{\prime}}}$.

Despite being one-dimensional, the above results convincingly reveal that
increasing depth can make a ReLU network express a much more complicated
function, which is the heart of depth separation. Here, we shed new light on
the depth separation problem with intra-layer links. Our primary argument is
that if intra-layer links shown in Figure 1(c) are inserted, there exist
shallow networks that previously cannot express some hard functions
constructed by deep networks now can do the job. Our investigation consists of
two parts. First, we substantiate that adding intra-layer links can greatly
increase the number of pieces via bound estimation, explicit construction, and
functional space analysis. Then, adding intra-layer links can represent
complicated functions such as sawtooth functions, without the need of going as
wide as before.

###  4.1 Intra-Layer Links Can Increase the Number of Pieces

####  4.1.1 Upper Bound Estimation

######  Lemma 4.3.

Let $g:\mathbb{R}\rightarrow\mathbb{R}$ be a PWL function with $w+1$ pieces,
then the breakpoints of $f:=\sigma(g)$ consist of two parts: some old
breakpoints of $g$ and at most $w+1$ newly produced breakpoints. Furthermore,
$f$ has $w+1$ new breakpoints if and only if $g$ has $w+1$ distinct zero
points.

###### Proof.

A direct calculus. ∎

######  Theorem 4.4 (Upper bound of feedforward networks).

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a PWL function represented by an
$\mathbb{R}\rightarrow\mathbb{R}$ ReLU DNN with depth $k+1$ and widths
$w_{1},\ldots,w_{k}$ of $k$ hidden layers. Then $f$ has at most
$\prod_{i=1}^{k}\left(w_{i}+1\right)$ pieces.

This bound is the univariate case of the bound:
$\prod_{i=1}^{k}\sum_{j=0}^{n}\binom{w_{i}}{j}$, derived in Montúfar (2017)
for $n$-dimensional inputs. In Appendix B, we offer constructions to show that
this bound is achievable in a depth-bounded but width-unbounded network
(depth=3) (Proposition B.1) and a width-bounded (width=3) but depth-unbounded
network (Proposition B.2) in one-dimensional space. Previously many bounds
Pascanu et al. (2013); Montufar et al. (2014); Montúfar (2017); Xiong et al.
(2020) on linear regions were derived, however, it is unknown whether these
bounds are vacuous or tight, particularly for networks with more than one
hidden layer. What makes Propositions B.1 and B.2 special is that they for the
first time substantiate that Montúfar (2017)’s bound is tight over three-layer
and deeper networks, although these results are for the one-dimensional case.

Remark 1. (Sharpening the bound in (Arora et al., 2016)). Previously, Arora et
al. (2016) computed the number of pieces produced by a network of depth $k+1$
and widths $w_{1},\ldots,w_{k}$ as $2^{k+1}\cdot(w_{1}+1)w_{2}\cdots w_{k}$.
The reason why their bound has an exponential term is that when considering
how ReLU activation increases the number of pieces, they repetitively computed
the old breakpoints generated in the previous layer. Our Lemma 4.3 implies
that the ReLU activation in fact cannot double the number of pieces of a PWL
function. Therefore, the depth separation theorem of Arora et al. (2016) needs
to be re-examined.

######  Lemma 4.5.

Let $g_{1},g_{2}:\mathbb{R}\rightarrow\mathbb{R}$ be two PWL functions with
totally $w$ breakpoints. Set $f_{1}:=\sigma\left(g_{1}\right)$ and
$f_{2}:=\sigma\left(g_{2}-f_{1}\right)$. Then the breakpoints of $f_{2}$
consist of three parts: some breakpoints of $g_{2}$, some breakpoints of
$f_{1}$, and at most $2w+2$ newly produced breakpoints. Furthermore, $f_{2}$
has $2w+2$ newly produced breakpoints if and only if $g_{2}-f_{1}$ has $2w+2$
distinct zero points.

###### Proof.

A direct corollary of Lemma 4.3. ∎

Let us illustrate why the intra-linked architecture can produce more pieces.
Given two PWL functions $g_{1}$ and $g_{2}$ which has totally $w$ breakpoints,
in the feedforward architecture, $\sigma\left(g_{1}\right)$ and
$\sigma\left(g_{2}\right)$ have totally at most $3w+2$ breakpoints, which
contains at most $w$ old breakpoints of $g_{1},g_{2}$ and at most $2w+2$ newly
produced breakpoints. However, in the intra-linked architecture,
$\sigma\left(g_{2}-\sigma\left(g_{1}\right)\right)$ can produce more
breakpoints because $\sigma(g_{1})$ has two states: activated or deactivated.
Then, $\sigma(g_{1})$ and $\sigma\left(g_{2}-\sigma\left(g_{1}\right)\right)$
consist of at most $w$ old breakpoints of $g_{1},g_{2}$ and
$(w+1)+(2w+2)=3w+3$ newly produced breakpoints.

######  Theorem 4.6 (Upper bound of 2-neuron intra-linked networks).

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a PWL function represented by a
ReLU DNN with depth $k+1$, widths $w_{1},\ldots,w_{k}$, and every two neurons
linked in each hidden layer as Figure 1(c). Assuming that $w_{1},\ldots,w_{k}$
are even, $f$ has at most $\prod_{i=1}^{k}\left(\frac{3}{2}w_{i}+1\right)$
pieces.

###### Proof.

We prove by induction on $k$. For the base case $k=1$, we assume for every odd
$j$, the neurons $\tilde{f}_{1}^{(j)}$ and $\tilde{f}_{2}^{(j+1)}$ are linked.
The number of breakpoints of $\tilde{f}_{1}^{(j)}$, $j=1,\ldots,w_{1}$, is at
most $2+(-1)^{j}$. Hence, the first layer yields at most $\frac{3}{2}w_{1}+1$
pieces. For the induction step, we assume that for some $k\geq 1$, any
$\mathbb{R}\rightarrow\mathbb{R}$ ReLU DNN with every two neurons linked in
each hidden layer, depth $k+1$ and widths $w_{1},\ldots,w_{k}$ of $k$ hidden
layers produces at most $\prod_{i=1}^{k}\left(\frac{3}{2}w_{i}+1\right)$
pieces. Now we consider any $\mathbb{R}\rightarrow\mathbb{R}$ ReLU DNN with
every two neurons linked in each hidden layer, depth $k+2$ and widths
$w_{1},\ldots,w_{k+1}$ of $k+1$ hidden layers. By the induction hypothesis,
each $\tilde{g}_{k+1}^{(j)}$ has at most
$\prod_{i=1}^{k}\left(\frac{3}{2}w_{i}+1\right)-1$ breakpoints. Then the
breakpoints of $\sigma(\tilde{g}_{k+1}^{(j)})$ consist of some breakpoints of
$\tilde{g}_{k+1}^{(j)}$ and at most
$\prod_{i=1}^{k}\left(\frac{3}{2}w_{i}+1\right)$ newly generated breakpoints.
Then $\tilde{g}_{k+1}^{(j+1)}-\tilde{f}_{k+1}^{(j)}$ has at most
$2\cdot\prod_{i=1}^{k}\left(\frac{3}{2}w_{i}+1\right)-1$ breakpoints, based on
Lemma 4.5. The breakpoints of
$\tilde{f}_{k+1}^{(j+1)}=\sigma(\tilde{g}_{k+1}^{(j+1)}-\tilde{f}_{k+1}^{(j)})$
consist of some breakpoints of $\tilde{g}_{k+1}^{(j+1)}-\tilde{f}_{k+1}^{(j)}$
and at most $2\cdot\prod_{i=1}^{k}\left(\frac{3}{2}w_{i}+1\right)$ newly
generated breakpoints. Note that
$\tilde{g}_{k+1}^{(1)},\ldots,\tilde{g}_{k+1}^{(w_{k+1})}$ have totally at
most $\prod_{i=1}^{k}\left(\frac{3}{2}w_{i}+1\right)-1$ breakpoints. In all,
the number of pieces we can therefore get is at most
$1+\frac{w_{k+1}}{2}\cdot\left(\prod_{i=1}^{k}\left(\frac{3}{2}w_{i}+1\right)+2\cdot\prod_{i=1}^{k}\left(\frac{3}{2}w_{i}+1\right)\right)+\prod_{i=1}^{k}\left(\frac{3}{2}w_{i}+1\right)-1=\prod_{i=1}^{k+1}\left(\frac{3}{2}w_{i}+1\right).$
∎

In the following theorems, we offer the bound estimation for high-dimensional
cases. The detailed proof for Theorem 4.8 is put into Appendix A.

######  Theorem 4.7 (Upper Bound of Feedforward Networks (Montúfar, 2017)).

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a PWL function represented by
an $\mathbb{R}^{n}\rightarrow\mathbb{R}$ ReLU DNN with depth $k+1$ and widths
$w_{1},\ldots,w_{k}$ of $k$ hidden layers. Then $f$ has at most
$\prod_{i=1}^{k}\sum_{j=0}^{n}\binom{w_{i}}{j}$ linear regions.

######  Theorem 4.8 (Upper Bound of Intra-linked Networks).

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a PWL function represented by
an $\mathbb{R}^{n}\rightarrow\mathbb{R}$ ReLU DNN with every two neurons
linked in each hidden layer, depth $k+1$ and widths $w_{1},\ldots,w_{k}$ of
$k$ hidden layers. We assume each $w_{i}$ is even. Then $f$ has at most
$\prod_{i=1}^{k}\sum_{j=0}^{n}\binom{\frac{3w_{i}}{2}+1}{j}$ linear regions.

####  4.1.2 Explicit Construction.

Despite that the bound estimation offers some light, to convincingly
illustrate that intra-layer links can increase the number of pieces, we need
to supply the explicit construction for the intra-linked networks. The number
of pieces in the construction should be bigger than either the upper bound of
feedforward networks or the maximal number a feedforward network can achieve.
Specifically, the constructions for 2-neuron intra-linked networks in
Propositions 4.9 and 4.10 have a number of pieces larger than the upper bounds
of feedforward networks. In Proposition 4.11, by enumerating all possible
cases, we present a construction for a 2-neuron intra-linked network of width
2 and arbitrary depth whose number of pieces is larger than what a feedforward
network of width 2 and arbitrary depth possibly achieves. Proposition 4.12
shows that $\prod_{i=1}^{k}\left(\frac{(w_{i}+1)w_{i}}{2}+1\right)$ pieces can
be achieved by a one-hidden-layer all-intra-linked network. Propositions 4.13
and 4.14 provide rather tight constructions for an all-neuron intra-linked
network of width 3&4 and arbitrary depth.

######  Proposition 4.9 (The bound
$\prod_{i=1}^{k}\left(\frac{3w_{i}}{2}+1\right)$ is tight for a two-hidden-
layer 2-neuron intra-linked network).

Given an $\mathbb{R}\rightarrow\mathbb{R}$ two-hidden-layer ReLU network, with
every two neurons linked in each hidden layer, for any even $w_{1}\geq
6,w_{2}\geq 4$, there exists a PWL function represented by such a network,
whose number of pieces is
$\left(\frac{3w_{1}}{2}+1\right)\left(\frac{3w_{2}}{2}+1\right)$.

###### Proof.

Please see Appendix C.

∎

######  Proposition 4.10 (Use intra-linked networks to achieve a sawtooth
function with $\prod_{i=1}^{k}\left(\frac{3w_{i}}{2}\right)$ pieces).

There exists a $[0,1]\rightarrow\mathbb{R}$ function represented by an intra-
linked ReLU DNN with depth $k+1$ and width $w_{1},\ldots,w_{k}$ of $k$ hidden
layers, whose number of pieces is at least
$\frac{3w_{1}}{2}\cdot\ldots\cdot\frac{3w_{k}}{2}$.

###### Proof.

Please see Appendix D.

∎

######  Proposition 4.11 (Intra-layer links can greatly increase the number of
pieces in an $\mathbb{R}\to\mathbb{R}$ ReLU network with width 2 and arbitrary
depth).

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a PWL function represented by an
$\mathbb{R}\rightarrow\mathbb{R}$ $(k+1)$-layer ReLU DNN with widths $2$ of
all $k$ hidden layers. Then the number of pieces of $f$ is at most
$\left\\{\begin{array}[]{cc}\sqrt{7}^{k},&\text{ if }k\text{ is even, }\\\
3\cdot\sqrt{7}^{k-1},&\text{ if }k\text{ is odd. }\end{array}\right.$

There exists an $\mathbb{R}\rightarrow\mathbb{R}$ $(k+1)$-layer $2$-wide ReLU
DNN, with neurons linked in each hidden layer, which can produce at least
$7\cdot 3^{k-2}+2$ pieces.

###### Proof.

The proof is put in Appendix E. ∎

######  Proposition 4.12 (
$\prod_{i=1}^{k}\left(\frac{(w_{i}+1)w_{i}}{2}+1\right)$ pieces for a one-
hidden-layer all-neuron intra-linked network).

Given an $\mathbb{R}\rightarrow\mathbb{R}$ one-hidden-layer ReLU network with
all neurons linked in the hidden layer, there exists a PWL function
represented by such a network, whose number of pieces is
$\frac{(w_{1}+1)w_{1}}{2}+1$.

###### Proof.

For the first layer, $\tilde{f}_{1}^{(1)}$ has one breakpoint and each
$\tilde{f}_{1}^{(j)}$ has at most $j$ newly produced breakpoints and some old
breakpoints of $\tilde{g}_{1}^{(j)}$ and $\tilde{f}_{1}^{(j-1)}$, for
$j=2,\ldots,n_{1}$. Hence, the first layer gives at most
$\frac{w_{i}+1}{2}w_{i}+1$ pieces. Then the rest of the proof is similar to
Theorem 4.6. ∎

######  Proposition 4.13 (An arbitrarily deep network of width=3 and with all
neurons in each layer intra-linked can achieve at least $5^{k}$ pieces).

There exists an $\mathbb{R}\rightarrow\mathbb{R}$ function represented by an
intra-linked ReLU DNN with depth $k$, width $3$ in each layer, and all neurons
intra-linked in each layer, whose number of pieces is at least $5^{k}$.

######  Proposition 4.14 (An arbitrarily deep network of width=4 and with all
neurons in each layer intra-linked can achieve at least $9^{k}$ pieces).

There exists an $\mathbb{R}\rightarrow\mathbb{R}$ function represented by an
intra-linked ReLU DNN with depth $k$, width $4$ in each layer, and all neurons
in each layer intra-linked, whose number of pieces is at least $9^{k}$.

###### Proof.

The proofs of Propositions 4.12, 4.13, and 4.14 are put in Appendix G. ∎

####  4.1.3 Functional Space Analysis

The above constructive analyses demonstrate that in the maximal sense, intra-
layer links can empower a feedforward network to represent a function with
more pieces. Now, we move one step forward by showing that intra-layer links
can surprisingly expand the functional space of a feedforward network. The
reason why this result is surprising is that one tends to think an intra-
linked network produces an exclusively different function from a feedforward
network. However, here we report that given an arbitrary feedforward ReLU
network, adding intra-layer links in the first layer can definitely expand its
functional space (Theorem 4.15). The core is that an intra-linked one-hidden-
layer network of two neurons can express a feedforward one-hidden-layer
network of two neurons, and the opposite doesn’t hold true.

######  Theorem 4.15.

Let $f$ be any $\mathbb{R}\rightarrow\mathbb{R}$ PWL representable by a
classical $(k+1)$-layer ReLU DNN with widths $w_{1}>2,\ldots,w_{k}$ of $k$
hidden layers. Then, $f$ can also be represented by a $(k+1)$-layer ReLU DNN
with widths $w_{1},\ldots,w_{k}$ of $k$ hidden layers, with neurons in the
first layer linked.

Remark 2. Finding new and powerful network architectures has been always
important in deep learning. Although the focus of our draft is the depth
separation theory rather than designing new architectures, our analysis
theoretically suggests that an intra-linked network is more powerful than a
feedforward network. Moreover, since adding intra-layer links increases no
trainable parameters, they can serve as an economical add-on to the model to
use parameters more efficiently. Even if only every two neurons are intra-
linked in a layer, the improvement is exponentially dependent on depth, i.e.,
approximately $\mathcal{O}(\frac{3}{2})^{k}$, which is considerable when a
network is deep.

###  4.2 Modify the Depth Separation Theorem with Intra-layer Links

In a broad sense, the depth separation theorem consists of two elements: i)
there exists a function representable by a deep network; ii) such a function
cannot be represented by a shallow network whose width is lower than a
threshold. Since adding intra-layer links can generally improve the capability
of a network, if one adds intra-layer links to a shallow network, the function
constructed by a deep network can be represented by a shallow network, even if
the width of this shallow network is still lower than the threshold. Theorem
4.17 showcases that a shallow network with all-neuron intra-layer links can
save the width up to a linear reduction. Theorems 4.18 and 4.19 modify the
depth separation $k^{2}$ vs 3 and $k^{2}$ vs $k$, respectively, by presenting
that a shallow network with 2-neuron intra-layer links only needs to go
$\frac{2}{3}$ times as wide as before to express the same function.

######  Lemma 4.16 (A network with width=2 can approximate any univariate PWL
function (Fan et al., 2021)).

Given a univariate PWL function with $n$ pieces $p(x)$, there exists a
$(n+1)$-layer network $\mathbf{D}(x)$ with two neurons in each layer such that
$f(x)=\mathbf{D}(x)$.

######  Theorem 4.17 (Modify the depth separation $k^{2}$ vs 2).

For every $k\geq 2$, there exists a function $p(x)$ that can be represented by
a $(k^{2}+1)$-layer ReLU DNN with 2 nodes in each layer, such that it cannot
be represented by a classical $2$-layer ReLU DNN $\mathbf{W}_{2}(x)$ with
width less than $k^{2}-1$, but can be represented by a $2$-layer, $(2k)$-wide
intra-linked ReLU DNN $\tilde{\mathbf{W}}_{2}(x)$.

###### Proof.

Combining Theorem 4.4, Theorem 4.12, and Lemma 4.16 straightly concludes the
proof. ∎

######  Theorem 4.18 (Modify the depth separation $k^{2}$ vs 3).

For every $k\geq 2$, there exists a function $p(x)$ that can be represented by
a $(k^{2}+1)$-layer ReLU DNN with 2 nodes in each layer, such that it cannot
be represented by a classical $3$-layer ReLU DNN $\mathbf{W}_{3}(x)$ with
width less than $k-1$, but can be represented by a $3$-layer,
$\frac{2(k-1)}{3}$-wide intra-linked ReLU DNN $\tilde{\mathbf{W}}_{3}(x)$.

###### Proof.

Combining Theorem 4.4, Proposition 4.9, and Lemma 4.16 straightly concludes
the proof. ∎

######  Theorem 4.19 (Modify the depth separation $k^{2}$ vs $k$).

For every $k\geq 1$, there is a $[0,1]\rightarrow\mathbb{R}$ PWL function
$p(x)$ represented by a feedforward $(2k^{2}+1)$-layer ReLU DNN with at most
$6$ nodes in each layer, such that it cannot be represented by a classical
$(k+1)$-layer ReLU DNN $W_{k}(x)$ with width less than $6^{k}$, but can be
represented by a $(k+1)$-layer 2-neuron intra-linked ReLU DNN
$\tilde{W}_{k}(x)$ with width no more than $4\cdot 6^{k-1}$.

###### Proof.

Per (Telgarsky, 2016)’s construction, a feedforward $(2k^{2}+1)$-layer ReLU
DNN with at most $2$ nodes in each layer can produce a sawtooth function of
$2^{k^{2}}$ pieces. Similarly, a feedforward $(2k^{2}+1)$-layer ReLU DNN with
at most $6$ nodes in each layer can have $6^{k^{2}}$ pieces. Thus, it follows
Theorem 4.4 that any classical $(k+1)$-layer ReLU DNN $W_{k}(x)$ with width
less than $6^{k}-1$ cannot generate $6^{k^{2}}$ pieces. However, according to
the construction in Proposition 4.10, let $w_{1}=w_{2}=\cdots=w_{k}=4\cdot
6^{k-1}$, an intra-linked network can exactly express a sawtooth function with
$6^{k^{2}}$ pieces. ∎

Remark 3. The existing depth separation theory is established for feedforward
networks. Our systematic analyses reveal that when considering shortcuts, the
existing depth separation can be modified in terms of reducing the bar of
width. Theorem 4.17 implicates that intra-layer links can reduce the bar of
the width substantially ($\mathcal{O}(1/w)$), where $w$ is the original width,
with a linear reduction. Our highlight is the existence of such shallow
networks that can be transformed by intra-layer links to have representation
power on a par with a deep network. Such shallow networks go against the
predictions of depth separation theory.

##  5 Discussion and Conclusion

Well-established network architectures such as ResNet and DenseNet imply that
incorporating shortcuts greatly empowers a neural network. However, only a
limited number of theoretical studies attempted to explain the representation
ability of shortcuts Veit et al. (2016); Fan et al. (2021); Lin and Jegelka
(2018). Although intra-layer links and residual connections are essentially
two different kinds of shortcuts, the techniques we developed and the
mechanisms we identified in analyzing intra-linked networks can be extended to
other networks with shortcuts. On the one hand, we identified conditions for
the tightness of the bound, which has been proven to be stronger than existing
results. Specifically, in the activation step, we distinguish the existing and
newly generated breakpoints to avoid repeated counting, and then in the
following pre-activation step, we maximize the oscillation to yield the most
pieces after the next activation. On the other hand, the construction of
functions in our work, i.e., constructing oscillations by preserving existing
breakpoints and splitting each piece into several ones, is generic in
analyzing other popular types of networks, thereby explaining how the shortcut
connections improve the representation power of a network.

For example, it is straightforward to see that a one-neuron-wide ReLU DNN can
represent PWL functions with at most three pieces, no matter how deep the
network is. However, as Theorem 5.1 shows, with residual connections, a ResNet
with $k$ neurons can represent a sawtooth function with $\mathcal{O}(k)$
pieces, which cannot be done by a feedforward network. For DenseNet, Theorem
4.4 shows that an $\mathbb{R}\rightarrow\mathbb{R}$ ReLU DNN with depth $k+1$
and width $w_{1},\ldots,w_{k}$ has at most $\prod_{i=1}^{k}(w_{i}+1)$ pieces.
If we add dense intra-layer links that connect any two neurons in a hidden
layer to turn a feedforward network into a DenseNet, Theorem 5.2 shows that
the so-obtained DenseNet can produce much more pieces than the feedforward
network. The difference is exponential, i.e.,
$1+\prod_{i=1}^{k}\left(2^{w_{i}}-1\right)$ vs $\prod_{i=1}^{k}(w_{i}+1)$. The
detailed proofs are put into Appendix H.

######  Theorem 5.1.

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a PWL function represented by a
one-neuron-wide ResNet. Mathematically, $f=c_{k+1}f_{k}+g_{k}$, where
$g_{1}(x)=x,f_{i}=\sigma\left(a_{i}g_{i}+b_{i}\right),g_{i+1}=c_{i}f_{i}+g_{i},c_{k+1},a_{i},b_{i},c_{i}$
are parameters, for $i=1,\ldots,k$. Then $f$ has at most $2^{k}$ pieces.
Furthermore, this upper bound is tight and $f$ can be a sawtooth function with
at most $2^{k}$ pieces.

######  Theorem 5.2.

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a PWL function represented by a
DenseNet obtained by adding dense intra=layer links into a feedforward network
with depth $k+1$ and width $w_{1},\ldots,w_{k}$ of $k$ hidden layers. Then we
can construct such a PWL function $f$ with at least
$1+\prod_{i=1}^{k}\left(2^{w_{i}}-1\right)$ pieces.

In this draft, via bound estimation, dedicated construction, and functional
space analysis, we have shown that an intra-linked network is much more
expressive than a feedforward one. Then, we have modified the depth separation
results to that a shallow network that previously cannot express some
functions constructed by deep networks now can do the job with intra-layer
links. Our results supplement the existing depth separation theory, and
suggest the potential of intra-layer links. At the same time, the identified
mechanism of generating pieces can also be used to decode the power of other
shortcut networks such as ResNet and DenseNet. Future endeavors can be
training networks using intra-layer links to solve real-world problems.

## References

  * Arora et al. (2016) Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee.  Understanding deep neural networks with rectified linear units.  _arXiv preprint arXiv:1611.01491_ , 2016.
  * Bianchini and Scarselli (2014) Monica Bianchini and Franco Scarselli.  On the complexity of neural network classifiers: A comparison between shallow and deep architectures.  _IEEE transactions on neural networks and learning systems_ , 25(8):1553–1565, 2014.
  * Bu et al. (2020) Kaifeng Bu, Yaobo Zhang, and Qingxian Luo.  Depth-width trade-offs for neural networks via topological entropy.  _arXiv preprint arXiv:2010.07587_ , 2020.
  * Eldan and Shamir (2016) Ronen Eldan and Ohad Shamir.  The power of depth for feedforward neural networks.  In _Conference on learning theory_ , pages 907–940. PMLR, 2016.
  * Fan et al. (2020) Feng-Lei Fan, Rongjie Lai, and Ge Wang.  Quasi-equivalence of width and depth of neural networks.  _arXiv preprint arXiv:2002.02515_ , 2020.
  * Fan et al. (2021) Fenglei Fan, Dayang Wang, Hengtao Guo, Qikui Zhu, Pingkun Yan, Ge Wang, and Hengyong Yu.  On a sparse shortcut topology of artificial neural networks.  _IEEE Transactions on Artificial Intelligence_ , 2021.
  * Gühring et al. (2020) Ingo Gühring, Mones Raslan, and Gitta Kutyniok.  Expressivity of deep neural networks.  _arXiv preprint arXiv:2007.04759_ , 2020.
  * Hanin and Rolnick (2019) Boris Hanin and David Rolnick.  Deep relu networks have surprisingly few activation patterns.  In _Advances in Neural Information Processing Systems_ , pages 359–368, 2019.
  * Hu and Zhang (2018) Qiang Hu and Hao Zhang.  Nearly-tight bounds on linear regions of piecewise linear neural networks.  _arXiv preprint arXiv:1810.13192_ , 2018.
  * Jalali et al. (2019) Shirin Jalali, Carl Nuzman, and Iraj Saniee.  Efficient deep learning of gmms.  _arXiv preprint arXiv:1902.05707_ , 2019.
  * Joshi et al. (2023) Chaitanya K Joshi, Cristian Bodnar, Simon V Mathis, Taco Cohen, and Pietro Liò.  On the expressive power of geometric graph neural networks.  _arXiv preprint arXiv:2301.09308_ , 2023.
  * LeCun et al. (2015) Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  _nature_ , 521(7553):436–444, 2015.
  * Lin and Jegelka (2018) Hongzhou Lin and Stefanie Jegelka.  Resnet with one-neuron hidden layers is a universal approximator.  _Advances in Neural Information Processing Systems_ , 31:6169–6178, 2018.
  * Malach and Shalev-Shwartz (2019) Eran Malach and Shai Shalev-Shwartz.  Is deeper better only when shallow is good?  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Montúfar (2017) Guido Montúfar.  Notes on the number of linear regions of deep neural networks.  _Sampling Theory Appl., Tallinn, Estonia, Tech. Rep_ , 2017.
  * Montufar et al. (2014) Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio.  On the number of linear regions of deep neural networks.  In _Advances in neural information processing systems_ , pages 2924–2932, 2014.
  * Pascanu et al. (2013) Razvan Pascanu, Guido Montufar, and Yoshua Bengio.  On the number of response regions of deep feed forward networks with piece-wise linear activations.  _arXiv preprint arXiv:1312.6098_ , 2013.
  * Poggio et al. (2017) Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao.  Why and when can deep-but not shallow-networks avoid the curse of dimensionality: a review.  _International Journal of Automation and Computing_ , 14(5):503–519, 2017.
  * Poggio et al. (2020) Tomaso Poggio, Andrzej Banburski, and Qianli Liao.  Theoretical issues in deep networks.  _Proceedings of the National Academy of Sciences_ , 117(48):30039–30045, 2020.
  * Poole et al. (2016) Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli.  Exponential expressivity in deep neural networks through transient chaos.  _Advances in neural information processing systems_ , 29, 2016.
  * Raghu et al. (2017) Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein.  On the expressive power of deep neural networks.  In _international conference on machine learning_ , pages 2847–2854. PMLR, 2017.
  * Rolnick and Tegmark (2017) David Rolnick and Max Tegmark.  The power of deeper networks for expressing natural functions.  _arXiv preprint arXiv:1705.05502_ , 2017.
  * Safran and Lee (2022) Itay Safran and Jason Lee.  Optimization-based separations for neural networks.  In _Conference on Learning Theory_ , pages 3–64. PMLR, 2022.
  * Safran and Shamir (2017) Itay Safran and Ohad Shamir.  Depth-width tradeoffs in approximating natural functions with neural networks.  In _International conference on machine learning_ , pages 2979–2987. PMLR, 2017.
  * Safran et al. (2019) Itay Safran, Ronen Eldan, and Ohad Shamir.  Depth separations in neural networks: what is actually being separated?  In _Conference on Learning Theory_ , pages 2664–2666. PMLR, 2019\.
  * Sanford and Chatziafratis (2022) Clayton H Sanford and Vaggos Chatziafratis.  Expressivity of neural networks via chaotic itineraries beyond sharkovsky’s theorem.  In _International Conference on Artificial Intelligence and Statistics_ , pages 9505–9549. PMLR, 2022.
  * Serra et al. (2018) Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam.  Bounding and counting linear regions of deep neural networks.  In _International Conference on Machine Learning_ , pages 4558–4566. PMLR, 2018.
  * Stanley (2004) Richard P. Stanley.  An introduction to hyperplane arrangements.  In _Lecture Notes, IAS/Park City Mathematics Institute_ , 2004.
  * Telgarsky (2015) Matus Telgarsky.  Representation benefits of deep feedforward networks.  _arXiv preprint arXiv:1509.08101_ , 2015.
  * Telgarsky (2016) Matus Telgarsky.  Benefits of depth in neural networks.  In _Conference on learning theory_ , pages 1517–1539. PMLR, 2016\.
  * Vardi and Shamir (2020) Gal Vardi and Ohad Shamir.  Neural networks with small weights and depth-separation barriers.  _Advances in neural information processing systems_ , 33:19433–19442, 2020.
  * Vardi et al. (2021) Gal Vardi, Daniel Reichman, Toniann Pitassi, and Ohad Shamir.  Size and depth separation in approximating benign functions with neural networks.  In _Conference on Learning Theory_ , pages 4195–4223. PMLR, 2021\.
  * Veit et al. (2016) Andreas Veit, Michael J Wilber, and Serge Belongie.  Residual networks behave like ensembles of relatively shallow networks.  _Advances in neural information processing systems_ , 29, 2016.
  * Venturi et al. (2021) Luca Venturi, Samy Jelassi, Tristan Ozuch, and Joan Bruna.  Depth separation beyond radial functions.  _Journal of Machine Learning Research_ , 2021.
  * Venturi et al. (2022) Luca Venturi, Samy Jelassi, Tristan Ozuch, and Joan Bruna.  Depth separation beyond radial functions.  _The Journal of Machine Learning Research_ , 23(1):5309–5364, 2022.
  * Xiong et al. (2020) Huan Xiong, Lei Huang, Mengyang Yu, Li Liu, Fan Zhu, and Ling Shao.  On the number of linear regions of convolutional neural networks.  In _International Conference on Machine Learning_ , pages 10514–10523. PMLR, 2020.
  * Zaslavsky (1975) T. Zaslavsky.  _Facing up to arrangements : face-count formulas for partitions of space by hyperplanes_.  Number 154 in Memoirs of the American Mathematical Society. American Mathematical Society, 1975.
  * Zaslavsky (1997) T Zaslavsky.  Facing up to arrangements: face-count formulas for partitions of space by hyperplanes.  _Memoirs of American Mathematical Society_ , 154:1–95, 1997\.

## Contents of Appendices

Section A provides a proof of Theorem 4.8.

Section B provides supplementary results to justify the tightness of Theorem
4.4.

Section C provides a proof of Proposition 4.9.

Section D provides a proof of Proposition 4.10.

Section E provides a proof of Proposition 4.11.

Section F provides a proof of Theorem 4.15.

Section G extends the results of 2-intra-linked networks to a network with
more intra-layer links.

Section H demonstrates that the analysis tools developed for intra-linked
networks can also be used to analyze the power of ResNet and DenseNet.

##  Appendix A Proof of Theorem 4.8

######  Lemma A.1 (Zaslavsky’s Theorem Zaslavsky [1975], Stanley [2004]).

Let $\mathcal{A}=\left\\{H_{i}\subset V:1\leq i\leq m\right\\}$ be an
arrangement in $\mathbf{R}^{n}$. Then, the number of regions for the
arrangement $\mathcal{A}$ satisfies

$\displaystyle r(\mathcal{A})\leq\sum_{i=0}^{n}\binom{m}{i}.$ (1)

###### Proof.

We prove by induction on $k$. For the base case $k=1$,
$\tilde{f}_{1}^{(2i-1)}=\sigma\left(\tilde{g}_{1}^{(2i-1)}\right)$ produces
one hyperplane in the input space $\mathbb{R}^{n}$. Furthermore,
$\tilde{f}_{1}^{(2i)}=\sigma\left(\tilde{g}_{1}^{(2i)}-\tilde{f}_{1}^{(2i-1)}\right)=\sigma\left(\tilde{g}_{1}^{(2i)}-\sigma\left(\tilde{g}_{1}^{(2i-1)}\right)\right)$
produces at most two hyperplanes in the input space $\mathbb{R}^{n}$.
Therefore, in total, the $w_{1}$ neurons in the first layer produces
$(1+2)\cdot\frac{w_{1}}{2}=\frac{3w_{1}}{2}$ hyperplanes in the input space
$\mathbb{R}^{n}$. Then by Zaslavsky’s Theorem, it will produce at most
$\sum_{j=0}^{n}\binom{w_{1}+1}{j}$ linear regions in the input space
$\mathbb{R}^{n}$. For the induction step, we assume that for some $k\geq 1$,
any $\mathbb{R}^{n}\rightarrow\mathbb{R}$ ReLU DNN with every two neurons
linked in each hidden layer, depth $k+1$ and widths $w_{1},\ldots,w_{k}$ of
$k$ hidden layers produces at most
$\prod_{i=1}^{k}\sum_{j=0}^{n}\binom{\frac{3w_{i}}{2}+1}{j}$ linear regions.
Now we consider any $\mathbb{R}^{n}\rightarrow\mathbb{R}$ ReLU DNN with every
two neurons linked in each hidden layer, depth $k+2$ and widths
$w_{1},\ldots,w_{k+1}$ of $k+1$ hidden layers. Then for each linear region $S$
produced by the first $k+1$ layers, again,
$\tilde{f}_{k+1}^{(2i-1)}=\sigma\left(\tilde{g}_{k+1}^{(2i-1)}\right)$
produces one hyperplane in $S$. Furthermore,
$\tilde{f}_{k+1}^{(2i)}=\sigma\left(\tilde{g}_{k+1}^{(2i)}-\tilde{f}_{k+1}^{(2i-1)}\right)=\sigma\left(\tilde{g}_{k+1}^{(2i)}-\sigma\left(\tilde{g}_{k+1}^{(2i-1)}\right)\right)$
produces at most two hyperplanes in the $S$. Therefore, in total, the
$w_{k+1}$ neurons in the $k+1$ layer produces
$(1+2)\cdot\frac{w_{k+1}}{2}=\frac{3w_{k+1}}{2}$ hyperplanes in $S$. Then by
Zaslavsky’s Theorem, it will produce at most
$\sum_{j=0}^{n}\binom{w_{k+1}+1}{j}$ linear regions in $S$. Thus $f$ has at
most $\prod_{i=1}^{k}\sum_{j=0}^{n}\binom{\frac{3w_{i}}{2}+1}{j}$ linear
regions. ∎

##  Appendix B Supplementary Results for the Tightness of Theorem 4.4

######  Proposition B.1 (The bound $\prod_{i=1}^{k}\left(w_{i}+1\right)$ is
tight for a depth-bounded but width-unbounded network).

Given an $\mathbb{R}\rightarrow\mathbb{R}$ two-hidden-layer ReLU network, for
any width $w_{1}\geq 3,w_{2}\geq 2$ in the first and second hidden layers,
there exists a PWL function represented by such a network, whose number of
pieces is $\left(w_{1}+1\right)\left(w_{2}+1\right)$.

###### Proof.

Figure 3: Construction of PWL functions to reach the bound of Proposition B.1
when $w_{1}=3$, $w_{2}=2$.

To guarantee the bound $\prod_{i=1}^{k}\left(w_{i}+1\right)$ is tight, the
following two requirements should be met: (i) each $g_{i}^{(j)}$, $i=0,1,2$,
$j=1,\ldots,w_{i}$, has distinct zero points that are as much as its number of
pieces, so that the activation step can produce the most new breakpoints; (ii)
the breakpoints of each $g_{(i+1)}^{(j)}$, $i=0,1,2$, $j=1,\ldots,w_{i+1}$, as
the affine combination of
$\left\\{f_{i}^{(1)},\ldots,f_{i}^{\left(w_{i}\right)}\right\\}$, contains all
the breakpoints of
$\left\\{g_{i}^{(1)},\ldots,g_{i}^{\left(w_{i}\right)}\right\\}$, so that all
the old breakpoints are reserved.

Now we give the proof in detail. Let
$f_{1}^{(1)}(x)=\sigma(3x),f_{1}^{(2)}(x)=\sigma(-x+3),f_{1}^{(3)}(x)=\sigma\left(\frac{3}{2}x-\frac{3}{2}\right)$.
When $w_{1}=3$, we set

$\begin{array}[]{l}g_{2}^{(1)}=-\left(f_{1}^{(1)}+f_{1}^{(2)}-f_{1}^{(3)}-3-\frac{1}{w_{2}+1}\right),\\\
g_{2}^{(j)}=f_{1}^{(1)}+f_{1}^{(2)}-f_{1}^{(3)}-3-\frac{j}{w_{2}+1},j=2,\ldots,w_{2}.\end{array}$

When $w_{1}>3$, we let $f_{1}^{(j)}=\sigma(-2x-2(j-3))$ and

$\begin{array}[]{l}g_{2}^{(1)}=-\left(f_{1}^{(1)}+f_{1}^{(2)}-f_{1}^{(3)}+\sum_{j=4}^{w_{1}}(-1)^{j-1}f_{1}^{(j)}-3-\frac{1}{w_{2}+1}\right)\\\
g_{2}^{(j)}=f_{1}^{(1)}+f_{1}^{(2)}-f_{1}^{(3)}+\sum_{r=4}^{w_{1}}(-1)^{r-1}f_{1}^{(r)}-3-\frac{j}{w_{2}+1},j=2,\ldots,w_{2}.\end{array}$

Then $g_{2}^{(j)}$ has $w_{1}+1$ distinct zero points. Hence for
$j=1,\ldots,w_{2}$, the breakpoints of
$f_{2}^{(j)}=\sigma\left(g_{2}^{(j)}\right)$ keeps all breakpoints of
$g_{2}^{(j)}$ and yields $w_{1}+1$ new breakpoints. Note that $f_{2}^{(j)}$
and $f_{2}^{(j)}$ do not share new breakpoints, and $f_{2}^{(1)}$ and
$f_{2}^{(2)}$ covers all the breakpoints of
$\left\\{g_{2}^{(j)}\right\\}_{j=1}^{w_{2}}$. Therefore, the total number of
pieces via an affine combination of
$f_{2}^{(1)},\ldots,f_{2}^{\left(w_{2}\right)}$ is
$\left(w_{1}+1\right)\left(w_{2}+1\right)$ pieces. ∎

######  Proposition B.2 (The bound $\prod_{i=1}^{k}\left(w_{i}+1\right)$ is
tight for a width-bounded but depth-unbounded network).

Given an $\mathbb{R}\rightarrow\mathbb{R}$ ReLU network with width $w$ for the
first layer and 3 for the other layers, for any depth $k\geq 2$, there exists
a PWL function represented by such a network, whose number of pieces is
$(w+1)\cdot 4^{k-1}$.

###### Proof.

Let $f_{1}^{(1)},\ldots f_{1}^{(w)}$ be the same as in Proposition B.1. Let

$\tilde{g}_{2}=\left\\{\begin{array}[]{c}f_{1}^{(1)}+f_{1}^{(2)}-f_{1}^{(3)}-3,\quad\text{
if }w=3,\\\
f_{1}^{(1)}+f_{1}^{(2)}-f_{1}^{(3)}+\sum_{j=4}^{w}(-1)^{j-1}f_{1}^{(j)}-3,\quad\text{
if }w>3.\end{array}\right.$

We set

$\begin{array}[]{l}f_{2}^{(1)}=\sigma\left(2\tilde{g}_{2}-\frac{1}{3}\right),\\\
f_{2}^{(2)}=\sigma\left(-\tilde{g}_{2}+\frac{2}{3}\right),\\\
f_{2}^{(3)}=\sigma\left(\frac{3}{2}\tilde{g}_{2}-\frac{1}{2}\right).\end{array}$

Now we continue our proof by induction. Assume we have constructed
$f_{i}^{(1)}$, $f_{i}^{(2)}$ and $f_{i}^{(3)}$, $i\geq 2$. Then we set

$\tilde{g}_{i+1}=f_{i}^{(1)}+f_{i}^{(2)}-f_{i}^{(3)}-\frac{3}{6^{i}}$

and

$\begin{array}[]{c}f_{i+1}^{(1)}=\sigma\left(2\tilde{g}_{i+1}-\frac{2}{6^{i}}\right),\\\
f_{i+1}^{(2)}=\sigma\left(-\tilde{g}_{i+1}-\frac{4}{6^{i}}\right),\\\
f_{i+1}^{(3)}=\sigma\left(\tilde{g}_{i+1}+\frac{3}{6^{i}}\right).\end{array}$

Through a direct calculus, we know $\tilde{g}_{i+1}$ has $(w+1)\cdot 4^{i-1}$
pieces with opposite slope in every two adjoint pieces and ranges from $0$ to
$3/6^{i}$ in each piece except the leftmost and rightmost piece, which implied
we can totally obtain $(w+1)\cdot 4^{k-1}$ pieces. ∎

##  Appendix C Proof of Proposition 4.9

######  Proposition C.1 (The bound
$\prod_{i=1}^{k}\left(\frac{3w_{i}}{2}+1\right)$ is tight for a two-hidden-
layer 2-neuron intra-linked network).

Given an $\mathbb{R}\rightarrow\mathbb{R}$ two-hidden-layer ReLU network, with
every two neurons linked in each hidden layer, for any even $w_{1}\geq
6,w_{2}\geq 4$, there exists a PWL function represented by such a network,
whose number of pieces is
$\left(\frac{3w_{1}}{2}+1\right)\left(\frac{3w_{2}}{2}+1\right)$.

###### Proof.

To guarantee the bound $\prod_{i=1}^{k}\left(\frac{3w_{i}}{2}+1\right)$ is
tight, the following two conditions should be satisfied: (i)
$\tilde{g}_{i}^{(j)}$ and $\tilde{g}_{i}^{(j+1)}-\tilde{f}_{i}^{(j)}$ have as
many zero points as possible so that $\sigma(\tilde{g}_{i}^{(j)})$ and
$\sigma(\tilde{g}_{i}^{(j+1)}-\tilde{f}_{i}^{(j)})$ can produce the maximal
number of breakpoints; (ii) all old breakpoints of
$\left\\{\tilde{g}_{i}^{(1)},\ldots,\tilde{g}_{i}^{\left(w_{i}\right)}\right\\}$
are reserved by $\tilde{g}_{i+1}^{(j)}$, an affine transform of
$\left\\{\tilde{f}_{i}^{(1)},\ldots,\tilde{f}_{i}^{\left(w_{i}\right)}\right\\}$.

We first consider the first hidden layer. Let

$\begin{array}[]{l}\tilde{f}_{1}^{(1)}(x)=\sigma\left(\frac{9}{2}x-27\right),~{}\tilde{f}_{1}^{(2)}(x)=\sigma\left(\frac{3}{2}x-\tilde{f}_{1}^{(1)}(x)\right)\\\
\tilde{f}_{1}^{(3)}(x)=\sigma(-2x+2),~{}~{}\tilde{f}_{1}^{(4)}(x)=\sigma\left(-x+2-\tilde{f}_{1}^{(3)}(x)\right)\\\
\tilde{f}_{1}^{(5)}(x)=\sigma\left(-\frac{7}{2}x-\frac{7}{4}\right),~{}\tilde{f}_{1}^{(6)}(x)=\sigma\left(-2x+8-\tilde{f}_{1}^{(5)}(x)\right).\end{array}$

When $w_{1}=6$, we set
$\tilde{g}=-\frac{2}{9}\tilde{f}_{1}^{(1)}-\tilde{f}_{1}^{(2)}+\frac{1}{2}\tilde{f}_{1}^{(3)}+\tilde{f}_{1}^{(4)}-\frac{4}{7}\tilde{f}_{1}^{(5)}-\tilde{f}_{1}^{(6)}.$

When $w_{1}>6$, for each odd $j>6$, let
$\tilde{f}_{1}^{(j)}=\sigma\left(-5\left(x-a_{j}+3\right)\right),\tilde{f}_{1}^{(j+1)}=\sigma\left(-2\left(x-a_{j}\right)-\tilde{f}_{1}^{(j)}\right),$
where $a_{j}=-\frac{19}{2}-9\left(\frac{j-1}{2}-3\right)$, then the output of
the first layer is expressed as the following:
$\tilde{g}=-\frac{2}{9}\tilde{f}_{1}^{(1)}-\tilde{f}_{1}^{(2)}+\frac{1}{2}\tilde{f}_{1}^{(3)}+\tilde{f}_{1}^{(4)}-\frac{4}{7}\tilde{f}_{1}^{(5)}-\tilde{f}_{1}^{(6)}+\sum_{j=7,j\text{
is odd
}}^{w_{2}}(-1)^{\frac{j+1}{2}}\left(\frac{2}{5}f_{1}^{(j)}+f_{1}^{(j+1)}\right),$
which has $\frac{3}{2}w_{1}+1$ pieces and whose adjacent pieces have slopes of
opposite signs. Note that any line $y=b$, where $b\in(-13/2,-6)$, can cross
all pieces of $\tilde{g}+b$. Thus, $g$ fulfills the conditions of Lemma 4.5.
We divide the breakpoints of $\tilde{g}$ into two parts:
$B_{upper}=\left\\{x:x\text{ is a breakpoint of }\tilde{g}\text{ and
}\tilde{g}(x)>b\right\\}$ and $B_{lower}=\left\\{x:x\text{ is a breakpoint of
}\tilde{g}\text{ and }\tilde{g}(x)\leq b\right\\}$. We refer to their counts
as #$B_{upper}$ and #$B_{lower}$.

Figure 4: The PWL functions that reach the bound of Proposition 4.9 when
$w_{1}=6$, $w_{2}=4$.

Next, we construct the second hidden layer.
$\tilde{f}_{2}^{(1)}:=\sigma\left(\tilde{g}+b_{1}\right)$, where
$b_{1}\in(-13/2,-6)$, has $\frac{3}{2}w_{1}+1$ new breakpoints. Then by
choosing some scaling parameter $a\in(0,1)$ bias $b_{2}$ to fulfill Lemma 4.5,
we can also make $a\tilde{g}+b_{2}-\tilde{f}_{2}^{(1)}$ has $3w_{1}+2$
distinct zero-points, which implies
$\tilde{f}_{2}^{(2)}:=\sigma\left(a\tilde{g}+b_{2}-\tilde{f}_{2}^{(1)}\right)$
has $3w_{1}+2$ newly produced breakpoints. Therefore, the affine combination
of $\tilde{f}_{2}^{(1)}$ and $\tilde{f}_{2}^{(2)}$ contains all breakpoints of
$B_{upper}$, and has
#$B_{upper}+\left(\frac{3}{2}w_{1}+1\right)+\left(3w_{1}+2\right)$
breakpoints. To reserve all the breakpoints of $\tilde{g}$, we do the similar
thing for $-\tilde{g}$ to gain $\tilde{f}^{(3)}_{2}$ and
$\tilde{f}^{(4)}_{2}$, whose affine combination has
#$B_{lower}+\left(\frac{3}{2}w_{1}+1\right)+\left(3w_{1}+2\right)$
breakpoints, which contains all breakpoints in $B_{lower}$, and shares no
breakpoints with the affine combination of
$\left\\{\tilde{f}^{(1)}_{2},\tilde{f}^{(2)}_{2}\right\\}$.

Hence, the affine combination of
$\left\\{\tilde{f}^{(1)}_{2},\tilde{f}^{(2)}_{2},\tilde{f}^{(3)}_{2},\tilde{f}^{(4)}_{2}\right\\}$
has #$B_{upper}+$ #
$B_{lower}+2\cdot\left(\frac{3w_{1}}{2}+1\right)+2\cdot\left(3w_{1}+2\right)=\left(\frac{3w_{1}}{2}\right)+6\cdot\left(\frac{3w_{1}}{2}+1\right)$
breaking points, which contains all the breakpoints of $\tilde{g}$.
$\left\\{\tilde{f}^{(1)}_{2},\tilde{f}^{(2)}_{2},\tilde{f}^{(3)}_{2},\tilde{f}^{(4)}_{2}\right\\}$
are visualized in Figure 4. Repeating this procedure by selecting different
$b_{1},a,b_{2}$, we can construct the remaining
$\\{\tilde{f}_{2}^{(i)}\\}_{i=5}^{w_{2}}$ such that the affine transformation
of $\\{\tilde{f}_{2}^{(i)}\\}_{i=1}^{w_{2}}$ has pieces of
$\frac{3}{2}w_{1}+\frac{3w_{2}}{2}\cdot\left(\frac{3}{2}w_{1}+1\right)+1=\left(\frac{3w_{1}}{2}+1\right)\left(\frac{3w_{2}}{2}+1\right)$.
∎

##  Appendix D Proof of Proposition 4.10

######  Proposition D.1 (Use intra-linked networks to achieve a sawtooth
function with $\prod_{i=1}^{k}\left(\frac{3w_{i}}{2}\right)$ pieces).

There exists a $[0,1]\rightarrow\mathbb{R}$ function represented by an intra-
linked ReLU DNN with depth $k+1$ and width $w_{1},\ldots,w_{k}$ of $k$ hidden
layers, whose number of pieces is at least
$\frac{3w_{1}}{2}\cdot\ldots\cdot\frac{3w_{k}}{2}$.

###### Proof.

Let $\phi(x)=x$ defined over $[0,\Delta]$. The core of the proof is to use a
one-hidden-layer network of $w\geq 2$ neurons to create $\frac{3w}{2}$ pieces
from $\phi(x)$.

Figure 5: A schematic illustration of how to use an intra-linked network to
generate a sawtooth function.

Let $\delta=\frac{2\Delta}{3w}$. Set $\tilde{g}^{(1)}=3\phi-3\delta$,
$\tilde{f}^{(1)}=\sigma\left(\tilde{g}^{(1)}\right)$, $\tilde{g}^{(2)}=\phi$,
$\tilde{f}^{(2)}=\sigma\left(\tilde{g}^{(2)}-\tilde{f}^{(1)}+\delta\right)$,
and $\tilde{g}^{(2j+1)}=4\phi-4(3j+1)\delta$,
$f^{(2j+1)}=\sigma\left(\tilde{g}^{(2j+1)}\right)$,
$\tilde{g}^{(2j+2)}=2\phi-6j\delta$,
$\tilde{f}^{(2j+2)}=\sigma\left(\tilde{g}^{(2j+2)}-\tilde{f}^{(2j+1)}\right)$,
for all $j=1,\ldots,w/2-1$. The output of this one-hidden-layer network is
$\xi_{\Delta,w}(x)=\frac{1}{3}\tilde{f}^{(1)}+\tilde{f}^{(2)}-\delta+\sum_{j=1}^{\frac{w}{2}-1}(-1)^{j}\left(\frac{1}{2}\tilde{f}^{(2j+1)}+\tilde{f}^{(2j+2)}\right),$
which has $\frac{3w}{2}$ pieces on $[0,\Delta]$. $\xi_{\Delta,w}(x)$ is of
slope $(-1)^{j}$ on $[j\delta,(j+1)\delta]$, $j=0,\ldots,3w/2-1$, and ranges
from $0$ to $\delta$ on each piece. Figure 5 shows how the affine
transformation of
$\\{\tilde{f}^{(1)},\tilde{f}^{(2)},\tilde{f}^{(3)},\tilde{f}^{(4)}\\}$
constructs a sawtooth function of 6 pieces. Please note that flipping
$\phi(x)$ or translating $\phi(x)$ will not prevent $\xi_{\Delta,w}(\phi(x))$
from generating $\frac{3w}{2}$ pieces.

The targeted intra-linked ReLU network with depth $k+1$ and width
$w_{1},\ldots,w_{k}$ of $k$ hidden layers is designed as
$\xi_{\Delta_{k},w_{k}}\circ\xi_{\Delta_{k-1},w_{k-1}}\circ\cdots\circ\xi_{\Delta_{1},w_{1}}(x)$,
where $\Delta_{i}=1/\Big{(}\prod_{j=1}^{i-1}\frac{3w_{i}}{2}\Big{)}$. ∎

##  Appendix E Proof of Proposition 4.11

###### Proof.

For the first assertion, we claim that each pre-activation $g_{i}^{(j)}$,
$2\leq i\leq k$, $j=1,2$, cannot have its every two adjacent pieces of slope
with different sign, which implies the activation cannot produce the most
breakpoints as in Lemma 4.3. In fact, $g_{2}^{(j)}$, $j=1,2$, has at most $3$
pieces. If some $g_{2}^{(j)}$ has $3$ pieces, then by exhaustion, we know
either it has a $0$-slope, or it has two adjacent pieces with slopes of the
same sign (see Figure 6). Hence, $f_{2}^{(j)}$, $j=1,2$, has at most $2$ newly
produced breakpoints. Then the output of the $2$-nd layer has at most
$2+2\times 2=6$ breakpoints, i.e., $7$ pieces. Applying a similar method to
each piece, we can get our result via a simple induction step.

Now we come to the second assertion. For convenience, we say an
$\mathbb{R}\rightarrow\mathbb{R}$ PWL function $f$ is of "triangle-trapezoid-
triangle" shape on $[a,b]\subset\mathbb{R}$, if there exists a partition of
$[a,b]:a<x_{1}<x_{2}<\cdots<x_{6}<b$ and a positive constant $c$, such that

$\left.f\right|_{[a,b]}(x)=\left\\{\begin{array}[]{cc}c&~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{,
if }x=a,x_{2},x_{5},b\\\ -c&~{}~{}\text{, if }x=x_{1},x_{6}\\\
-3c&~{}~{}~{}~{}\text{, if }x\in\left[x_{3},x_{4}\right]\\\ \text{linear
connection }&\text{, otherwise. }\end{array}\right.$

Given a PWL function $f:\mathbb{R}\rightarrow\mathbb{R}$ of "triangle-
trapezoid-triangle" shape on $[a,b]$, with corresponding partition
$a<x_{1}<x_{2}<\cdots<x_{6}<b$ and $f(a)=c>0$, if we set

$\begin{array}[]{l}g^{(1)}=4f\\\ g^{(2)}=2f-\frac{3c}{2}\\\
f^{(1)}=\sigma\left(g^{(1)}\right)\\\
f^{(2)}=\sigma\left(g^{(2)}-f^{(1)}\right),\end{array}$

then $g=-\frac{1}{4}f^{(1)}+f^{(2)}+\frac{c}{8}$ is of "triangle-trapezoid-
triangle" shape on
$\left[a,x_{2}\right],\left[x_{2},x_{5}\right]and\left[x_{5},b\right]$
respectively.

Using this fact, we can construct a PWL function represented by a
$(k+1)$-layer $2$-wide intra-linked ReLU DNN, which has $7\cdot 3^{k-2}+2$
pieces. Actually, set

$\begin{array}[]{l}\tilde{f}_{1}^{(1)}=\sigma(2x),\\\
\tilde{f}_{1}^{(2)}=\sigma\left(x-\tilde{f}_{1}^{(1)}+1\right),\\\
\tilde{g}_{2}^{(1)}=-4\tilde{f}_{1}^{(2)}+2,\\\
\tilde{g}_{2}^{(2)}=-2\tilde{f}_{1}^{(2)}+\frac{3}{2},\end{array}$

then through a direct calculus,
$\frac{1}{4}\tilde{f}_{2}^{(1)}+\tilde{f}_{2}^{(2)}-\frac{3}{8}$ is of
"triangle-trapezoid-triangle" shape on $[-1,1]$. Using the fact above
repeatedly, we can construct a PWL function represented by a
$\mathbb{R}\rightarrow\mathbb{R}$ $(k+1)$-layer, $2$-wide, intra-linked ReLU
DNN, which is constant on $(-\infty,-1]\cup[1,\infty)$ and of "triangle-
trapezoid-triangle" shape on
$\left[-1+\frac{2n}{3^{k-2}},-1+\frac{2(n+1)}{3^{k-2}}\right]$,
$n=0,\ldots,3^{k-2}-1$.

Figure 6: Exhaustion of all possible shapes of $g_{2}^{(j)}$,$j=1,2$ in
Proposition 4.11.

∎

##  Appendix F Proof of Theorem 4.15

######  Lemma F.1.

Let
$f^{(1)}=\sigma\left(a^{(1)}x+b^{(1)}\right),f^{(2)}=\sigma\left(a^{(2)}x+b^{(2)}\right),f=c^{(1)}f^{(1)}+c^{(2)}f^{(2)}+d$,
where $a^{(1)}a^{(2)}>0,b^{(1)},b^{(2)},c^{(1)},c^{(2)}$, and
$d\in\mathbb{R}$, there exists some
$\tilde{a}^{(1)},\tilde{a}^{(2)},\tilde{b}^{(1)},\tilde{b}^{(2)},\tilde{c}^{(1)},\tilde{c}^{(2)}$,
and $\tilde{d}\in\mathbb{R}$ such that
$f=\tilde{c}^{(1)}\tilde{f}^{(1)}+\tilde{c}^{(2)}\tilde{f}^{(2)}+\tilde{d}$,
where
$\tilde{f}^{(1)}=\sigma\left(\tilde{a}^{(1)}x+\tilde{b}^{(1)}\right),\tilde{f}^{(2)}=\sigma\left(\tilde{a}^{(2)}x+\tilde{b}^{(2)}-\tilde{f}^{(1)}\right)$.

###### Proof.

Without loss of generality, we assume $a^{(1)},a^{(2)}>0$ and
$-\frac{b^{(2)}}{a^{(2)}}<-\frac{b^{(1)}}{a^{(1)}}$. Then $f$ is of slope $0$,
$c^{(2)}a^{(2)}$, and $c^{(1)}a^{(1)}+c^{(2)}a^{(2)}$ on
$\left(-\infty,-\frac{b^{(2)}}{a^{(2)}}\right],\left[-\frac{b^{(2)}}{a^{(2)}},-\frac{b^{(1)}}{a^{(1)}}\right]$
and $\left[-\frac{b^{(1)}}{a^{(1)}},\infty\right)$, respectively. Now we
choose $\tilde{a}^{(1)},\tilde{a}^{(2)}$ satisfying
$0<\tilde{a}^{(1)}<\tilde{a}^{(2)}$, and set
$\tilde{b}^{(i)}=\frac{b^{(i)}}{a^{(i)}}$. $\tilde{a}^{(i)}$, $i=1,2$. Then
$\tilde{f}^{(1)}$ is of slope $0$ and $\tilde{a}^{(1)}$ on
$\left(-\infty,-\frac{b^{(1)}}{a^{(1)}}\right]$ and
$\left[-\frac{b^{(1)}}{a^{(1)}},\infty\right)$, respectively, while
$\tilde{f}^{(2)}$ is of slope 0, $\tilde{a}^{(2)}$, and
$\tilde{a}^{(2)}-\tilde{a}^{(1)}$ on
$\left(-\infty,-\frac{b^{(2)}}{a^{(2)}}\right),\left[-\frac{b^{(2)}}{a^{(2)}},-\frac{b^{(1)}}{a^{(1)}}\right]$,
and $\left(-\frac{b^{(1)}}{a^{(1)}},\infty\right)$, respectively. Hence, let
$\tilde{c}^{(2)}=c^{(2)}a^{(2)}/\tilde{a}^{(2)},\tilde{c}^{(1)}=\left(c^{(1)}a^{(1)}+c^{(2)}a^{(2)}-\right.\left.\tilde{c}^{(2)}\left(\tilde{a}^{(2)}-\tilde{a}^{(1)}\right)\right)/\tilde{a}^{(1)}$,
and $\tilde{d}=d$, we have
$f=\tilde{c}^{(1)}\tilde{f}^{(1)}+\tilde{c}^{(2)}\tilde{f}^{(2)}+\tilde{d}$. ∎

######  Theorem F.2.

Let $f$ be any $\mathbb{R}\rightarrow\mathbb{R}$ PWL representable by a
classical $(k+1)$-layer ReLU DNN with widths $w_{1}>2,\ldots,w_{k}$ of $k$
hidden layers. Then, $f$ can also be represented by a $(k+1)$-layer ReLU DNN
with widths $w_{1},\ldots,w_{k}$ of $k$ hidden layers, with neurons in the
first layer linked.

###### Proof.

Let the output of the $j$-th neuron of the first layer in the feedforward
network be $f_{1}^{(j)}(x)=\sigma\left(a_{1}^{(j)}x+b_{1}^{(j)}\right)$,
$j=1,\ldots,w_{1}$. Since the feedforward network is invariant to permutating
neurons, we can link the arbitrary $j$-th and $j^{\prime}$-th neuron if
$a_{1}^{(j)}a_{1}^{(j^{\prime})}>0$, which directly concludes the proof
according to Lemma F.1. ∎

Remark D.1. Generally, Theorem 4.15 does not hold for deeper layers. Since the
first layer has only one input while the higher layer generally has several
inputs so that Lemma F.1 does not hold. But Theorem 4.15 still holds for
higher layers of some special networks. For example, the function class in
Telgarsky [2015] is given by the composition of several
$\mathbb{R}\to\mathbb{R}$ functions, which makes the corresponding network has
one neuron in every other layer.

##  Appendix G Extension to more intra-layer links

Figure 7: The construction demonstrating that the bound
$\prod_{i=1}^{k}\left(\frac{(w_{i}+1)w_{i}}{2}+1\right)$ is tight for a one-
hidden-layer intra-linked network.

###  G.1 Proof of Proposition 4.12

###### Proof.

Without loss of generality, a one-hidden-layer network with all neurons intra-
linked is mathematically formulated as the following:

$\begin{cases}&\tilde{f}^{(1)}=\sigma(w^{(1)}x+b^{(1)})\\\
&\tilde{f}^{(j+1)}=\sigma(w^{(j)}x+b^{(j)}-\tilde{f}^{(j)})\\\ \end{cases}.$
(2)

To prove that the bound
$\prod_{i=1}^{k}\left(\frac{(w_{i}+1)w_{i}}{2}+1\right)$ is tight for a one-
hidden-layer network, the key is to make each $\tilde{f}^{(j)}$ produce $j$
new breakpoints and have $j$ non-zero pieces that share a point with $y=0$. We
use mathematical induction to derive our construction. Figure 7 schematically
illustrates our construction idea.

First, let $\tilde{f}^{(1)}=\sigma(x+1)$ and
$\tilde{f}^{(2)}=\sigma(0.5\times(x+2)-\tilde{f}^{(1)})$. Note that
$\tilde{f}^{(1)}$ has $1$ non-zero piece that shares a point with $y=0$, and
$\tilde{f}^{(2)}$ has $2$ non-zero pieces that share a common point with
$y=0$.

Then, given $\tilde{f}^{(j)},j\geq 2$, we suppose $\tilde{f}^{(j)}$ has $j$
non-zero pieces that share a point with $y=0$. Since $\tilde{f}^{(j)}$ is
continuous, we select its peaks $\\{(x_{p_{i}},\tilde{f}^{(j)}(x_{p_{i}}))\\}$
by the following conditions: i) $\tilde{f}^{(j)}$ is not differentiable at
$x_{p_{i}}$; ii) $\tilde{f}^{(j)}(x_{p_{i}})\neq 0$. Next, let
$(x^{*},\tilde{f}^{(j)}(x^{*}))$ be the lowest peak of $\tilde{f}^{(j)}$. As
long as the slope $w^{(j+1)}$ and the bias $b^{(j+1)}$ satisfy

$\begin{cases}&w^{(j+1)}<\frac{\tilde{f}_{1}^{(j)}(x^{*})}{x^{*}+j+1}\\\
&b^{(j+1)}=w_{j+1}\times(j+1)\end{cases},$ (3)

$w^{(j+1)}x+b^{(j+1)}$ crosses and only crosses $j$ pieces of
$\tilde{f}^{(j)}$. These pieces are exactly non-zero pieces that share a point
with $y=0$. Thus, plus the breakpoint $-\frac{b^{(j+1)}}{w^{(j+1)}}$,
$\tilde{f}^{(j+1)}$ generates a total of $j+1$ new breakpoints. At the same
time, $\tilde{f}^{(j+1)}$ has $j+1$ non-zero pieces that share a point with
$y=0$. Figure 7 illustrates the process of induction.

Finally, the total number of breakpoints is
$\sum_{j=1}^{w_{1}}j=\frac{(w_{1}+1)w_{1}}{2}$, which concludes our proof.

∎

###  G.2 Proof of Proposition 4.14

###### Proof.

The core of the proof is to use a one-hidden-layer all-neuron-intra-linked
network of width $4$ to create a quasi-sawtooth function with as many pieces
as possible. We construct four neurons as follows:

$\begin{cases}&\tilde{f}^{(1)}=\sigma(2x)\\\
&\tilde{f}^{(2)}=\sigma(x+1-\sigma(\tilde{f}^{(1)}))\\\
&\tilde{f}^{(3)}=\sigma(\frac{1}{3}(x+2)-\tilde{f}^{(2)})\\\
&\tilde{f}^{(4)}=\sigma(\frac{1}{9}(x+3)-\tilde{f}^{(3)})\end{cases}.$ (4)

The profiles of
$\tilde{f}^{(1)},\tilde{f}^{(2)},\tilde{f}^{(3)},\tilde{f}^{(4)}$ are shown in
Figure 8(a).

Figure 8: A schematic illustration of how to use an intra-linked network to
generate a sawtooth function.

By combining $\tilde{f}^{(1)},\tilde{f}^{(2)},\tilde{f}^{(3)},\tilde{f}^{(4)}$
with carefully calibrated coefficients, we have the following quasi-sawtooth
function that has $9$ pieces are

$\eta(x)=\tilde{f}^{(4)}+\frac{5}{84}\times\tilde{f}^{(3)}-\frac{1}{3}\times\tilde{f}^{(2)}+0\times\tilde{f}^{(1)}.$
(5)

As shown in Figure 8(b), we have marked all breakpoints of $\eta(x)$ to
validate its correctness.

Next, we just need to let each layer of the intra-linked network represent a
stretched and down-pulled variant of $\eta(x)$, e.g., the $k$-th layer
$\eta_{k}(x)=M_{k}\cdot\eta(x)-B_{k}$, where $M_{k}$ is a sufficiently large
number and $B_{k}>\frac{5}{504}M_{k}+3$ to ensure that $[-3,0]$ is within the
function range of $\eta_{k}(x)$.

Finally, the constructed network is

$\eta_{k}\circ\eta_{k-1}\circ\cdots\circ\eta_{1}(x).$ (6)

∎

###  G.3 Proof of Proposition 4.13

###### Proof.

Following the same spirit in proof of Theorem 4.14, we construct three neurons
as follows:

$\begin{cases}&\tilde{f}^{(1)}=\sigma(2x)\\\
&\tilde{f}^{(2)}=\sigma(x+1-\sigma(\tilde{f}^{(1)}))\\\
&\tilde{f}^{(3)}=\sigma(\frac{1}{3}(x+2)-\tilde{f}^{(2)})\end{cases}.$ (7)

The target function that returns us $5$ pieces is

$\xi(x)=\frac{1}{100}\times\tilde{f}^{(3)}-\frac{1}{3}\times\tilde{f}^{(2)}+0\times\tilde{f}^{(1)}.$
(8)

Next, we just need to let each layer of the intra-linked network represent a
stretched and down-pulled variant of $\xi(x)$, e.g., the $k$-th layer
$\xi_{k}(x)=T_{k}\cdot\eta_{k}(x)-C_{k}$, where $T_{k}$ is a sufficiently
large number and $C_{k}>\frac{1}{200}T_{k}+2$ to ensure that $[-2,0]$ is
within the function range of $\xi_{k}(x)$.

Finally, the constructed network is

$\xi_{k}\circ\xi_{k-1}\circ\cdots\circ\xi_{1}(x).$ (9)

∎

##  Appendix H Analysis Extended to ResNet and DenseNet

###  H.1 Proof of Theorem 5.1

###### Proof.

The first claim follows from Lemma 4.3 and a simple induction step. Following
the idea of the construction in Propositions 4.9 and 4.10, we set $c_{i}=-2$
and $a_{i}=1$ for all $i$ and set $b_{1}=0$, $b_{i}=2-2^{-i+2}$ for
$i=2,\ldots,k$ . ∎

Figure 9: A schematic illustration of using constructions in intra-linked
networks to analyze DenseNet.

###  H.2 Proof of Theorem 5.2

###### Proof.

For convenience, we only consider the case $w_{i}=3$, the general case is just
simply repeating this procedure. Let

$f_{1}^{(1)}(x)=\sigma(3x),f_{1}^{(2)}(x)=\sigma\left(\frac{3}{2}x+3-f_{1}^{(1)}\right),f_{1}^{(3)}(x)=\sigma\left(\frac{x}{2}+2-f_{2}-\frac{1}{3}f_{1}\right)$

be the neurons of the first hidden layer. Then we consider the affine
combination. It is easy to find coefficient $c_{1},c_{2}$ such that

$c_{1}f_{1}^{(1)}(x)+c_{2}f_{1}^{(2)}(x)=\left\\{\begin{array}[]{cc}\frac{3}{8}x+\frac{3}{4},&x\in[-2,0],\\\
-\frac{1}{4}x+\frac{3}{4},&x\in[0,2],\\\ \frac{x}{8},&x\in[2,4],\\\ 0,&\text{
otherwise. }\end{array}\right.$

A direct calculus gives
$\tilde{g}=c_{1}f_{1}^{(1)}(x)+c_{2}f_{1}^{(2)}(x)+f_{1}^{(3)}(x)$, shown in
Figure 9. Then follow the same idea in analyzing intra-linked networks, we
know all the non-constant pieces of $\tilde{g}$ can generate
$\prod_{i=1}^{k}\left(2^{w_{2}}-1\right)$ in the next layer and the result
follows after a simple induction step. ∎

Theorem 5.1 confirms that adding simple links can greatly improve the
representation ability of a network. Actually, both ResNet and intra-layer
linked networks do not increase the number of parameters, but they can
represent more complicated functions than the feedforward of the same neurons
used in each layer. Hence, the linked structure can improve the efficiency of
parameters. Besides, we can see from the proof of Theorem 5.1 and 5.2 that the
idea and construction in analyzing intra-linked networks can indeed be
utilized to analyze other architecture of networks.