It is well-known that neural networks are universal approximators, but that deeper networks tend in practice to be more powerful than shallower ones. We shed light on this by proving that the total number of neurons m required to approximate natural classes of multivariate polynomials of n variables grows only linearly with n for deep neural networks, but grows exponentially when merely a single hidden layer is allowed. We also provide evidence that when the number of hidden layers is increased from 1 to k, the neuron requirement grows exponentially not with n but with n^{1/k}, suggesting that the minimum number of layers required for practical expressibility grows only logarithmically with n. Deep learning has lately been shown to be a very powerful tool for a wide range of problems, from image segmentation to machine translation. Despite its success, many of the techniques developed by practitioners of artificial neural networks (ANNs) are heuristics without theoretical guarantees. Perhaps most notably, the power of feedforward networks with many layers (deep networks) has not been fully explained. The goal of this paper is to shed more light on this question and to suggest heuristics for how deep is deep enough.It is well-known BID7 BID11 BID15 BID1 BID23 that neural networks with a single hidden layer can approximate any function under reasonable assumptions, but it is possible that the networks required will be extremely large. Recent authors have shown that some functions can be approximated by deeper networks much more efficiently (i.e. with fewer neurons) than by shallower ones. Often, these results admit one or more of the following limitations: "existence proofs" without explicit constructions of the functions in question; explicit constructions, but relatively complicated functions; or applicability only to types of network rarely used in practice.It is important and timely to extend this work to make it more concrete and actionable, by deriving resource requirements for approximating natural classes of functions using today's most common neural network architectures. BID17 recently proved that it is exponentially more efficient to use a deep network than a shallow network when Taylor-approximating the product of input variables. In the present paper, we move far beyond this result in the following ways: (i) we use standard uniform approximation instead of Taylor approximation, (ii) we show that the exponential advantage of depth extends to all general sparse multivariate polynomials, and (iii) we address the question of how the number of neurons scales with the number of layers. Our results apply to standard feedforward neural networks and are borne out by empirical tests.Our primary contributions are as follows:• It is possible to achieve arbitrarily close approximations of simple multivariate and univariate polynomials with neural networks having a bounded number of neurons (see §3).• Such polynomials are exponentially easier to approximate with deep networks than with shallow networks (see §4).• The power of networks improves rapidly with depth; for natural polynomials, the number of layers required is at most logarithmic in the number of input variables, where the base of the logarithm depends upon the layer width (see §5). We have shown how the power of deeper ANNs can be quantified even for simple polynomials. We have proved that arbitrarily good approximations of polynomials are possible even with a fixed number of neurons and that there is an exponential gap between the width of shallow and deep networks required for approximating a given sparse polynomial. For n variables, a shallow network requires size exponential in n, while a deep network requires at most linearly many neurons. Networks with a constant number k > 1 of hidden layers appear to interpolate between these extremes, following a curve exponential in n 1/k . This suggests a rough heuristic for the number of layers required for approximating simple functions with neural networks. For example, if we want no layers to have more than 2 10 neurons, say, then the minimum number of layers required grows only as log 10 n. To further improve efficiency using the O(n) constructions we have presented, it suffices to increase the number of layers by a factor of log 2 10 ≈ 3, to log 2 n.The key property we use in our constructions is compositionality, as detailed in BID24 . It is worth noting that as a consequence our networks enjoy the property of locality mentioned in , which is also a feature of convolutional neural nets. That is, each neuron in a layer is assumed to be connected only to a small subset of neurons from the previous layer, rather than the entirety (or some large fraction). In fact, we showed (e.g. Prop. 4.6) that there exist natural functions computable with linearly many neurons, with each neuron is connected to at most two neurons in the preceding layer, which nonetheless cannot be computed with fewer than exponentially many neurons in a single layer, no matter how may connections are used. Our construction can also be framed with reference to the other properties mentioned in : those of sharing (in which weights are shared between neural connections) and pooling (in which layers are gradually collapsed, as our construction essentially does with recursive combination of inputs). This paper has focused exclusively on the resources (neurons and synapses) required to compute a given function for fixed network depth. (Note also results of BID18 ; BID13 ; BID12 for networks of fixed width.) An important complementary challenge is to quantify the resources (e.g. training steps) required to learn the computation, i.e., to converge to appropriate weights using training data -possibly a fixed amount thereof, as suggested in Zhang et al. (2017) . There are simple functions that can be computed with polynomial resources but require exponential resources to learn (Shalev-Shwartz et al., 2017) . It is quite possible that architectures we have not considered increase the feasibility of learning. For example, residual networks (ResNets) BID14 and unitary nets (see e.g. BID0 BID16 ) are no more powerful in representational ability than conventional networks of the same size, but by being less susceptible to the "vanishing/exploding gradient" problem, it is far easier to optimize them in practice. We look forward to future work that will help us understand the power of neural networks to learn. Without loss of generality, suppose that r i > 0 for i = 1, . . . , n. Let X be the multiset in which x i occurs with multiplicity r i .We first show that n i=1 (r i + 1) neurons are sufficient to approximate p(x). Appendix A in Lin et al. (2017) demonstrates that for variables y 1 , . . . , y N , the product y 1 · · · · · y N can be Taylorapproximated as a linear combination of the 2 N functions σ(±y 1 ± · · · ± y d ).Consider setting y 1 , . . . , y d equal to the elements of multiset X. Then, we conclude that we can approximate p(x) as a linear combination of the functions σ(±y 1 ± · · · ± y d ). However, these functions are not all distinct: there are r i + 1 distinct ways to assign ± signs to r i copies of x i (ignoring permutations of the signs). Therefore , there are DISPLAYFORM0
We prove that deep neural networks are exponentially more efficient than shallow ones at approximating sparse multivariate polynomials.
{"src": "scitldr-AIC_train", "paper_id": "SyProzZAW"}