The Expressive Power of Neural Networks: A View from the Width

Introduction

Deep neural networks have achieved state-of-the-art performance in a wide range of tasks such as speech recognition, computer vision, natural language processing, and so on. Despite their promising results in applications, our theoretical understanding of neural networks remains limited. The expressive power of neural networks, being one of the vital properties, is crucial on the way towards a more thorough comprehension.

The expressive power describes neural networks’ ability to approximate functions. This line of research dates back at least to 1980’s. The celebrated universal approximation theorem states that depth-$2$ networks with suitable activation function can approximate any continuous function on a compact domain to any desired accuracy . However, the size of such a neural network can be exponential in the input dimension, which means that the depth-$2$ network has a very large width.

From a learning perspective, having universal approximation is just the first step. One must also consider the efficiency, i.e., the size of the neural network to achieve approximation. Having a small size requires an understanding of the roles of depth and width for the expressive power. Recently, there are a series of works trying to characterize how depth affects the expressiveness of a neural network . show the existence of a $3$-layer network, which cannot be realized by any $2$-layer to more than a constant accuracy if the size is subexponential in the dimension. prove the existence of classes of deep convolutional ReLU networks that cannot be realized by shallow ones if its size is no more than an exponential bound. For any integer $k$, explicitly constructed networks with $O(k^{3})$ layers and constant width which cannot be realized by any network with $O(k)$ layers whose size is smaller than $2^{k}$. This type of results are referred to as depth efficiency of neural networks on the expressive power: a reduction in depth results in exponential sacrifice in width. However, it is worth noting that these are existence results. In fact, as pointed out in , proving existence is inevitable; There is always a positive measure of network parameters such that deep nets can’t be realized by shallow ones without substantially larger size. Thus we should explore more in addition to proving existence.

Different to most of the previous works which investigate the expressive power in terms of the depth of neural networks, in this paper we study the problem from the view of width. We argue that an integration of both views will provide a better understanding of the expressive power of neural networks.

Firstly, we prove a universal approximation theorem for width-bounded ReLU networks. Let $n$ denotes the input dimension, we show that width-$(n+4)$ ReLU networks can approximate any Lebesgue integrable function on $n$-dimensional space with respect to $L^{1}$ distance. On the other hand, except for a zero measure set, all Lebesgue integrable functions cannot be approximated by width-$n$ ReLU networks, which demonstrate a phase transition. Our result is a dual version of the classical universal approximation theorem for depth-bounded networks.

Next, we explore quantitatively the role of width for the expressive power of neural networks. Similar to the depth efficiency, we raise the following question on the width efficiency:

Are there wide ReLU networks that cannot be realized by any narrow network whose size is not substantially increased?

We argue that investigation of the above question is important for an understanding of the roles of depth and width for the expressive power of neural networks. Indeed, if the answer to this question is yes, and the size of the narrow networks must be exponentially larger, then it is appropriate to say that width has an equal importance as depth for neural networks.

In this paper, we prove that there exists a family of ReLU networks that cannot be approximated by narrower networks whose depth increase is no more than polynomial. This polynomial lower bound for width is significantly smaller than the exponential lower bound for depth. However, it does not rule out the possibility of the existence of an exponential lower bound for width efficiency. On the other hand, insights from the previous analysis suggest us to study if there is a polynomial upper bound, i.e., a polynomial increase in depth and size suffices for narrow networks to approximate wide and shallow networks. Theoretically proving a polynomial upper bound seems very difficult, and we formally pose it as an open problem. Nevertheless, we conduct extensive experiments and the results demonstrate that when the depth of the narrow network exceeds the polynomial lower bound by just a constant factor, it can approximate wide shallow networks to a high accuracy. Together, these results provide more comprehensive evidence that depth is more effective for the expressive power of ReLU networks.

Our contributions are summarized as follows:

We show a width efficiency polynomial lower bound. For integer $k$, there exist a class of width-$O(k^{2})$ and depth-2 ReLU networks that cannot be approximated by any width-$O(k^{1.5})$ and depth-$k$ networks. On the other hand, experimental results demonstrate that networks with size slightly larger than the lower bound achieves high approximation accuracy.

Research analyzing the expressive power of neural networks date back to decades ago. As one of the most classic work, Cybenko proved that a fully-connected sigmoid neural network with one single hidden layer can universally approximate any continuous univariate function on a bounded domain with arbitrarily small error. Barron , Hornik et al. ,Funahashi achieved similar results. They also generalize the sigmoid function to a large class of activation functions, showing that universal approximation is essentially implied by the network structure. Delalleau et al. showed that there exists a family of functions which can be represented much more efficiently with deep networks than with shallow ones as well.

Since the development and success of deep neural networks recently, there have been much more works discussing the expressive power of neural networks theoretically. Depth efficiency is among the most typical results.

The remainder of the paper is organized as follows. In section 2 we introduce some background knowledge needed in this article. In section 3 we present our main result – the Width-Bounded Universal Approximation Theorem; besides, we show two comparing results related to the theorem. Then in section 4 we turn to explore quantitatively the role of width for the expressive power of neural networks. Finally, section 5 concludes. All proofs can be found in the Appendix and we give proof sketch in main text as well.

Preliminaries

The architecture of neural networks often specified by the width and the depth of the networks. The depth $h$ of a network is defined as its number of layers (including output layer but excluding input layer); while the width $d_{m}$ of a network is defined to be the maximal number of nodes in a layer. The number of input nodes, i.e. the input dimension, is denoted as $n$.

Width-bounded ReLU Networks as Universal Approximator

