Some recent work has shown separation between the expressive power of depth-2 and depth-3 neural networks. These separation results are shown by constructing functions and input distributions, so that the function is well-approximable by a depth-3 neural network of polynomial size but it cannot be well-approximated under the chosen input distribution by any depth-2 neural network of polynomial size. These results are not robust and require carefully chosen functions as well as input distributions.

 We show a similar separation between the expressive power of depth-2 and depth-3 sigmoidal neural networks over a large class of input distributions, as long as the weights are polynomially bounded. While doing so, we also show that depth-2 sigmoidal neural networks with small width and small weights can be well-approximated by low-degree multivariate polynomials. Understanding the remarkable success of deep neural networks in many domains is an important problem at present (e.g., BID10 ). This problem has many facets such as understanding generalization, expressive power, optimization algorithms in deep learning. In this paper, we focus on the question of understanding the expressive power of neural networks. In other words, we study what functions can and cannot be represented and approximated by neural networks of bounded size, depth, width and weights.The early results on the expressive power of neural networks showed that the depth-2 neural networks are universal approximators; that is to say, with only mild restrictions on the activation functions or neurons, the depth-2 neural networks are powerful enough to uniformly approximate arbitrary continuous functions on bounded domains in R d , e.g., BID2 ; BID9 ; BID0 . However, the bounds that they provide on the size or width of these neural networks are quite general, and therefore, weak. Understanding what functions can be represented or wellapproximated by neural networks with bounded parameters is a general direction in the study of expressive power of neural networks. Here the parameters could mean the number of neurons, the width of hidden layers, the depth, and the magnitude of its weights etc.Natural signals (images, speech etc.) tend to be representable as compositional hierarchies BID10 , and deeper networks can be thought of as representing deeper hierarchies. The power of depth has been a subject of investigation in deep learning, e.g., BID8 . We are interested in understanding the effect of depth on the expressive power. In particular, one may ask whether having more depth allows representation of more functions if the size bound remains the same. BID5 show a separation between depth-2 and depth-3 neural networks. More precisely, they exhibit a function g : R d → R and a probability distribution µ on R d such that g is bounded and supported on a ball of radius O( √ d) and expressible by a depth-3 network of size polynomially bounded in d. But any depth-2 network approximating g in L 2 -norm (or squared error) within a small constant under the distribution µ must be of size exponentially large in d. Their separation works for all reasonable activation functions including ReLUs (Rectified Linear Units) and sigmoids. The function and the input distribution in BID5 are carefully constructed and their proof techniques seem to crucially rely on the specifics of these constructions. Building upon this result, BID14 show that while the indicator function of the L 2 -ball can be well-approximated by depth-3 networks of polynomial size, any good approximation to it by depth-2 networks must require exponential size. Here, the notion of approximation in the lower bound is the same as in BID5 and a carefully constructed distribution that is arguably not quite natural.Daniely (2017) (see also BID12 ) also gave a separation between depth-2 and depth-3 networks by exhibiting a function g : S d−1 × S d−1 → R which can be well-approximated by a depth-3 ReLU neural network of polynomially bounded size and weights but cannot be approximated by any depth-2 (sigmoid, ReLU or more general) neural network of polynomial size with (exponentially) bounded weights. This separation holds under uniform distribution on S d−1 × S d−1 , which is more natural than the previous distributions. However, the proof technique crucially uses harmonic analysis on the unit sphere, and does not seems robust or applicable to other distributions. Telgarsky (2016) shows a separation between depth-2k 3 + 8 and depth-k ReLU neural networks, for any positive integer k, when the input is uniformly distributed over [−1, 1] d . BID11 (see also BID14 BID21 ) show that there are univariate functions on a bounded interval such that neural networks of constant depth require size at least Ω (poly(1/ )) for a uniform -approximation over the interval, whereas deep networks (the depth can depend on ) can have size O (polylog(1/ )).The above separation results all fit the following template: certain carefully constructed functions can be well approximated by deep networks, but are hard to approximate by shallow networks using a notion of error that uses a carefully defined distribution. (Only Liang & Srikant (2017) is distribution-independent as it deals with uniform approximation everywhere in the domain). Thus these results do not tell us the extent to which deeper networks are more expressive than the shallow ones. We would like to understand whether there are large classes of functions and distributions that witness the separation between deep and shallow networks. An answer to this question is also more likely to shed light on practical applications of neural networks. BID17 ; BID16 ; BID18 show that even functions computed by a depth-2 neural network of polynomial size can be hard to learn using gradient descent type of algorithms for a wide class of distributions. These results address questions about learnability rather than the expressive power of deep neural networks. BID7 shows that piecewise affine functions on [0, 1] d with N pieces can be exactly represented by a width (d + 3) network of depth at most N . Lower bound of Ω((N + d − 1)/(d + 1)) on the depth is proven for functions of the above type when the network has width at most (d + 1) and very closely approximates the function.Our depth separation results apply to neural networks with bounds on the magnitudes of the weights. While we would prefer to prove our results without any weight restrictions, we now argue that small weights are natural. In training neural networks, often weights are not allowed to be too large to avoid overfitting. Weight decay is a commonly used regularization heuristic in deep learning to control the weights. Early stopping can also achieve this effect. Another motivation to keep the weights low is to keep the Lipschitz constant of the function computed by the network (w.r.t. changes in the input, while keeping the network parameters fixed) small. BID6 contains many of these references. One of the surprising discoveries about neural networks has been the existence of adversarial examples BID19 ). These are examples obtained by adding a tiny perturbation to input from class so that the resulting input is misclassified by the network. The perturbations are imperceptible to humans. Existence of such examples for a network suggests that the Lipschitz constant of the network is high as noted in BID19 . This lead them to suggest regularizing training of neural nets by penalizing high Lipschitz constant to improve the generalization error and, in particular, eliminate adversarial examples. This is carried out in BID1 , who find a way to control the Lipschitz constant by enforcing an orthonormality constraint on the weight matrices along with other tricks. They report better resilience to adversarial examples . On the other hand, BID13 suggest that Lipschitz constant cannot tell the full story about generalization.
depth-2-vs-3 separation for sigmoidal neural networks over general distributions
{"src": "scitldr-AIC_train", "paper_id": "SJICXeWAb"}