Neural Networks with Small Weights and Depth-Separation Barriers

The expressive power of feedforward neural networks has been extensively studied in recent years. It is wellknown that sufficiently large depth-2 neural networks, using reasonable activation functions, can approximate any continuous function on a bounded domain (Cybenko [1989], Funahashi [1989], Hornik [1991], Barron [1994]). However, the required size of such networks can be exponential in the input dimension, which renders them impractical. From a learning perspective, both theoretically and in practice, the main interest is in neural networks whose size is at most polynomial in the input dimension. When considering the expressive power of neural networks of bounded size, a key question is what are the tradeoffs between the width and the depth. Overwhelming empirical evidence indicates that deeper networks tend to perform better than shallow ones, a phenomenon supported by the intuition that depth, providing compositional expressibility, is necessary for efficiently representing some functions. From the theoretical viewpoint, quite a few works in the past few years have explored the beneficial effect of depth on increasing the expressiveness of neural networks.