In this section we consider universal approximation with width-bounded ReLU networks. The following theorem is the main result of this section.

The proof of this theorem is lengthy and is deferred to the supplementary material. Here we provide an informal description of the high level idea.

For any Lebesgue integrable function and any predefined approximation accuracy, we explicitly construct a width-$(n+4)$ ReLU network so that it can approximate the function to the given accuracy. The network is a concatenation of a series of blocks. Each block satisfies the following properties:

1) It is a depth-$(4n+1)$ width-$(n+4)$ ReLU network.

2) It can approximate any Lebesgue integrable function which is uniformly zero outside a cube with length $\delta$ to a high accuracy;

3) It can store the output of the previous block, i.e., the approximation of other Lebesgue integrable functions on different cubes;

4) It can sum up its current approximation and the memory of the previous approximations.

It is not difficult to see that the construction of the whole network is completed once we build the blocks. We illustrate such a block in Figure 1 . In this block, each layer has $n+4$ neurons. Each rectangle in Figure 1 represents a neuron, and the symbols in the rectangle describes the output of that neuron as a function of the block. Among the $n+4$ neurons, $n$ neurons simply transfer the input coordinates. For the other $4$ neurons, $2$ neurons store the approximation fulfilled by previous blocks. The other $2$ neurons help to do the approximation on the current cube. The topology of the block is rather simple. It is very sparse, each neuron connects to at most $2$ neurons in the next layer.

The proof is just to verify the construction illustrated in Figure 1 is correct. Because of the space limit, we defer all the details to the supplementary materials.

Theorem 1 can be regarded as a dual version of the classical universal approximation theorem, which proves that depth-bounded networks are universal approximator. If we ignore the size of the network, both depth and width themselves are efficient for universal approximation. At the technical level however, there are a few differences between the two universal approximation theorems. The classical depth-bounded theorem considers continuous function on a compact domain and use $L^{\infty}$ distance; Our width-bounded theorem instead deals with Lebesgue-integrable functions on the whole Euclidean space and therefore use $L^{1}$ distance.

Theorem 1 implies that there is a phase transition for the expressive power of ReLU networks as the width of the network varies across $n$, the input dimension. It is not difficult to see that if the width is much smaller than $n$, then the expressive power of the network must be very weak. Formally, we have the following two results.

Then it’s a direct comparison with Theorem 1 since in Theorem 1 the $L^{1}$ distance can be arbitrarily small.

The main idea of the two theorems is grabbing the disadvantage brought by the insufficiency of dimension. If the corresponding first layer values of two different input points are the same, the output will be the same as well. When the ReLU network’s width is not larger than the input layer’s width, we can find a ray for "most" points such that the ray passes the point and the corresponding first layer values on the ray are the same. It is like a dimension reduction caused by insufficiency of width. Utilizing this weakness of thin network, we can finally prove the theorem.

Width Efficiency vs. Depth Efficiency

Going deeper and deeper has been a trend in recent years, starting from the 8-layer AlexNet , the 19-layer VGG , the 22-layer GoogLeNet , and finally to the 152-layer and 1001-layer ResNets . The superiority of a larger depth has been extensively shown in the applications of many areas. For example, ResNet has largely advanced the state-of-the-art performance in computer vision related fields, which is claimed solely due to the extremely deep representations. Despite of the great practical success, theories of the role of depth are still limited.

Theoretical understanding of the strength of depth starts from analyzing the depth efficiency, by proving the existence of deep neural networks that cannot be realized by any shallow network whose size is exponentially larger. However, we argue that even for a comprehensive understanding of the depth itself, one needs to study the dual problem of width efficiency: Because, if we switch the role of depth and width in the depth efficiency theorems and the resulting statements remain true, then width would have the same power as depth for the expressiveness, at least in theory. It is worth noting that a priori, depth efficiency theorems do not imply anything about the validity of width efficiency.

In this section, we study the width efficiency of ReLU networks quantitatively.

Theorem 4 states that there are networks such that reducing width requires increasing in the size to compensate, which is similar to that of depth qualitatively. However, at the quantitative level, this theorem is very different to the depth efficiency theorems in . Depth efficiency enjoys exponential lower bound, while for width Theorem 4 is a polynomial lower bound. Of course if a corresponding polynomial upper bound can be proven, we can say depth plays a more important role in efficiency, but such a polynomial lower bound still means that depth is not strictly stronger than width in efficiency ,sometimes it costs depth super-linear more nodes than width.

This raises a natural question: Can we improve the polynomial lower bound? There are at least two possibilities.

1) Width efficiency has exponential lower bound. To be concrete, there are wide networks that cannot be approximated by any narrow networks whose size is no more than an exponential bound.

2) Width efficiency has polynomial upper bound. Every wide network can be approximated by a narrow network whose size increase is no more than a polynomial.

Exponential lower bound and polynomial upper bound have completely different implications. If exponential lower bound is true, then width and depth have the same strength for the expressiveness, at least in theory. If the polynomial upper bound is true, then depth plays a significantly stronger role for the expressive power of ReLU networks.

Currently, neither the exponential lower bound nor the polynomial upper bound seems within the reach. We pose it as a formal open problem.

We further conduct extensive experiments to provide some insights about the upper bound of such an approximation. To this end, we study a series of network architectures with varied width. For each network architecture, we randomly sample the parameters, which, together with the architecture, represent the function that we would like narrower networks to approximate. The approximation error is empirically calculated as the mean square error between the target function and the approximator function evaluated on a series of uniformly placed inputs. For simplicity and clearity, we refer to the network architectures that will represent the target functions when assigned parameters as target networks, and the corresponding network architectures for approximator functions as approximator networks.

