Rational approximation techniques for analysis of neural networks

Artificial neural networks are comprised of an interconnected collection of certain nonlinear devices; examples of commonly used devices include linear threshold elements, sigmoidal elements, and radial-basis elements. We employ results from harmonic analysis and the theory of rational approximation to obtain almost tight lower bounds on the size (i.e., number of elements) of neural networks. The class of neural networks to which our techniques can be applied is quite general it includes any feedforward network in which each element can be piecewise approximated by a low degree rational function. For example, we prove that any depth-d+1 network of sigmoidal units or linear threshold elements computing the parity function of n variables must have R(dn¹/d-ε) size, for any fixed ε>0. In addition, we prove that this lower bound is almost tight by showing that the parity function can be computed with O(dn¹d/) sigmoidal units or linear threshold elements in a depth-(d+1) network. These almost tight bounds are the first known complexity results on the size of neural networks with depth more than two. Our lower bound techniques yield a unified approach to the complexity analysis of various models of neural networks with feedforward structures. Moreover, our results indicate that the in the context of computing highly oscillating symmetric Boolean functions, networks of continuous-output units such as sigmoidal elements do not offer significant reduction in size compared with networks of linear threshold elements of binary outputs