To be detailed, the target networks are fully-connected ReLU networks of input dimension $n$, output dimension $1$, width $2k^{2}$ and depth $3$, for $n=1,2$ and $k=3,4,5$. For each of these networks, we sample weight parameters according to standard normal distribution, and bias parameters according to uniform distribution over $[-1,1)$. The network and the sampled parameters will collectively represent a target function that we use a narrow approximator network of width $3k^{3/2}$ and depth $k+2$ to approximate, with a corresponding $k$. The architectures are designed in accordance to Theorem 4 – we aim to investigate whether such a lower bound is actually an upper bound. In order to empirically calculate the approximation error, $20000$ uniformly placed inputs from $[-1,1)^{n}$ for $n=1$ and $40000$ such inputs for $n=2$ are evaluated by the target function and the approximator function respectively, and the mean square error is reported. For each target network, we repeat the parameter-sampling process $50$ times and report the mean square error in the worst and average case.

We adopt the standard supervised learning approach to search in the parameter space of the approximator network to find the best approximator function. Specifically, half of all the test inputs from $[-1,1)^{n}$ and the corresponding values evaluated by target function constitute the training set. The training set is used to train approximator network with a mini-batch AdaDelta optimizer and learning rate $1.0$. The parameters of approximator network are randomly initialized according to . The training process proceeds $100$ epoches for $n=1$ and $200$ epoches for $n=2$; the best approximator function is recorded.

Table 1 lists the results. Figure 2 illustrates the comparison of an example target function and the corresponding approximator function for $n=1$ and $k=5$. Note that the target function values vary with a scale $\sim 10$ in the given domain, so the (absolute) mean square error is indeed a rational measure of the approximation error. It is shown that the approximation error is indeed very small, for the target networks and approximator networks we study. From Figure 2 we can see that the approximation function is so close to the target function that we have to enlarge a local region to better display the difference. Since the architectures of both the target networks and approximator networks are determined according to Theorem 4, where the depth of approximator networks are in a polynomial scale with respect to that of target networks, the empirical results show an indication that a polynomial larger depth may be sufficient for a narrow network to approximate a wide network.

Conclusion

In this paper, we analyze the expressive power of neural networks with a view from the width, distinguished from many previous works which focus on the view from the depth. We establish the Universal Approximation Theorem for Width-Bounded ReLU Networks, in contrast with the well-known Universal Approximation Theorem, which studies depth-bounded networks. Our result demonstrate a phase transition with respect to expressive power when the width of a ReLU network of given input dimension varies.

We also explore the role of width for the expressive power of neural networks: we prove that a wide network cannot be approximated by a narrow network unless with polynomial more nodes, which gives a lower bound of the number of nodes for approximation. We pose open problems on whether exponential lower bound or polynomial upper bound hold for the width efficiency, which we think is crucial on the way to a more thorough understanding of expressive power of neural networks. Experimental results support the polynomial upper bound and agree with our intuition and insights from the analysis.

The width and the depth are two key components in the design of a neural network architecture. Width and depth are both important and should be carefully tuned together for the best performance of neural networks, since the depth may determine the abstraction level but the width may influence the loss of information in the forwarding pass. A comprehensive understanding of the expressive power of neural networks requires looking from both views.

Acknowledgments

This work was partially supported by National Basic Research Program of China (973 Program) (grant no. 2015CB352502), NSFC (61573026), and the elite undergraduate training program of School of Mathematical Science in Peking University. We would like to thank the anonymous reviewers for their valuable comments on our paper.

References

Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine Learning, 14(1):115–133, 1994.

Nadav Cohen, Or Sharir, and Amnon Shashua. On the expressive power of deep learning: A tensor analysis. In Conference on Learning Theory, pages 698–728, 2016.

George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals, and Systems (MCSS), 2(4):303–314, 1989.

Olivier Delalleau and Yoshua Bengio. Shallow vs. deep sum-product networks. In Advances in Neural Information Processing Systems, pages 666–674, 2011.

Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference on Learning Theory, pages 907–940, 2016.

Ken-Ichi Funahashi. On the approximate realization of continuous mappings by neural networks. Neural networks, 2(3):183–192, 1989.

Nick Harvey, Chris Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension bounds for piecewise linear neural networks. COLT 2017, 2017.

Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770–778, 2016.

Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359–366, 1989.

Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pages 1097–1105, 2012.

R. Srikant Shiyu Liang. Why deep neural networks for funtion approximation? ICLR 2017, 2017.

Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. CoRR, abs/1409.1556, 2014.

Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott E. Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. CoRR, abs/1409.4842, 2014.

Matus Telgarsky. Benefits of depth in neural networks. COLT 2016: 1517-1539, 2016.

Dmitry Yarotsky. Error bounds for approximations with deep relu networks. arXiv preprint arXiv:1610.01145, 2016.

Quynh Nguyen and Matthias Hein. The loss surface of deep and wide neural networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2603–2612, International Convention Centre, Sydney, Australia, 06–11 Aug 2017. PMLR.

Appendix A Appendix

We prove this theorem by constructing a network architecture which can approximate any Lesbegue-integrable function w.r.t $L^{1}$ distance. We will firstly illustrate that $f$ can be approximated by finite weighted sum of indicator functions on n-dimensional cubes. Then we will show how a ReLU network approximate an indicator function on an n-dimensional cube. Finally we will show that ReLU network can "store" the quantities and sum them up.

Assume $x=(x_{1},\dots,x_{n})$ is the input. Since $f$ is L-integrable, for any $\epsilon>0$, there exists $N>0$ which satisfies

For simplication, the following symbols are introduced.

$f_{1}$ denotes the positive part of$f$, while $f_{2}$ denotes the negative part. $V_{E}^{i}$ is the space between $f_{i}$ and $y=0$ in $E$, i=1,2.

For i=1,2, since $V_{E}^{i}$ is measurable, there exists a Lebesgue cover of $V_{E}^{i}$ consisting finite (n+1)-dimensional cubes $J_{j,i}$, satisfying

. We assume the number of $J_{j,i}s$ is $n_{i}$. Here and below $m(\cdot)$ denotes Lebesgue measure.

For any (n+1)-dimensional cube $J_{j,i}$, we assume

Note that each $J_{j,i}$ corresponds to an indicator function. we define

From (7) and (9), we can prove that f can be approximated by finite weighted sum of indicator function on n-dimensional cubes. Also we have

Then we will show how to use ReLU network to approximate such a function. We wish to find functions $\varphi_{j,i}$, satisfying

For any I $\in$ {$\phi_{j,i}$}, we assume

Next we will construct a network $\mathscr{A}$ to produce a function J, satisfying

We define some notations here. We denote the network by $\mathscr{A}$, the function represented by the whole network by $F_{\mathscr{A}}$, the function represented by the $kth$ layer of the network by $F_{k,\mathscr{A}}$, the function represented by the $jth$ node in the $kth$ layer by $F_{k,j,\mathscr{A}}$, the function represented by the first $k$ layers of the network after being ReLUed by $R_{k,\mathscr{A}}$. The function represented by the $jth$ node in the $kth$ layer after ReLUed is $R_{k,j,\mathscr{A}}$. Here, without loss of generality, $R_{0,\mathscr{A}}$ denotes the input layer. The weight matrix is denoted by $A$ and the offset vector by $u$. The depth is denoted by h.

For any $\delta>0,k=1,2,\dots,n$, we can design a ReLU network $\mathscr{A}_{k}$ satisfying following conditions: (1)The width of each layer of $\mathscr{A}_{k}$ is n+4. (2)The depth of $\mathscr{A}$ is 3. (3)for i=0,1,2,3, j=1,2,…,n, $R_{i,j,\mathscr{A}_{k}}=(x_{i}+N)^{+}$ (4)for j=n+1,n+2, all the weights related to $R_{i,j,\mathscr{A}_{k}}$ are 0. (5)$R_{1,n+3,\mathscr{A}_{k}}$ is a function of x such that

$0\leq R_{1,n+3,\mathscr{A}_{k}}(x)\leq 1$ for any x

$R_{1,n+3,\mathscr{A}_{k}}(x)=0$ if $(x_{1},\dots,x_{k-1})\notin[a_{1},b_{1}]\times\dots\times[a_{k-1},b_{k-1}]$

$R_{1,n+3,\mathscr{A}_{k}}(x)=1$ if $(x_{1},\dots,x_{k-1})\in[a_{1}+\delta(b_{1}-a_{1}),b_{1}-\delta(b_{1}-a_{1})]\times\dots\times[a_{k-1}+\delta(b_{k-1}-a_{k-1}),b_{k-1}-\delta(b_{k-1}-a_{k-1})]$

(6) $R_{3,n+3,\mathscr{A}_{k}}$ is a function of x such that

$0\leq R_{4,n+3,\mathscr{A}_{k}}(x)\leq 1$ for any x

$R_{4,n+3,\mathscr{A}_{k}}(x)=0$ if $(x_{1},\dots,x_{k})\notin[a_{1},b_{1}]\times\dots\times[a_{k},b_{k}]$

$R_{4,n+3,\mathscr{A}_{k}}(x)=1$ if $(x_{1},\dots,x_{k})\in[a_{1}+\delta(b_{1}-a_{1}),b_{1}-\delta(b_{1}-a_{1})]\times\dots\times[a_{k}+\delta(b_{k}-a_{k}),b_{k}-\delta(b_{k}-a_{k})]$

We call this shallow ReLU network Single ReLU Unit(SRU). We will explain some details of SRU. The first n+2 nodes in each layer is "memory element" of SRU while the last two is the "computation element" of SRU. The main idea of SRU is to process the function $R_{0,n+3,\mathscr{A}_{k}}$ to get $R_{3,n+3,\mathscr{A}_{k}}$.

The main idea of this process is to "chop" the function and reduce the support set of the function. See Figure 1 for a simulation sample when $n=2$.

We will show that, for any $\delta>0$, $J=\mathscr{A}(x_{1},x_{2},\cdots,x_{n})$ can produce exatly the same shape as the hyper-trapezoid inscribed in cube $I$ in Figure 1. For simplicity, define $\mathscr{B}_{k}=\mathscr{A}_{k}\comp\mathscr{A}_{k-1}\comp\cdots\comp\mathscr{A}_{1}$, here $k=1,2,\cdots,n$. Examine $\mathscr{B}_{1}$. The input layer is identity function in every dimension.

For simplicity, define $f^{+}=ReLU(f)$. The first hidden layer retains the information of the input layer.

The first n nodes remain unchanged thorough out the whole network $\mathscr{A}$, which are used to record the information of the input layer.The $(n+1)$ and $(n+2)$th node are reserved for the positive and negetive part of the whole target function respectively. In fact, the whole network $\mathscr{A}$ is constructed to simulate a single indicator function $I$, if the function $I$ is positive, then we will store the simulation result $J$ into the $(n+1)$th node. Otherwise, $J$ will be stored into $(n+2)$th node. By adding up those simulation results in these two nodes, we can get a simulation of $\sum_{j=1}^{n_{i}}(-1)^{i+1}b_{n+1,j,i}\phi_{j,i}$ , and thus simulates the target function. We list the result in second,third and fourth layer below.

For simplicity, denote $L_{k}=R_{4,j,\mathscr{B}_{k}}$.The network $\mathscr{A}_{k}\quad(k=2,\cdots,n)$ is similar to the case of $k=1$.The input layer is the final layer in $\mathscr{B}_{k-1}$.

For each k, we "chop" two sides in the kth dimension. Finally, we get the shape J in Figure 3.It is stored in the (n+3)th node as $L_{n}$in the last layer of $\mathscr{A}$. We then use a single layer to record it in the (n+1)th or the (n+2)th node, and reset the last two nodes to zero. Now the network is ready to simulate another (n+1)-dimensional cube. The whole construction process is shown in Figure 4.

Using this construction, we can simulate $I$ by $J$, which is produced by network $\mathscr{A}$. Note that, as $\delta$ approaches 0, the simulation error w.r.t $L_{1}$ distance converges to 0.

Next we will find a value of $\delta$ to fit the need of our proof. See Figure 3. The side length of small square on the top surface is $1-2\delta$ as the side length of the top surface. We will select a suitable $\delta>0$, satisfying $\int_{X}|I-J|d{x}<\frac{\epsilon}{4C+3\epsilon}\int_{E}|I|dx$. Denote

Notice that $I-J=0$ on $X_{0}$, and the maximum value of $I-J$ on $X$ is 1. Thus,

Thus, for $i=1,2;j=1,2,\cdots,n_{i}$, $\phi_{j,i}$ can be approximated by network function $\mu_{j,i}$. Satisfies

Sum those equations up, combined with (13), we have

Thus, we have the approximation of cubes $J_{j,i}$. Next we show how to combine those approximation functions together by network. There are $n_{1}$ positive cubes, corresponding to $n_{1}$ positive functions $\mu_{i,1}$;$n_{2}$ negative cubes, correspond to $n_{2}$ negative functions $\mu_{j,2}$. The detailed network is shown in Figure 3.

Finally, we have $g\triangleq\sum_{i=1}^{2}\sum_{j=1}^{n_{i}}(-1)^{i+1}b_{n+1,j,i}\mu_{j,i}d{x}$. $f_{0}$ is the result function produced by our designed network. Combined with (7),(9),(17), we have

Thus, $g$ is the function we need in the theorem.

A.2 Proof of Theorem 2

The proof is long and complicated, so we firstly define some notations for convenience afterwards. We denote the network by $\mathscr{A}$, the function represented by the whole network by $F_{\mathscr{A}}$, the function represented by the $kth$ layer of the network by $F_{k,\mathscr{A}}$, the function represented by the $jth$ node in the $kth$ layer by $F_{k,j,\mathscr{A}}$, the function represented by the first $k$ layers of the network after being ReLUed by $R_{k,\mathscr{A}}$. Here, without loss of generality, $R_{0,\mathscr{A}}$ denotes the input layer. We define

Condition 1: $d_{m}=n$ and the widths of all the layers except the output layer are n.

Obviously other cases where $d_{m}\leq n$ are just special cases of this setting. The weight matrix of each layer is denoted by $A_{d}$ and the offset vector by $u_{d}$ where d is the number of layer. The depth is denoted by h. Here we will introduce 2 definitions inspired by Benefits of depth in neural networks (Telgarsky ,2016).

Definition 1: A set X $\subset\ R^{n}$ is a linear block if there exist t linear functions $(q_{i})_{i=1}^{t}$, and m tuples $(U_{j},L_{j})_{j=1}^{m}$ where $U_{j}$ and $L_{j}$ are subsets of [t](where [t]:=$1,\dots,t$), such that \vec{x}\in\X is equivalent to

Definition 2: A function f:$R^{k}\to R$ is $(t,\alpha,\beta)-sa((t,\alpha,\beta)-semi-algebraic)$ if there exist t polynomials $(q_{i})_{i=1}^{t}$ of degree $\leq\alpha$, and m triples $(U_{j},L_{j},p_{j})_{j=1}^{m}$ where $U_{j}$ and $L_{j}$ are subsets of [t](where [t]:=$1,\dots,t$) and $p_{j}$ is a polynomial of degree $\leq\beta$, such that

We can see Theorem 2 is a direct conclusion of Lemma 1 as follows:

Lemma 1: Consider a function $F_{\mathscr{A}}$ represented by a relu neural network $\mathscr{A}$ where $d_{m}\leq n$, the following equation holds.

We will prove that if assumption 1 holds,

, which is equivalent to Lemma 1. To prove Lemma 1, we need Lemma 2.

Lemma 2: For any given $\mathscr{A}$ where assumption 1 and Condition 1 hold and any $k\in\{0,1,2,\dots,h-1\}$, there exists a linear block $X_{k}$ which satisfies following conditions:

$S_{2}(k)$:For any $\vec{x}\notin X_{k}$, $F_{\mathscr{A}}(\vec{x})=0$

$S_{3}(k)$:For any $\vec{x}$ in $B(X_{k})$, $F_{\mathscr{A}}(\vec{x})=0$, where $B(X_{k})$, the boundary set of $X_{k}$, is defined as $\{\vec{x}:for\ any\ \epsilon>0,\exists\vec{u}\in X_{k},\vec{v}\notin X_{k}s.t.||\vec{u}-\vec{x}||<\epsilon,||\vec{v}-\vec{x}||<\epsilon,\}$

$S_{4}(k)$:There exists a matrix $H$ and a vector $\vec{b}$ such that $R_{k,\mathscr{A}}(\vec{x})=H\vec{x}+\vec{b}$ for $\vec{x}\in X_{k}$

If Lemma 2 holds and assumption 1 holds, let $k=h-1$, $F_{\mathscr{A}}$ is a linear function on its support set, a linear block. It is not hard to prove Lemma 1 after that. However, the proof of Lemma 2 is difficult. Before getting into the detail, we’d like to make some remark. Our conclusion may seem strange at first since $F_{\mathscr{A}}$ is like a linear function. Note we derive all these conclusions under assumption 1. Our proof actually shows that assumption 1 does not hold in most cases and the expressive power of thin neural networks is weak. Before proving Lemma 2, we need Lemma 3 as a preparation.

Apparently, for any Relu neural network $\mathscr{A}$, there exists an $M_{0}$ s.t. $F_{\mathscr{A}}$ is a ($M_{0}$,1,1)-sa function. This means that there exists an M s.t. $R^{n}$ can be partitioned into M linear blocks where $F_{\mathscr{A}}$ is a linear function in each block. Furthermore, $F_{\mathscr{A}}$ must be a Lipschitz function in each block. Since $F_{\mathscr{A}}$ is continuous in $R^{n}$, it is a Lipschitz function in $R^{n}$, which means there exists an L s.t.

for any $\vec{x},\vec{y}\in R^{n}$. Then we can prove Lemma 3.

Lemma 3: If assumption 1 and Condition 1 hold, then for any ray X, if $F_{\mathscr{A}}(\vec{x})$ is constant in X, then

Proof of Lemma 3: We assume $F_{\mathscr{A}}$ is L-Lipschitz. For simplicity, let $v=F_{\mathscr{A}}(X)$ and assume $v\geq 0$ without loss of generality. Then we define a set $X^{+}=\{\vec{a}:\exists\vec{x}\in Xs.t.||\vec{x}-\vec{a}||\leq\frac{v}{2L}\}$. Apparently, $F_{\mathscr{A}}(\vec{x})\geq v/2$ for any $\vec{x}\in X^{+}$ and the volume of $X^{+}$ is $+\infty$. Thus,

Proof of Lemma 2: We prove this lemma with mathematical induction.

Basis: The k=0 case is simple. We let $X_{0}=R^{n}$. It is easy to verify that $S_{i}(0)$ holds for i=1,2,3,4.

Inductive step: Given that $S_{i}(k)$ holds for i=1,2,3,4, we will prove that $S_{i}(k+1)$ holds for i=1,2,3,4 too. Let $X_{k+1}=\{\vec{x}:\vec{x}\in X_{k}\ and\ for\ any\ j=1,2,\dots,n,\ F_{k+1,j,\mathscr{A}}(\vec{x})>0\}$. Apparently, $X_{k+1}$ is a linear block which is a subset of $X_{k}$. We will prove $X_{k+1}$ satisfies $S_{i}(k+1)$ for i=1,2,3,4.

Based on $S_{4}(k)$, it is easy to see $F_{k+1,\mathscr{A}}$ is a linear function on $X_{k}$. There exist a $n\times n$ matrix $W_{k+1}$ and a $n\times 1$ vector $b_{k+1}$ such that on $X_{k}$

Note $P_{k+1,i}$ is convex and $X_{k}$ is convex based on $S_{1}(k)$. Thus $X_{k+1}$ is convex and so that $S_{1}(k+1)$ holds.

Now we are going to prove $S_{2}(k+1)$ holds. For any $\vec{x}\in X_{k}\backslash X_{k+1}$, there exists $j(\vec{x})\in[n]$, such that $F_{k+1,j(\vec{x}),\mathscr{A}}(\vec{x})\leq 0$. Note $j(\vec{x})$ depends on $\vec{x}$, but we write it as $j$ for simplicity.

Since $W_{k+1}$ is an $n\times n$ matrix, there must exist an n-dimensional vector $\vec{\alpha}(\vec{x})\neq 0$ such that $\vec{\alpha}(\vec{x})\perp W_{k+1}(i,)\ i\in[n],i\neq j$. Note, $\vec{\alpha}(\vec{x})$ depends on $\vec{x}$, however, we write it as $\vec{\alpha}$ for simplicity. We assume $W_{k+1}(j,)\vec{\alpha}\leq 0$. If it does not hold, we substitute $-\vec{\alpha}$ for $\vec{\alpha}$. Then we consider the following set

, the intersection of $X_{k}$ and the ray corresponding to $\vec{\alpha}$ and $\vec{x}$. By $S_{1}(k)$, $X_{k}$ is convex. Obviously, the ray corresponding to $\vec{\alpha}$ and $\vec{x}$ is also convex. Thus $IRX_{\vec{x}}$ is a convex set and so that a continuous part of a ray. For any $\vec{y}\in IRX_{\vec{x}}$ and any $i\in[n],i\neq j$,

Besides, for any $\vec{y}\in IRX_{\vec{x}}$, when i=j,

In general, we find $R_{k+1,\mathscr{A}}$ is constant on $IRX_{\vec{x}}$. Therefore $F_{\mathscr{A}}$ is constant on $IRX_{\vec{x}}$. We define

Since $IRX_{\vec{x}}$ is a continuous part of a ray, $\{t:\vec{x}+t\vec{\alpha}\in IRX_{\vec{x}}\}$ is an interval.

If $T=+\infty$, then $IRX_{\vec{x}}$ is a ray and thus we can conclude $F_{\mathscr{A}}(\vec{x})=0$ by using Lemma 3.

If $T<+\infty$, for any $\epsilon>0$, there exist $T_{1},T_{2}$ such that

By the definition of $B(X_{k})$, $\vec{x}+T\vec{\alpha}\in B(X_{k})$. By $S_{3}(k)$,

. On the other hand, $F_{\mathscr{A}}$ is constant on $IRX_{\vec{x}}$. Because of continuity it is constant on

Obviously, $\vec{x}+T\vec{\alpha}\in\overline{IRX_{\vec{x}}}$. Thus,

Since $F_{\mathscr{A}}(\vec{x}+T\vec{\alpha})=0$,then

In all, for any $\vec{x}\in X_{k}\backslash X_{k+1}$, if assumption 1 holds, $F_{\mathscr{A}}(\vec{x})=0$. Besides, since for any $\vec{x}\in X_{k}^{c}$, $F_{\mathscr{A}}(\vec{x})=0$, then $S_{2}(k+1)$ holds.

Because $F_{\mathscr{A}}$ is continuous and $S_{2}(k+1)$ holds, we can easily find $S_{3}(k+1)$ holds.

It is a linear function. $S_{4}(k+1)$ holds.

Proof of Lemma 1: If assumption 1 holds, by setting $k=h-1$ in Lemma 3, we find there exists a linear block $LBX=X_{k}$ such that

$F_{\mathscr{A}}(\vec{x})=0\ for\ any\ \vec{x}\notin LBX\ or\ \vec{x}\in B(LBX)$

$R_{h-1,\mathscr{A}}$ is a linear function on LBX.

, $F_{\mathscr{A}}$ is a linear function on LBX. As $F_{\mathscr{A}}=0$ outside LBX, to finish the proof we just need to prove that for any $\vec{x}\in LBX$, $F_{\mathscr{A}}(\vec{x})=0$. For any $\vec{x}\in LBX$, let

Since LBX and $L_{\vec{x}}$ are both convex, $IL_{\vec{x}}$ is convex. Thus there exists an interval A such that

Apparently, $F_{\mathscr{A}}(t\vec{x})$ is a linear function of t on A. Define

If $a>-\infty,b<+\infty$,then $a\vec{x},b\vec{x}\in B(LBX)$. Thus

. Since $F_{\mathscr{A}}(t\vec{x})$ is a linear function,

If $a>-\infty,b=+\infty$ or $a=-\infty,b<+\infty$, we assume $a=-\infty,b<+\infty$ without loss of generality. Then $F_{\mathscr{A}}(b\vec{x})=0$. If $F_{\mathscr{A}}(\vec{x})\neq 0$, because of the linearity of $F_{\mathscr{A}}$

Since $F_{\mathscr{A}}(\vec{x})$ is Lipschitz, it contradicts with $\int_{R^{n}}|F_{\mathscr{A}}(\vec{x})|<+\infty$. So $F_{\mathscr{a}}(\vec{x})=0$

If $a=-\infty,b=+\infty$, we can prove $F_{\mathscr{A}}(\vec{x})=0$ in a similar way.

In general, $F_{\mathscr{A}}(\vec{x})=0$ for any $\vec{x}\in R^{n}$ if assumption 1 holds.

Then obviously Theorem 2 is a direct result of Lemma 1.

A.3 Proof of Theorem 3

We denote the input by $\vec{x}=(x_{1},x_{2},...,x_{n})$, and the value of the first layer’s nodes of $A$ by $y=(y_{1},y_{2},...,y_{m})$, here $m<n$ and let

where $i=1,2,\cdots,n$, $j=1,2,\cdots,m$.$b_{i}$ and $a_{ij}$ are parameters of $A$.Since $m<n$, there exists a non-zero vector $x_{0}$ in $R_{0}^{n}$, which satisfies

Since changes along $x_{0}$ don’t affect the first layer of network $A$: $F_{A}$, which is determined by the first layer of $A$ itself, it is constant along $\vec{x}_{0}$ as a result. Thus $F_{A}$ must be constant along some fixed direction $x_{0}$.

Now we can prove that: given f and a fixed unit vector $x_{0}$, we have a positive $\epsilon$ that for all continuous $F$ which is constant along the direction $x_{0}$, the $L^{1}$ distance between $f$ and $F$ is lower bounded by $\epsilon$. Pick two points $a_{0}$ and $b_{0}$ along $x_{0}$ that $f(a_{0})<f(b_{0})$, due to the continuity of $f$, there exists positive $r$ and $c$ that for all $a$ in $U(a_{0},r)$ and $b$ in $U(b_{0},r)$, $f(b)-f(a)>c$. Let the lebesgue-measure of $U(a_{0},r)$ be $V$, with the triangle inequality $|f(b)-F(b)|+|f(b-b_{0}+a_{0})-F(b-b_{0}+a_{0})|>f(b)-f(b-b_{0}+a_{0})>c$, we can see there exists such an $\epsilon$ which is $>=Vc$.

Then treat $\epsilon$ as a function of $x_{0}$. Since $\epsilon$ is positive and continuous because $f$ and $F$ are continuous and have compact domain (so any such $F$ is uniformly continuous, then ’rotating’ $F$ by a small angle guarantees a small uniform difference, one can easily see $\epsilon$ is continuous now), it has a lower bound over all unit vector $x_{0}$. Denote this lower bound as $\epsilon^{*}$, $\epsilon^{*}$ must be positive because the set of all unit vector $x_{0}$ is a compact set (see it as the surface of unit ball). Since $F_{A}$ must be constant along some direction, $\epsilon^{*}$ is the desired universal constant for all $F_{A}$.

A.4 Proof of Theorem 4

We first prove the case with input dimension $n=1$, then the extension to $n>1$ cases is trivial.

We will choose $2k^{4}$ different points $x^{(1)},x^{(2)},\dots,x^{(2k^{4})}\in R$ and consider functions represented by ReLU network on them. Here,

For any ReLU network $\mathscr{A}$, we define a $2k^{4}$-dimensional vector

We will begin our proof by introducing 2 lemmas.

For any $f\in E_{0}$, we will fabric a ReLU network $\mathscr{A}$ with width $2k^{2}$ and depth 3 such that $f=f_{\mathscr{A}}$. Firstly, it is easy to choose appropriate first layer weights and bias to make

Denote the weights and bias of kth layer by $W_{k,\mathscr{A}}$ and $B_{k,\mathscr{A}}$. $W_{k,\mathscr{A}}$ is a matrix and $B_{k,\mathscr{A}}$ is a vector such that

Define $F_{2,i,\mathscr{A}}$ to be the function at the $ith$ node in the second layer, which is a piecewise linear function which is linear between any integral points on the x-axis. It satisfies:

Together with the linearity between integral points on the x-axis, the function represented by the $ith$ node can be uniquely decided. Then we activate those functions by RELU, and add them up to get the final output $f_{\mathscr{A}}$. One can easily check that

Combined with the definition of $E_{0}$ and $E_{w}$, we have:

Lemma 5: For any k$\geq$5, only a 0 measure set(Lebesgue measure on the weight and bias space) of the networks in $\mathscr{F}_{k}$ can be equaled by a deep network whose width $\leq k^{\frac{3}{2}}$ and depth $\leq k+2$.

We prove a stronger statement: only a 0 measure set(Lebesgue measure on the weight and bias space) of the networks in $\mathscr{F}_{k}$ can be equaled on specific $2k^{4}$ different points $x^{(1)},x^{(2)},\dots,x^{(2k^{4})}$,by a deep network whose width $\leq k^{\frac{3}{2}}$ and depth $\leq k+2$. Notice the fact that a network with width $d$ and depth $h$ has degree of freedom = $d^{2}(h-2)+d(h-1)+2d+1$. Define $\mathscr{B}$ to be one of the deep networks, with width $d\leq k^{\frac{3}{2}}$ and depth $h\leq k+2$. Let $g_{0}$ be the function mapping the parameters of the deep network to $f_{\mathscr{B}}$:

When $d\leq k^{\frac{3}{2}}$ and $h\leq k+2$, the degree of freedom of the deep network $\leq k^{4}+k^{3}<2k^{4}$, and $g_{0}$ is $C_{1}$-derivable almost everywhere. Thus, $B$: the set of all $\beta$, which is the solution space of $g_{0}$ has a zero measure in $R^{2k^{4}}$ according to Differential Homeomorphism Theorem. In fact, we can implement the original mapping to a new function $g_{1}$

in the way of adding variables $p_{1},p_{2},...,p_{2k^{4}-d^{2}(h-2)-d(h-1)-2d-1}$ which have no effect on the value of $F$, then the Jacobian of $g_{1}$ is zero now because the differential of $F$ to $p_{i}$s is 0, thus by the transform formulation of integration, the measure of the range is zero.

It’s obvious that $m(E_{0})>0$, so $E_{0}\cap range(g_{1})$ is a negligible subset in $E_{0}$ and as a result only a negligible set of the functions in this family of wide networks can be equaled by such deep networks.

Then because all parameters in these deep networks are bounded, we can extend the difference on finite points to integration on input domain.

Apparently, the shape of such a deep network can be denoted by a vector whose $m^{th}$ entry denotes the width of the $m^{th}$ layer except for the output layer. We denote the shape vector of a network $N$ by S(N). Thus for all networks with $h\leq k+2$ and $d_{m}\leq k^{1.5}$,

Denote the all elements of $V$ by $\{V_{j}\}$, we only need to prove Lemma 6 as followed,then $n=1$ case is proved directly by setting $\epsilon=min_{j\leq|V|}\{\epsilon_{j}\}$:

Lemma 6: For any wide network $N_{w}$ which can’t be equaled by deep networks with width $\leq k^{1.5}$ and depth $\leq k+2$ as above, there exists a $\epsilon_{j}>0$ for all deep network $N_{d}$ with $S(N)=V_{j}$ satisfies

Set $\epsilon_{j}=inf\{\int_{0}^{2k^{2}}(N_{d}(x)-N_{w}(x))^{2},S(N_{d})=V_{j}\}$ We are going to prove $\epsilon_{j}>0$. With the conclusion of inequability above and continuity of the function $N_{d}\ and\ N_{w}$, we know for any

Thus, if $\epsilon_{j}=0$ There must be a sequence $N_{d_{i}}$ satisfies

This causes contradiction to our conclusion of inequability above. So $\epsilon_{i}>0$ and we are finished with the proof of the case with $n=1$. ∎

For cases with $n>1$, we denote these $n$ inputs by $x_{1},...,x_{n}$. We construct the same wide network for $x_{1}$ only and ignore other inputs(set the weights from them to the first later to be 0). Our wide network still has width $2k^{2}$ and depth 3, and for any deep network with width $\leq k^{1.5}$ and depth $\leq k+2$ all our results above hold as well (for the choice of the prechosen $2k^{4}$ points, their value on $x_{2},...,x_{n}$ can be arbitary). The whole proof is finished now.